잉여역수 활용
게시글 주소: 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를 선물하세요.
-
대학커뮤니티 노크에서 선발한 홍익대 선배가 오르비에 있는 예비 홍익대생, 홍익대...
-
영어기출 0
지금 이명학 알고리즘 듣고있는데 기출을 병행하는 게 좋을까요 알고리즘 다 끝내고...
-
전 174정도인데 이거 어느정도임?
-
현우진T가 그때도 강사하려나 5년뒤 뉴런이 궁금해짐 확통은 얼마나 괴랄하려나
-
-
못듣나요?
-
본인 과고나와서 5
솔직히 카이스트나 포공이나 천재들은 아니고 그냥 꿀빤애들같은데 서울대<— 여긴 그냥...
-
나 가채점을 안해서 원점수를 알고 싶은데 국수탐 백분위별 원점수 표 갖고있는 사람있음???
-
얼버기 1
어제 깜빡 잠들었네... ㅇㅈ메타 돌았었나
-
원래 작년처럼 교재로 독학조질랬는데 강의 어케할지 ㄹㅇ궁금해서 일단해봄,,
-
사탐 메디컬 4
언미생1지1에 지방의/약 지망이고 개념 다 안돌린 생명 빼고 다 1뜨는데 사탐으로...
-
감동적 실화..
-
아침과외 6
공기가 차갑네요
-
디자인 자체가 아줌마 아저씨만 입게 생기지 않음?? 캐나다구스도 ㅇㅇ
-
어디감?
-
베르테르 72번 2
호에
-
닉 바꿈요 6
.
-
묵묵히 삼수
-
얼버기 12
다시 잠들수도..
-
중국 우한에서 새 박쥐 코로나 바이러스 발견... 인간 감염 가능 6
박쥐에서 인간에게 감염될 수 있는새로운 코로나 바이러스를 중국 연구팀이 우한에서...
-
[성적 인증] https://orbi.kr/00071836019 [칼럼글 모음]...
-
상식적으로 말도 안 통하는 나라에 와서 돈 받고 팔려가듯이 결혼하려는 사람 중에...
-
전문직들이 뽑은 전문직 수입 순위 # 동일티어내 앞일수록 평균수입 높음 1티어:...
-
잇올 지금 교실로 관리자한테 말하고 들어갈수있나요? 1
레전드 늦잠자서 지금 들어가는데 책이 다 자리에 있어요 원래 안되는거 알긴 한데..
-
화작 언매 고민 0
작년에 9모까지 언매 공부하다가 9모때 언매 3개틀리고나서 수능때 화작으로...
-
팀 07 파이팅
-
안녕하세요 반수생이고 작년 수능 안 보고 재작년에 화학 2등급 떴습니다 현역 때도...
-
나 변비인듯ㅠㅠ 2
왜그러냐 그래서 항문도 ㅈㄴ아픔 어제 피도 ㅈㄴ묻어나오더라 항문이 아파서 그런지...
-
한양대 빵 질문 0
한양대 낮공말고 중간공이상중에 빵난경우 몇점까지 뚫렷나요?
-
얼버기 2
한시간만 다시 자야지
-
남편 살해한 40대 베트남인 징역 3년…"심신미약 상태서 범행" 3
(수원=연합뉴스) 이영주 기자 = 가족을 살뜰히 보살핀 50대 남편을 흉기로 찔러...
-
뭐든지 과유불급이군
-
오점뼈 1
오늘 점심 뼈해장국이라는 뜻
-
하 #~# 0
어제 겜 할일 안 하고 잠들어서 조졌네 이번달은 할일 밀리면 안 됐는데
-
ㅇㅅㅇ
-
지급 준비 제도 등 - 수특 독서 적용편 주제 통합 09 0
안녕하세요, 디시 수갤·빡갤 등지에서 활동하는 무명의 국어 강사입니다. 오늘은 올해...
-
15세 ‘최연소’ 의대생 탄생…명문 의과대 복수 합격 10
"스스로 생각하고 찾아보면서 학습…의과학자 되고파" 15세 소년이 복수의 서울 소재...
-
멍청한 내 머리가 싫다
-
배고프당 0
-
재종 악몽 꿈 1
불켜놓고 자면 높은 확률로 악몽 꾸는 듯 대충 내용은 어느날 재종을 안 가고 집에서...
-
육군이면 집앞으로 갈 방법은 없죠...? 연고지복무병 모집 대상지역은 아니던데,,,
-
온리 수의대 지망생 4수 시작 선택과목 조언 좀 ㅠㅠ 0
4수 할건데 사탐, 확통을 해도 되는건지 그냥 정석대로 미적, 과탐을 해야 하는지...
-
예?
-
-
조금 외로운가 0
벌써 외롭다고
-
안녕하세요 '지구과학 최단기간 고정 1등급만들기' 저자 발로탱이입니다. 지난 1년간...
-
ㅠㅠ ㅠㅠ ㅠㅠ 김민정 나의 썩은 장기라도 가져가
-
술다깼당 0
구마완료
-
힘내라 샤미코
-
지금 시대인재 라이브 수강신청해서 들을 수 있나요.?
예?
일차방정식 ㄷㄷ