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

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

(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\neq q\)p는 소수이므로 \(n^k\equiv 1 \pmod q\) 을 만족시키는 k 중에서 가장 작고, 오일러의 정리에 의해, p는 q-1을 나눈다.

따라서 \(q \equiv 1 \pmod p\)

그러므로 q는 \(2kp + 1\) 꼴이다. ■

(정리)

10k+1 꼴의 소수가 무한하다.

(증명)

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