잉여역수 활용
게시글 주소: 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
진짜 와다 와
-
내에플팬슬 이거20만원짜린데 후
-
화2 전국 1등급 수 =253 기숙은 몰루?
-
과고 입시 5
무물받는다
-
라면 요즘엔 4
진매보다 열라면이 더 맛있는 듯
-
범죄도시에서 장췐옆에 빡빡이 닮앗대
-
뒤지겠네 ㅅㅂ 나랑 말동무 좀 해줘
-
오렌지주스랑 먹는게맛잇다
-
1. 나는 평생동안(초등학생~현재) 연애를 해 본 적이 없다 2. 나는 한 번도...
-
특히 좋아하는 메뉴 나오면 막 두세번씩 먹음 단체급식 느낌의 약간 B급 요리들...
-
님들 나 순결임 6
순결지키기 ㅈㄴ 쉽네 본인은 심지어 연애관련도 순결임 레굴루스가 좋아하겠노 ㅋㅋㅋㅋㅋ
-
비슷한가요?
-
반갑습니다 8
-
말하면 이미지타격이 상당해서 안할래
-
마음같아선 다 보고 싶은데 시간이 너무 아까움… 3-4따리라면 다 보는 게 맞나.?
-
풀이 까지는 아니더라도 사고과정 알려주면 5000덕 12
수학황들의 사고과정을 앞으로 덕코로 사겠음
-
흐음
-
프본이에요 8
반가워요
예?
일차방정식 ㄷㄷ