잉여역수 활용
게시글 주소: 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를 선물하세요.
-
아 모르겠고 빨리 12화 내놔~~~~~~~!!!!!!!
-
잔다. 2
자라. 캬캬.
-
뭐지이건 3
-
운동 하루에 30분 러닝이라도 뛰셈 생각보다 몸이 많이 안좋아지더라 건강이 최우선임
-
작수 국어 1등급(언매 93점)이었는데 그냥 기출분석하고 사설 모고 풀면서 국어...
-
남들과 다른 길을 걷는다
-
에혀 그래도 적자는 아님 흐흐
-
정상인이구나 헤헤헤헤 나처럼 이벤트는 관심끄고 오시캐릭 1명만 정해서 그것만...
-
https://orbi.kr/00071915064 캬루형아 너무 잘만든거가타
-
영어 5등급 노베인데 단어는 꾸준히 하고있고 인강을 들으려는데 듣기vs독해 뭘 먼저...
-
행복한 새르비 되십셔!
-
오늘 5
술마셔서 기분 개좋음 ㅎㅎㅎㅎㅎㅎㅎ
-
-
근데 계속 홍뱃 쓸 예정
-
D
-
치뱃 너무이쁘다 진짜
-
-
통상인데 일러보고 대가리 깨져서 천장 박았는데 끝까지 미즈키 못 뽑음
-
왜냐면 이제부터 기다림이 24시간이 넘을 때마다대가리를 존나 쎄게 쳐서 제 머릿속을...
-
미적 n축 2
쓰는 어려운 문제 하나 만들어야하는데 241128과 결합시켜야하나 아이디어가 안떠오름
예?
일차방정식 ㄷㄷ