잉여역수 활용
게시글 주소: 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를 선물하세요.
-
원래 단과 강사들 쉬는 시간에 질문 안받아주지 아늠? 5
남지현 이 쌤은 거의 쉬는 시간 10분 하면 7분은 질문받던데 이쌤이 특이한거냐?
-
무기한 휴르비 1
-
손잡아보고싶구나
-
그렇다고 방임은 아니시고 폰은 늦게 사주시는 등 주변 친구들이랑 대화하다 보면...
-
지인선 N제가 9번~15번 / 20~22번까지 다뤘으니 지인선 입문 n제가...
-
수면의 질이 나빠지겠죠?
-
노트가 왜 무성생식을함뇨 세포분열을막함
-
95 99 3 90 88 2 1 2 2 돈낭비다 vs 로또산다는마인드로 찔러본다...
-
학사 살 땐 2
옆방 부엉이 잠 깰 까봐 담요 위에 이불까지 쓰고 입 막고 울었었는데 추억이 되었군
-
기하충이라면 8
사각형 영어 정돈 알아야제
-
경제 vs 세지 3
목표는 만점 및 높은백분위와 표점
-
흑석반수생 2
갑자기 생각남
-
ㄹㅇ 쫌 치는데
-
몇일쯤인가요???
-
분명히 국어에 모든걸 걸어야하긴 하는데 이번주에 국어 20분했네
-
반수 4
현역 25학번이고 논술로 중대 상경 등록했는데 과 상관 없이 성대 가는게 목표였어서...
-
대단하다!
-
과외할 때 좋을 거 같은데
-
아 모르겠고 빨리 12화 내놔~~~~~~~!!!!!!!
-
잔다. 2
자라. 캬캬.
예?
일차방정식 ㄷㄷ