잉여역수 활용
게시글 주소: 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를 선물하세요.
-
이거 짤라도 되겠죠?...
-
06년생입니다 작수 수능 44444이고 군대 가라는데(원래는 재수 할려고 했고...
-
햄버거 먹말? 1
11시쯤 집밥 차려먹었는데 어제 저녁을 안 먹어서 그런가 또 배고픔뇨
-
디코 그거 1
큐떠블류 이알아님?
-
비독원이랑 뭐 하나 더 해야할거같은데 기출은 비독원애 많을거같긴한데 기출 or 리트...
-
신기하다
-
미쳐버린거지
-
폐기 맛도리 도시락 5개 가져가는거 양심 없진 않겠죠….?
-
초싸가 되버림
-
시간표가 반수하라고 칼들고 협박한다 ㅅㅂ ㅋㅋㅋㅋㅋㅋㅋ
-
XY 염색체는 보이지 않는 글 입니다.
-
작수 딱 3컷인데 하루에 미적분 1강 공통 격일로 2강씩 총 3강 듣는데 풀이가...
-
죠죠 댔다
-
한양대 추가모집 2
올해 안 하나?
-
공허 2
하다
-
영원할거라고 말했잖아
-
미용실 갈건데 2
헤어스타일 추천좀
-
본인이 가진거 보내주거나 남에거 사서 다른사람에게 주고 그러면 재미있을텐데
-
신촌이 베스트인건 머 아는데 다른데가 궁금하네 ㅇㅇ
-
강기분언매 듣고있는데 복습을 하긴 하거든요 님들 공부할때 모든 컨디션을 외울때까지...
예?
일차방정식 ㄷㄷ