편집을 취소할 수 있습니다. 이 편집을 되돌리려면 아래의 바뀐 내용을 확인한 후 게시해주세요.
최신판 | 당신의 편집 | ||
13번째 줄: | 13번째 줄: | ||
'''만일 GCD(a,n)=1이면, |x|<√n, |y|<√n과 ax≡y (mod n)을 만족하는 x, y가 존재한다.''' | '''만일 GCD(a,n)=1이면, |x|<√n, |y|<√n과 ax≡y (mod n)을 만족하는 x, y가 존재한다.''' | ||
우선 법 n에 대해 집합 {ax-y| 0≤x≤√n, 0≤y≤√n}를 생각한다. 그러면 이 집합의 원소의 개수는 최소 <math>(\ | 우선 법 n에 대해 집합 {ax-y| 0≤x≤√n, 0≤y≤√n}를 생각한다. 그러면 이 집합의 원소의 개수는 최소 <math>(\sqrt{\lfloor n \rfloor} +1)^2 </math>개가 된다. 분명히 법 n은 n개의 합동이 아닌 원소를 포함하고 있고, <math>(\sqrt{\lfloor n \rfloor} +1)^2 > n</math>이므로 [[비둘기집의 원리]]에 의해서 ax<sub>0</sub>-y<sub>0</sub>=ax<sub>1</sub>-y<sub>1</sub>를 만족하는 x<sub>0</sub>, x<sub>1</sub>, y<sub>0</sub>, y<sub>1</sub>가 존재한다. 따라서 a(x<sub>0</sub>-x<sub>1</sub>)=y<sub>0</sub>-y<sub>1</sub>가 되고, x<sub>0</sub>-x<sub>1</sub> , y<sub>0</sub>-y<sub>1</sub>의 절댓값은 √n보다 작게 된다. | ||
=== 정리의 증명 === | === 정리의 증명 === |