잉여역수 활용
게시글 주소: 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를 선물하세요.
-
못푸는 문제는 없는데 처리속도가ㅜ딸려서 시간안에 다 못풀어
-
슬슬 5
닉변할 때가 온거 가튼데
-
정겹고 좋네요~
-
라면 4
하루에 두개 먹는 건 에바겠지 아까 오후에 하나 먹었는데
-
팔로잉 목록에 왜 안보이지
-
2차 얼버잠 2
이젠 진짜 ㅃㅃ
-
제대학전부주작이에요
-
키빼몸 4
???
-
공대기준 최소학점만 박고 1학기 다닌다고 치면 복학했을때 타격 큼?
-
근데 좋은 대학 다니는 사람한테는 좋은 인식이 심어지지 않나요 9
좋은대학 나왔으면 일단 첫인상부터가 좋음
-
뭔말인진 알겠는데 시험장에서 너무 급해 고치고싶다
-
수능 잘 보는법 4
저도 잘 본적 없어서 몰라요
-
이거 다 받고 공부하고 잘래
-
으하하
-
인증해주세요 7
-
수강신청 타임어택 안해도되나요?
-
귀가 ㅇㅈ 2
사실 아까 퇴근하면서 찍었어요
-
달리 말할 곳이 없어서 여기에라도 써요.. 말투 ㅈㅅ. 나는 여자고 우울증이 안...
-
오르비언들 재수하는거 다 잘하고 대학생활 잘하고 수능도 잘보자
-
본인 ㅈ반고임 3
국어 모고 내가 거의 맨날 반 1등이엿음
예?
일차방정식 ㄷㄷ