[중고딩문제] (개쉬움)정수론 증명 질문좀

[익명(223.38)]

서로소인 p q에 대해

q로 나눈 나머지가 1이되는 p^n이 반드시 존재한다

이거 증명을 하긴했는데

좀 더 직관적인 증명이 있을까요??

- dc official App

[익명(223.38)]

https://m.dcinside.com/board/mathematics/395864
이런식으로 증명하긴했는데 직관적이지 않음 - dc App

[익명(119.206)]

잘 증명하신 것 같은데요? 뭐가 직관적인지는 모르겠지만, 보통 i*p= q*Q+r(Q는 몫 r은 나머지) for i=1,2,..,q-1로 할때 gcd(p,q)=1이면 r={1,..,q-1} for i=1...,q-1이 나오는데 여기서 1이상 q이하인 수중에서 q와 서로소인 수를 i에 집어 넣으면 이때 나오는 r(나머지)의 집합도 q와 서로소인 수가 됩니다.

[익명(119.206)]

(1*p)x...x(i*p)x...((q-1)*p)=(qQ_1+r_1)x...x(qQ_(q-1)+r_(q-1))가 되는데 이식을 정리하면{1*..i...*(q-1)}(p^psi(q)-1)=q*Q s.t i는 q와 서로소, qsi(q)는 q와 서로소가 되는 수의 개수(Q는 q로 나누어진다는 것을 표하기 위해 그냥썻습니다.) q는 i를 못나눔으로 p^psi(q)-1/q가 됩니다. n=psi(q)가 p^n을 q로 나누었을 때 나머지가 1이되는 값입니다. fermat 정리인가? 구글에 이름 치면 나옵니다.

[수갤러 1(118.235)]

저는 비둘기집 원리를 써봐도 좋을거같아요1. 함수를 다음과 같이 정의합니다. f:{p^n|n은 자연수}->{0,1,2,…,q-1} given by f(p^n)=p^n (mod q)2. 그럼 정의역이 공역보다 갯수가 훨씬 더 많기 때문에 이 함수는 자명하게 one to one이 아닙니다.3. 따라서 Pigeonhole principle에 의해서 서로 다른 자연수 n<m이 존재해서 p^n=p^m (mod q) 즉, 나머지가 같습니다. 4. 그러면 p^m-p^n=p^n{p^(m-n)-1}은 q로 나누어 떨어집니다. 즉, q의 배수예요.5. p, q는 서로소니까 q는 p^(m-n)-1을 나눌 수 밖에 없고 이때의 m-n이 올려주신 명제에 해당하는 자연수에 해당하게 됩니다. - dc App

[수갤러 1(118.235)]

아 이미 비둘기 쓰셨네요…헿 - dc App