잉여역수 활용
게시글 주소: 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를 선물하세요.
-
디자인 자체가 아줌마 아저씨만 입게 생기지 않음?? 캐나다구스도 ㅇㅇ
-
한양대가 냥대인 이유 13
.
-
왜 다들 100 넘냐
-
잇올 지금 교실로 관리자한테 말하고 들어갈수있나요? 1
레전드 늦잠자서 지금 들어가는데 책이 다 자리에 있어요 원래 안되는거 알긴 한데..
-
보통 스트레이트는 아니고 자기 일하거나 학교 다니다 간 거 4수 한의(스트레이트)...
-
.
-
옯스타맞팔하실분 20
자자 날이면 날마다 안옵니다 @D2plexion
-
오점뼈 1
오늘 점심 뼈해장국이라는 뜻
-
왜 4등급임? 에이씨
-
어떤 이미지든 환영이야
-
선택과목 고민하는데 이유가 “나중에 메디컬 성적 되면 디메리트 있나.”인게 걍...
-
생각ㅇ이많아짐 사문풀때도 시간때문에 허덕이는데..... 수학에 한바가지...
-
출석부! 출석부 출석부! 지하철! 지하철 지하철! 공산당! 공산당 공산당! 진짜...
-
공군 질받 9
암거나 ㄱㄱ
-
이시간에
-
성대바꿔
-
서바전국이랑 작년 5모빼고는 시간 다 널널하게 시간남았었음 이제야 경제 들어간...
-
ㅇㅈ 18
은 술먹고 비번 틀렸던 거라는 거.
-
학벌딸 치고 싶어서 인거 같음 그냥 병신 한남 자존감 밑바닥 루저새끼라 뭐라도 하나...
-
가산점 이도저도 아니게 쳐받고 따지고 보면 불이익만 있네
예?
일차방정식 ㄷㄷ