잉여역수 활용
게시글 주소: 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를 선물하세요.
-
이거만큼 직관적으로 이미지 심어주는 프사 없음
-
이게 쇼츠로 밈같은거 대충 볼때는 으음 그렇구나 하고 봣는데,가사 보면서 노래로...
-
어싸 + 브릿지 + 시중N제 다풀건데 작년실모같은거 구해다가 더풀필요없나요
-
으하하하
-
ㅈㄱㄴ 있나여?
-
성적ㅇㅈ 5
-
저도 듣고싶어요
-
방법이 궁금합니다.
-
으흐흐 6
흐흐흐흐
-
추가모집도 추합이 있는지 아니면 최초합밖에 없는지 궁금하네요..
-
솔직히 작년 6모 12번<< 양승진이 제일 잘풀어줌ㅇㅇ 9
미지수 3개 쓰면서 계산지옥 버틴 것도 아니구 실전 개념 쓴 것도 아니고 그냥 y축...
-
그때 우리 동아리 출신 충남대 수의대 선배가 왔음 근데 우리 동아리 나름 공부 잘...
-
상대학교로 가는 케이스도 있나 진짜??
-
그런 티 안 나게 돌려가며 기만하는 느낌을 내고 싶은데 뭘 해야할까
-
있나요? 이거 롤보다 더 암걸리는데
-
시대 재종 2
대치에서 목동관으로 옮길 수 있나요? 그냥 나갔다가 다시 목동으로 원서 넣으면...
-
잠이 안오는데 할 줄 아는게 국어밖에 없어서요
-
연대에 4
설대버리고 오는사람도 있나요?
-
흠.....아닌가? 아니다
-
심신미약 상태엿음 원래 딴 닉이엿는데 심신미약 상태가 안 됏다면 오르비 제대로...
예?
일차방정식 ㄷㄷ