잉여역수 활용
게시글 주소: 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를 선물하세요.
-
불안 + 원래 수전증이 너무 심해서내내 달달달달 떨음 ..ADHD까지 겹쳐서...
-
이제생각하면 노뱃이 좋은듯 2 1
나의 대학을 함부로 특정할수 없는거자나 알고보면 내가 지방4년제일수도 현역설의...
-
ㅅㅂ잇올기숙 들어갓는데 다 새기분하는데 나만 이제 강기분 시작이야 5 1
현타 좆되고케왤케 늦개시작햇나싶다
-
강원 정선 산불 발생 어제 오후 강원도 정선군에서 산불이 발생하여 이틀째 진화...
-
. 0 0
.
-
수분감 다음 2 0
뉴런 하는게 정베인가요? 스텝1까지만 다품
-
드뎌퇴근~ 3 1
또 이렇게 한주를 무사히 클리어~~~
-
학교다니면서정시도성공한정파라면7ㅐ추 11 4
-
님들 돈 없는데어떻게해요 1 1
ㅜㅠㅠㅠㅠㅠㅠ
-
사탐 의대 결정 좀ㅇㅇ 4 0
현역은 실패하고… 재수하면서 사탐의 가고 싶은데, 사람들마다 말이 달라서ㅇㅇ 나는...
-
사실 내가 수학못하는거맞음 20문제주고 40분주는데 4개못풀엇다 진짜 폐급 다됐구나
-
15살 카의는 뭐냐 ㅅㅂ 0 0
보법이 다르네
-
사망직전 2 1
-
우옹애 0 0
-
맛있는거 먹고 싶다 12 0
근데 뭐가 맛있는지 모르겠어
-
강의평가 보는법 0 0
학교 변경하려고 에타 탈퇴후 재가입 반복했더니 한달 정지돼버림… 에타 말고는...
-
약대 고경제 9 0
고경제 와 제주약대 면 어디로 선택하시나요
-
뉴런을 하고있는데요... 2 0
제가 뉴런 내용을 확실하게 체화 하고있는지 알고싶습니다. 혹시 방법이 있을까요
-
문디컬 틀딱 ㄱ과목선택 도움 12 0
문디컬 목표로 수능 다시볼건데 2등급 중반 / 100 / 1 / 50/ 50...
-
애니 프사얘들아 8 0
너네들 혹시 애니? 푸하하하하 ㅋㅋㅋㅋㅋㅋ
예?
일차방정식 ㄷㄷ