잉여역수 활용
게시글 주소: 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를 선물하세요.
-
고양이 물마실때 2 0
계속 혀 낼름낼름거리는거 개커엽네
-
배고픈데 2 0
3시간 뒤엔 저녁이어서 지금 먹을만한거 추천좀
-
심찬우 나형시험지 봤나 2 7
수학에 벽 느꼈다던데 나형에 벽까지 느낄정도면 지금 태어났으면 그냥 대학을 못갔을듯
-
근데 그냥 왜 정시에 내신반영 하는지 알거같음 4 10
저런사람 거르려고 하는거 아님? 고등학교에서 사회화 전혀 안된채로 수능을 다른...
-
부모님의 반대로 자신의 꿈을 포기하셨던분 계신가요 1 0
전 사격선수 하고 싶었는데, 가정을 부양해야할 의남자는 전문직이나 대기업 혹은 자기...
-
슬슬 버거워지는거 같기도 0 0
멍청한 내 머리가 싫다
-
난 매일매일 재밌었는데 힘들긴해도
-
안녕하세요 2 0
안녕히가세요
-
메가패스를 구매하지 않았아서 환급 못해준다네요 이게 말이 됩니까?
-
[유석재의 돌발史전] 서울과 도쿄의 시간이 같다... 이것도 ‘친일 잔재’인가 1 0
1896~1911, 1954~1961년의 시간은 지금보다 30분 느렸다 유석재의...
-
잇올기숙<< 한달 다니고 그만둘거임 ㅅㅂ 더해진거라곤 수면케어뿐인데 200이 더비싸 2 0
심지어 장학제도도 별로없고..통학 안한다는 장점과 수면케어 빼곤 뭐 없어 라면도...
-
온리 수의대 지망생 4수 시작 선택과목 조언 좀 ㅠㅠ 1 0
4수 할건데 사탐, 확통을 해도 되는건지 그냥 정석대로 미적, 과탐을 해야 하는지...
예?
일차방정식 ㄷㄷ