잉여역수 활용
게시글 주소: 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등급 이상들은 거의 다 맞는 문제인건가요 수학입니다
-
나도 이제는 뒷방늙은이 신세로구나....
-
현우진T가 그때도 강사하려나 5년뒤 뉴런이 궁금해짐 확통은 얼마나 괴랄하려나
-
돈지랄ㅁㅌㅊ 5
깊콘 소비해야하는데 커피는 못먹고 단건 혈당이슈생겨서 메가에서 빵쳐먹음ㅠㅠ
-
운동하니까 3
2kg 빠졌음뇨 헤헤
-
25수능 기준임 언매 97점 미적 100점 사문 50점 지1 50점 이게 연대...
-
님들 경제하지 마셈 11
홍보하고 다닌게 님 같은 사람들 오라고 한게 아님
-
닉 뭐로 바꾸지 6
-
아 1
저축했더니 통장에 돈이 22457원밖에없어 이걸로 3일살아야돼 미치겠네
-
모순과 거짓이 동치 무모순과 참이 동치 이렇게 말하면 사람이나 ai나 전부 틀렸다고...
-
호림원 상병님께.. 39
Agent K 입니다. 메인에 올라온 호림원 상병님의 검정고시 관련 글을 보고 글을...
-
좋아요 80개도 받아보네
-
만약에 학교를 안가는걸로 결정나면 1학기는 휴학이 불가함에도 수업거부를 하는거니까...
-
좋지 않네
-
지금 일어났네 0
으아아아
-
??
-
메가환급 0
가채점이야 뭐 지금이라도 하면 되는데 모의지원 못한건 어떻게든 만회못하겠죠?
-
그러면 미련없이 죽을텐데
예?
일차방정식 ㄷㄷ