잉여역수 활용
게시글 주소: 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
옯붕이들 ㅂㅂ
-
그러면 뭐하냐 맨날 보던 사람밖에 없는데
-
선샌니 저 하장실가따와도데요??ㅠㅠ
-
아이큐검사 2
120 몇인가 그랬음
-
동서연고. 1
무요.. 왜요.. 혼잣말이에요..
-
새르비에 2
기만자들 왤케 많음
-
다시 예전처럼 하자 다시는 오늘처럼 살지 않으리
-
아 손아파 ㅠㅠ 8
ㅠㅠ
-
진짜 하나도 모르겠던데 몰, 파장, 종속~ 빼고는
-
본인이 저능하다 말하는 사람보다 대학 못 간거면 어떻게 되는 거야 내가 더 저능하다...
-
인사해주세요 6
언제나 고민이 많아지네요,, 반가워요 선생님,, ,,
-
저질렀다 2
아
-
미치겠네
-
이대 꿀팁 5
기숙사 안에 미용실 2만원대인데 친구 레이어드 컷 맛깔나게 잘해줌 외부인도 머리 가능
-
뭐 유급빡세게 때린다는데 스택이지금 1이라 (정공) 예2는 끝나야 갈수있을거같은데 ㄱㅊ음?
-
아이큐 ㅇㅈ 2
시공간 통찰력 높은편이더라
-
막상 키를 재지는 않고 쌤이 그냥 적당히 올려치기해서 적어서 내라고 했었음ㅋㅋㅋ 개웃걌는데
-
어떻게 끌어올리셨나요? 조언부탁해요
-
그만늙고싶다 4
후
-
학평 ㅇㅈ 3
전설의 언매 ALL틀
예?
일차방정식 ㄷㄷ