"10k+1 꼴의 소수는 무한히 많다"의 두 판 사이의 차이

2010년 3월 23일 (화) 18:38 판

(a) p: odd prime. n^(p-1) + n^(p-2) + … + 1 의 소인수 중 p 가 아닌 것은 2kp + 1 꼴임을 보여라. (b) 10k+1 꼴의 소수가 무한함을 보여라.

보조정리

p는 홀수인 소수. \(n^{p-1} + n^{p-2} +\cdots + 1\) 의 소인수 중 p 가 아닌 것은 \(2kp + 1\) 꼴임을 보여라.

(증명)

\(p\neq q\)인 q가 \(n^{p-1} + n^{p-2} +\cdots + 1\)의 소인수라 하자.

\(n^{p-1} + n^{p-2} +\cdots + 1\equiv (p-1)n+1 \pmod 2\) 이므로, \(n^{p-1} + n^{p-2} +\cdots + 1\)는 언제나 홀수이다. 따라서 \(q \equiv 1 \pmod 2\).

한편, q는 \((n^{p-1} + n^{p-2} +\cdots + 1)(n-1)=n^p-1\)의 약수이다.

따라서 \(n^p-1\equiv 0 \pmod q\)이고, p는 소수이므로 \(n^k\equiv 1 \pmod q\) 을 만족시키는 k 중에서 가장 작다.

오일러의 정리에 의해, p는 q-1을 나눈다.

@@ 21번째 줄: / 21번째 줄: @@
 (증명)
-q가 <math>n^{p-1} + n^{p-2} +\cdots + 1</math>의 소인수라 하자.
+<math>p\neq q</math>인 q가 <math>n^{p-1} + n^{p-2} +\cdots + 1</math>의 소인수라 하자.
-<math>n^{p-1} + n^{p-2} +\cdots + 1\equiv (p-1)n+1 \pmod 2</math> 이므로, <math>n^{p-1} + n^{p-2} +\cdots + 1</math>는 언제나 짝수이다. 따라서 <math>q \equiv 1 \pmod 2</math>.
+<math>n^{p-1} + n^{p-2} +\cdots + 1\equiv (p-1)n+1 \pmod 2</math> 이므로, <math>n^{p-1} + n^{p-2} +\cdots + 1</math>는 언제나 홀수이다. 따라서 <math>q \equiv 1 \pmod 2</math>.
 한편, q는 <math>(n^{p-1} + n^{p-2} +\cdots + 1)(n-1)=n^p-1</math>의 약수이다.
-<math>n^p-1</math>
+따라서 <math>n^p-1\equiv 0 \pmod q</math>이고, p는 소수이므로 <math>n^k\equiv 1 \pmod q</math> 을 만족시키는 k 중에서 가장 작다.
+오일러의 정리에 의해, p는 q-1을 나눈다.