잉여역수 활용
게시글 주소: 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를 선물하세요.
-
올해는 team 06의 시대다
-
무수한 오르비 뱃지단들의 습격이..
-
인터넷에 검색해봐도 정보가 없거나 인터넷에 오개념이 널려있는경우엔 지피티도...
-
아이스크림 사먹으러 가기
-
ㅠㅠ
-
자율전공인데 성적제한이 있음 그레서 내가 1지망으로 원하는 학과에 들어갈수 있을지...
-
이해가안가네 진짜
-
피뎁 2
피뎁 프린트x,패스트x 이런데다 메일 보내서 제본받으면 잡혀가나요…다들 어디서 제본하는거?
-
이해원은 ㅈㄴ 싫어하시더라 한완수랑 해모 ㅈㄴ 까셨는데 기억에남네요
-
학원 하나 없는 곳서… 11년간 ‘섬마을 선생님’ 돼준 한의대생 14
경희대 한의대 졸업 한진석씨 등 완도군 ‘생일도’서 특별 감사장 전남 완도군에 있는...
-
[고려대학교 25학번 합격] 합격자를 위한 고려대 25 단톡방을 소개합니다. 0
고려대 25학번 합격자를 위한 고려대 클루x노크 오픈채팅방을 소개합니다. 24학번...
-
이해가안됨
-
"대학 절반만 갈래?"
-
무단결석,지각 100회 생기부에 안좋은말 적혀있고 13
내신6등급? 수행평가 다 준비안했는데 서연고 정시할때 많이 불리할까요? 수능...
-
댓글 달면 차단목록에 있는 회원입니다 이것도 안보고싶은데
-
일하기 싫어.. 5
예?
일차방정식 ㄷㄷ