잉여역수 활용
게시글 주소: 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를 선물하세요.
-
상병때도 저격맞는구나
-
맞팔 구합니다 3
현역학생입니다 물리러에요
-
1. 요즘제가 프리미엄/프리미엄 플러스로 나뉘어 있던데 무엇을 쓰시는지 2....
-
핑크핑크
-
혼자갈건데 풍족하게쓸거면 30?
-
흠
-
나만 없나
-
기출 좋앗던거 3
241122 (개 잘 만든문제)121130 (함수의 증가속도, 아주 중요한 관점)...
-
둘 다 가져가는게 경제학적으로 합리적인거같긴 한데 또 완벽하게 예측한다고하니까...
-
오르비 공감 19
명문대생들이 뻘글 쓰고 같이 댓글 달고 노니까 공부는 안하면서 나도 그들이랑 비슷한 줄 알게 됨
-
25경제 22점... 25
(상업)경제 22점... 5등급 입갤 작수 그냥 경제는 아무 공부없이 풀었을때...
-
ㅈㄱㄴ
-
싸악
-
허수 특징 22
좆도 실력 없는새끼들이 이커뮤니티 저커뮤니티 돌아다니면서 얻어들은 지식가지고 풀지도...
-
공부 잘하는 여자를 만나야하는이유
-
-
불편해요 더워....
-
다들건강해랑
예?
일차방정식 ㄷㄷ