|
<ol>
<li> a와<math>a</math>와 서로소인 소수 p에<math>p</math>에 대해 <math>a, 2a, 3a, ..., (p-1)a인a</math>인 <math>p-1개의1</math>개의 수를 살펴보자. 이 수들을 p로<math>p</math>로 나눴을 때 나오는 [[나머지]]는 모두 다르다.
#* 증명 : [[귀류법]]으로, 서로 같은 나머지를 가진 두 수, ia와<math>ia</math>와 ja가<math>ja</math>가 있다고존재해서 그 나머지가 같다고 하자(<math>0 < i < j < p인p</math>인 정수). 그렇다면 이그 두 수의 차는 p로 나누어질 것이다. 두 수의 차는차 <math>(j-i)a이다a</math>는 <math>p</math>로 나누어질 것이다. 그러나 <math>0<j-i<p이므로p</math>이므로 <math>j-i는i</math>는 p의<math>p</math>의 배수가 아니며, 문제의 가정에 따라 a는<math>a</math>는 p와<math>p</math>와 서로소이다.
#* 따라서 같은 나머지를 가지는 수가 없으므로, <math>p-1개의1</math>개의 수는 모두 그 나머지가 다르다.
<li> 또 <math>0 < i < p인p</math>인 i에<math>i</math>에 대해 <math>ia</math> 역시 p의<math>p</math>의 배수가 아니다. 이에 대한 증명은 위와 같으므로 생략한다.
<li> 이제 [[집합]]
:<math>A = \left\{x|x = ia,\;i\in\{1,\dots,p-1\} B\right\}</math>
를 정의하자. 이는 첫 번째에 가정한 <math>p-1개의1</math>개의 수들의 집합이다. 또한,여기서 집합
:<math>B = \{1,2,\dots,p-1\}</math>
를 보자. 이는인데, p와<math>p</math>와 서로소인 수를 p로<math>p</math>로 나눌 때 생기는 모든 나머지들의 집합이다. 처음에 했던 증명에 의해, A와<math>A</math>와 <math>B</math>의 B의[[기수 크기는(수학)|크기]]는 같다.
<li> 따라서,
| 