잉여역수 활용
게시글 주소: https://orbi.kr/00072132800
실수세계에서 보던 일들을 좀 더 Local한 세계인 Z_m 세계로 가져와보자. (m으로 나눈 나머지)
예를 들어 Z_{20}이라는 세계에선, 1과 21은 아예 똑같은 숫자이다.
우리는 Z_m에서의 일차방정식을 푸는 것이 목적이다.
즉, ax==b (modm)의 해를 찾는 것.
만약, a의 역수가 존재한다면..?
x==(b/a) (modm)이 되겟다.
역수가 존재할 조건은 뭘까.
그것은 바로 "a와 m이 서로소인 것"이다.
역수가(곱셈에 대한 역원) 존재한다는 말은 어떤 c에 대해,
ac == 1 (modm)이 되는 c가 존재한다는 것이다.
이 방정식의 해를 찾는 알고리즘은, 이미 기원전에 알려졋다 (유클리드 알고리즘), 또한 이 c는 유일하다. (modm으로)
해가 존재할 조건도, (전에 말햇듯이 a와 m은 서로소)
참고(깊은 이야기) "Z_m에서 m과 서로소"라는 말은 실수세계에선 "0이 아니다"라는 말과 같은 말이다.
예를 들어, 3x==8 (mod11)의 해를 찾아보자.
그러면, 바로 x==8/3 (mod11)로 찾아주면 된다.
정수로 정리해주려면, 3*4=1(mod11)이므로, 3의 역수는 4가 된다.
즉 x==8/3=8*4==32==10 (mod11)로 바로 찾아줄 수 잇다.
다른 방법은,
3x==8 (mod11)
=> x==8/3==(8+22)/3==10 (mod11)로 정리해주면 되겟다.
0 XDK (+0)
유익한 글을 읽었다면 작성자에게 XDK를 선물하세요.
-
아 썅 1 0
아이큐 테스트 ㅈㄴ 정성스럽게 했는데 결과를 보려면 수수료 이지랄 ㅋㅋㅋㅋㅋㅋㅋㅋㅋ
-
프셐) 자랑좀 하겠읍니다 4 0
오시 올클인데 돌 없어서 담달에 깨질거 같습니다...
-
친구가 요리해준대요 22 2
멋있다
-
지인선n제 표지 겁나 예쁨 6 2
4월에 아름아름 풀거라 일단 킵
-
논술 0 0
논술 공부하는 학생들은 아래 블로그 글 정독해보세요 큰 도움이 될 겁니다....
-
이창무선생님은 타수가 낮은 이유가 뭘까요??? 12 0
정말 잘 가르치신다고 생각하는데... 대성수학이 워낙 빵빵하기는하지만요 뭐일까요???
-
솔직히 전형이 너무 조잡스럽긴함 14 3
그냥 롤 랭크마냥 6 9 배치고사 치고 수능 쇼부봐서 대학보내면안대나
-
암산테스트 1초당 하나 연습중 8 0
이론상 120점 가능하긴한데... 현 최고기록
-
프셐 뉴비 ㅇㅈ 4 0
출첵 하루이틀 빼곤 다 했을듯
-
자퇴 정시파이터 옯붕이는 댓좀 9 2
친목질좀하자
-
공부 잘하게 생겼는데 공부 못한다고 한소리 들음
-
학종으로 한양의 기원 4일차 3 2
젭알
-
지구1 1등급 지구2 1등급 둘 중 뭐가 더 어려움???
-
사실 이미 작년 2학기 혼자 다녀서 괜찮대요
-
나 요즘 오르비 줄였다 14 0
칭찬해줘 응응
-
뱃지 신청하면 3 0
보통 얼마정도후에 발급되나여? 빨리 받고싶다 !!!!
-
경제러분들 중에 심심하신 분 14 0
25수능 직업탐구 상업경제 풀어보시고 난이도에 대해 얘기해주실 수 있나요
-
피터 = 베드로 야곱 = 제이콥 안드레아 = 앤드류 요한 = 요한, 존 다윗 =...
-
잘생겨지는법 2 0
1.태어난다 2.리세마라를한다 3-1차은우로 태어난다 3-2.1번부터 반복
예?
일차방정식 ㄷㄷ