잉여역수 활용
게시글 주소: 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를 선물하세요.
-
2021 9 21(가형) 그래프가 아닌 원으로 생각해보기 4
유튜브 정병훈 선생님 21년도 9월 21번(가형) 고찰 참고하여 단위원으로부터...
-
수도퀴즈 ㅇㅈ 8
쉽지 않네...
-
추합이라 가입을 못해서.. 시간표 짜는데만 사용하고 사례도 할게요..
-
새르비도 하고 뻘글도 써야겟다
-
24 수능 88점 25 6모 70점인데 이거 뭐임???? 2
아니 그래도 기출 돌리면서 단 한번도 84점 밑으로 내려간 적이 없었거든? 특히나...
-
아아악
-
총균쇠 일부분 따오고 책제목 맞춰봐 하면 어떻게 맞춤
-
안 자도 일단은 죽진 않는거 같은데
-
물화는 시간이 안남아서 항상 쫓기듯이 해서 뭔가 상상이 안가 시간이 남는다는게
-
심찬우 형님 재종생활 힘들어도 견디시면 좋은날 올겁니다 7
시대 재종에서 "아 심찬우네 걸러야지." 이 소리만 15번 들은거 같은데 실력으로 증명해봅시다
-
노마드 in100인데 아직도 픽업이 없다는게 말이 안됨... 각전 일러 개꼴인데 ㅠ
-
수강신청날 하루아침에 벼락거지가 된 내가 마이너스 통장같았던 시간표 들고 있다가...
-
논란빼고 순수실력으로만 알려주셈
-
현역 정시파이터이고 선택과목은 현재 언매 미적 생명은 좋아해서 계속 들고가려고...
-
ㅠㅠㅠ
-
원래 단과 강사들 쉬는 시간에 질문 안받아주지 아늠? 5
남지현 이 쌤은 거의 쉬는 시간 10분 하면 7분은 질문받던데 이쌤이 특이한거냐?
-
무기한 휴르비 1
-
손잡아보고싶구나
-
그렇다고 방임은 아니시고 폰은 늦게 사주시는 등 주변 친구들이랑 대화하다 보면...
-
지인선 N제가 9번~15번 / 20~22번까지 다뤘으니 지인선 입문 n제가...
예?
일차방정식 ㄷㄷ