잉여역수 활용
게시글 주소: 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
그냥 사귀는거 포기하게 너무 힘들다 나도
-
옯스타 팠다 9
hoohoh77 ㄱㄱ 친해지면 ㅇㅈ보내줌
-
300원~500원
-
투필수 해제되고 나서 투과목 망했다 이제 누가하냐 이랬는데 알고보니 역대급...
-
의미를 찾지 마시길 바랍니다
-
마스터 등반 시작
-
키작으면 좋은점 4
애들이 귀엽다고함 헤헤
-
마감전까지 이미지 써줌 13
ㅇㅇ
-
하루만 더 새자 7
이거 못 잘 거 같아. 극혐하는거 < 자려고 누워서 눈 감고 잇는데 정작 잠은 못...
-
애니프사 12
하는 이유가 뭔가요
-
과기원 라인 정리해줌 11
카이스트<—인정. 서울대 다음 포항공대<—연고라인 유니스트 지스트 <——중경외시...
-
미친 수강평 정상화좀 해봐 범바오야
-
…?
-
전독시 실사화되더라 11
유튜브에서 예고편봤는데 그거가 실사화가 가능한가 근데
-
어디가나요..?? 갑자기 그냥 궁금해져서..ㅎㅎ 14111..ㅋㅋㅋㅋ 약간 이런 더...
-
진짜 너무샌대
-
아 맨날 이래 ㅛㅂㅈㅐㅏㅎㄷㄱ푼ㅇㅊ
-
이미지 써드림 11
아이민이 7의 배수도 3의 배수도 아닌 옯붕이들에게만
-
예?
일차방정식 ㄷㄷ