잉여역수 활용
게시글 주소: 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를 선물하세요.
-
아으 무서운 사람들
-
어케되는거임?
-
언어이해 3
이건 뭐 언어 읽고 잘 이해하는 거겟지 이건 어느정도 잘 나오려나 지각추론 이게 먼...
-
이유는 요새 오르비 자주 안 들어와서 누구 이미지 써주거나 내 이미지를 물을 그런게...
-
학교 선배한테 연락옴요…. 다들 새터오티 안가도 아무도 존재모른다고해서 걍 안갔는데...
-
갱상도 남자처럼 살짝 무뚝뚝함 그렇지만 사투리 때문에 애교가 많아보임 나한테 싫은...
-
맞팔해요 4
잡담태그 잘달아오
-
저렇게 공부대비 효율 잘 나오는 과목은 그래도 모든 탐구중에는 경제밖에 없으니까...
-
안녕하세요 5
레전드 굇수입니다 내일 보죠
-
좀 부담스러울 거 같은데 별 의미 없이 그냥 붙여서 보내는 거라면 감정표현을 너무...
-
수능 만점 가능한가
-
ㅇㅈ 6
대신 시라이시 안을 드립니다
-
프사변경완료 5
다시 민지단 복귀
-
수시러 최저 맞추는 친구가 과탐하다 사문 듣는데 ㄹㅇ 그냥 재밌는 유튜브보는느낌?...
-
3차긴한데 mri까지 찍었는데 다른 개인병원에서는 만져보고 바로 뭔지 알더라.....
-
고1때 두명 썸탔고 한명은 학기초에 소개받았었는데 연락을 서로 먼저안해서 자연스럽게...
-
인생날로먹고싶다 4
의대생 하나 꼬셔야지 ㅇ.ㅇ.. 집안일 공부할게
-
옯스타 맞팔 4
안하실분
-
이러면 누가함 ㅋㅋ
-
애들아 4
울지마
예?
일차방정식 ㄷㄷ