잉여역수 활용
게시글 주소: 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를 선물하세요.
-
심심한 4
좋은 닉네임임
-
형님이라고 부를까 생각중임
-
저는 남자로써 4
누구 한명 싫어도 비갤이 아닌 여기서 저격을 하고 잘풀리면 wwe 안풀려도 ufc를 열겠습니다 선서
-
어떤 사람이 닉 추천 글에 댓글로 자기 전 닉네임 추천함
-
? 5
-
ㅇㅈ시 추천댓글 11
ㄹㅈㄷㄱㅁ 이라고 치면됨
-
하..
-
생윤이랑 사문 ㅈ같은부분만 합쳐서 5배어렵게만든느낌임 물론생윤은하다가던지긴했음...
-
용기내서 그녀에게 데이트신청 해볼까
-
ㅇㅈ 11
ㅋㅋ
-
그래도 아직까진 한국사회에서 낫베드죠?
-
저희 학번에 02 남자분 계셨는디 같은 조였거든요??? 사람 너무 좋고 착하고...
-
개빡치네
-
ㅇㅈ 11
학원에 이거 가져가서 풀엇음
-
카이스트<—인정. 서울대 다음 포항공대<—연고라인 유니스트 지스트 <——중경외시...
-
조만간 책이라도 한 권 읽어야겠어요 지금은 너무 내 세상에 사로 잡혀버린 느낌...
-
아니 이게 진짠게 가끔가다가 화나서 이상한 욕할때있음 8
그래도 나랑 같이게임해줘서 다들 감사합니다.
-
안자는사람 7
다들뭐하고있나요?
-
확통담요단으로 전향하고 담요킹이 되겠어
-
고백하기가 어렵고 걔도 너무바빠서 받아줄지도 모르겠어서 막막함
예?
일차방정식 ㄷㄷ