잉여역수 활용
게시글 주소: 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를 선물하세요.
-
술 존나 처마시고 그 다음날에도 처 마시니까 평소 주량보다 덜 먹었는데 취함 그래서...
-
시대 다닌 뒤로 꼬질함이 사라지지가 않음 잘 씻고 꾸며도 꼬질꼬질함 묘하게
-
모두 다 1을 맞아봤습니다 근데수능은시발
-
스타팅 블록 2
스타팅 블록(Starting Block) '시작을 막는다' 김범준 스블 아이디어...
-
수1 수2는 머리 깨지면서 김범준스블 듣고 있는데 스블 미적은 많이 어렵다는...
-
평가원 #~#
-
퇴근까지 3시간 2
-
키야
-
취침 1
-
맛있는건~ 1
정말 참을 수 없어어~
-
대성에서 김범준t랑 스타일 젤 비슷한 강사분이 누구인가요? 2
김범준 풀커리 가려고 했는데고지금부터 밀리는거 보고 스블이랑 기출분석 다 하려면...
-
윤석열 윤석열 하고 소리지르는데 ㅅㅂ 이거 맞냐
-
눈물나올고 같아ㅏ ㅠㅠ
-
너무 좋다
-
로또야 되면 그만이지만 대학은 붙었다고 끝이 아닌데 아직 시작도 안 했는데
-
발행일보다 빨리 받기 ~
-
콩진호 콩진호
-
무료궁합인가 사주궁합 보고왔는데.. 나 결혼 늦게하는게 좋은 팔자라던데.. 약간...
-
우리 동네는 쫀득쿠키 100g 9000원대인데 여친 동네는 쫀득쿠키 130g...
-
미치겠네
예?
일차방정식 ㄷㄷ