잉여역수 활용
게시글 주소: 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를 선물하세요.
-
하 ㅠㅠㅠ 오지훈과 함께한 내 추억은??
-
자고일어나서마저할수도
-
새르비하고 10
자고일어날때쯤 담젠전하겠네 흐흐 즐거운 잉여생활
-
귀엽다는거임
-
당연한거임
-
이름 뭐로 바꾸지 13
도로시로 갈아탈까
-
연구원인데 떼잉,,삼각함수랑 수열을 훨 잘함 지로함에 비하면
-
냥대 크아아아악 6
크오아오아앙
-
"예수를 배반한 제자가 유다" 라는 사실을 아는 게 상식인지 여부로 논란이 된 적이...
-
자
-
ㅇㅈ 23
생일이에용
-
약간 싸이코패스된것같음 23
존나뜬금없이 부모님 이혼통보받았는데 전혀안슬퍼서 그냥그렇군요... 한다음 바로...
-
메이저의나 인설의쯤 가서 옯창 되면 보통 금테 달더라고요 오르비 8년 넘게 하면서 든 생각 ㅇㅇ
-
주위에있으면 뭐라하진못하고.. 그냥내가최대한빨리자리를뜸
-
불면증.. 4
원하는 기상시간보다 45분이나 일찍일어나버렸다
-
ㄱㄱ
-
평균만 가졌다면...
-
다들 대학을 보내주었던 하나의 간절함/무기가 있음? 20
공유해주세요!
-
잘까 4
흠
-
241122. 5
진짜 딱 삼차함수여서 결정됨. 머지 진짜아주 멋잇음. 출제자랑 대화해보고 시픔
예?
일차방정식 ㄷㄷ