잉여역수 활용
게시글 주소: 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
사실 나 성격이 좀 많이 안좋음
-
막 무슨 혐오식품 이런거만 아니면 안먹는 몇개 있긴 한데 ㄹㅇ 그거빼곤 다잘먹음...
-
가보자가보자
-
알바끝 6
헤으응 힘들어 낼 11시까지 어디 가야해서 얼마못잠
-
9900원 곱창집아냐 12
구라안치고 모둠곱창이 9900원이고 순두부찌개랑 부추 무한리필 위는 호밀밭 빙수인데...
-
롤의정리 4
롤은 재밌다
-
잘생겨지고싶다 8
존잘러들의 삶을 살아보고 싶다
-
계속공급이 들어와!!!!!!
-
최근에 알게 되었는데 행복의 50%정도는 유전이래
-
있으면 된다(충분조건) -> x 있어야 한다(필요조건) -> x 있으면 좋다 ->...
-
무적건 연대임 ㅋㅋ
-
ㅇㅈ 12
비슷하게 생김.
-
롤할사람 4
모집ㅂ중
-
.. 4
작수 2등급인데 29 30 제대로 풀진 못하고요 28번도 웬만하면 못풀고 27풀때쯤...
-
건대가는데 지장없겠지?
-
평능아로 과탐 잘보는거힘들어
-
호감 오르비언 닉언하기 10
순대렐라 순대렐라
-
심심한 4
좋은 닉네임임
-
형님이라고 부를까 생각중임
-
잠 9
따
예?
일차방정식 ㄷㄷ