잉여역수 활용
게시글 주소: 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를 선물하세요.
-
공식에서 이런게 나오네
-
금살껄 4
라고할때살껄
-
BB가 AA에 밀려 떨어지는 경우도 있겠지?
-
출하싫 3
날씨 호달달
-
잘자용 16
배가 고파져서 블아 ost 158번 그레고리오 피아노 버전을 들으면서 이만 자야겠오요
-
침대에서 자면서 망상함
-
나 심심한 때 18
자꾸 내 게시글 와서 님 개구리 맞죠? ㅇㅈㄹ하는 애가 잇엇음 그래서 뉴비엿던 내가...
-
ㅠㅠ ㅠㅠ ㅠㅠ 김민정 나의 썩은 장기라도 가져가
-
어디까지라고봄? 집은 경상도 어딘가.. 그냥건동홍가서새벽에서울가는데욕심인가싶어서써봄..
-
지금 시대인재 라이브 수강신청해서 들을 수 있나요.?
-
그토록 간절하던 한양대 낮공을 수학3점실수하나땜에 못가서 대학원이라도 꼭 한양대로 가야겠음
-
화학 어렵다 2
어제 밤에 연등하면서 넋이 나가버림 ㅋㅋㅋ
-
ㅇㅈ 13
새벽이니까 다행일듯 내 손임 펑~~
-
25수능후기 17
6평 성적 화미영 세지/지1 24324 9평 성적 언미영 세지/지1 12214 수능...
-
남 안 될 거라 단정하고 처 말하는 심보가 대체 뭐임 정 존나 떨어지게 시발
-
나 가채점을 안해서 원점수를 알고 싶은데 국수탐 백분위별 원점수 표 갖고있는 사람있음???
-
-
발 300 11
손도 많이 큼
-
얼버기 1
어제 깜빡 잠들었네... ㅇㅈ메타 돌았었나
-
디자인 자체가 아줌마 아저씨만 입게 생기지 않음?? 캐나다구스도 ㅇㅇ
예?
일차방정식 ㄷㄷ