"10k+1 꼴의 소수는 무한히 많다"의 두 판 사이의 차이
Pythagoras0 (토론 | 기여) |
Pythagoras0 (토론 | 기여) |
||
| 1번째 줄: | 1번째 줄: | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
==개요== | ==개요== | ||
| 15번째 줄: | 7번째 줄: | ||
| − | + | ==증명== | |
| − | + | ;보조정리 | |
| − | == | ||
| − | |||
p는 홀수인 소수이다. <math>n^{p-1} + n^{p-2} +\cdots + 1</math> 의 소인수 중 p 가 아닌 것은 <math>2kp + 1</math> 꼴임을 보여라. | p는 홀수인 소수이다. <math>n^{p-1} + n^{p-2} +\cdots + 1</math> 의 소인수 중 p 가 아닌 것은 <math>2kp + 1</math> 꼴임을 보여라. | ||
| − | |||
| − | + | ;증명 | |
<math>p\neq q</math>인 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>의 소인수라 하자. | ||
| 43번째 줄: | 32번째 줄: | ||
그러므로 q는 <math>2kp + 1</math> 꼴이다. ■ | 그러므로 q는 <math>2kp + 1</math> 꼴이다. ■ | ||
| − | |||
| − | |||
| − | |||
| − | |||
| + | ;정리 | ||
10k+1 꼴의 소수는 무한히 많다. | 10k+1 꼴의 소수는 무한히 많다. | ||
| − | |||
| − | + | ;증명 | |
10k+1 꼴의 소수가 유한하다고 가정하고 그 집합을 <math>\{q_1,q_2,\cdots,q_r\}</math> 이라 하자. | 10k+1 꼴의 소수가 유한하다고 가정하고 그 집합을 <math>\{q_1,q_2,\cdots,q_r\}</math> 이라 하자. | ||
| 86번째 줄: | 71번째 줄: | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| 110번째 줄: | 85번째 줄: | ||
* [[등차수열의 소수분포에 관한 디리클레 정리]] | * [[등차수열의 소수분포에 관한 디리클레 정리]] | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
[[분류:소수]] | [[분류:소수]] | ||
2014년 6월 16일 (월) 05:24 판
개요
- 초등정수론을 통한 10k+1 꼴의 소수의 무한성 증명
- 똑같은 증명을 2pk+1 (p : 소수) 꼴의 소수의 무한성을 보이는데 사용할 수 있다.
- 더 일반적으로 등차수열의 소수분포에 관한 디리클레 정리 가 성립한다
증명
- 보조정리
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 \equiv 1 \pmod p\) 임을 보이자.
\(n\equiv 1 \pmod q\)이면, \(n^{p-1} + n^{p-2} +\cdots + 1\equiv p \pmod q\) 이므로, q는 \(n^{p-1} + n^{p-2} +\cdots + 1\) 약수일 수 없다. (\(p\neq q\)이므로)
\(n\not\equiv 1 \pmod q\)이라 하자. 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가 가장 작은 수이다. 따라서 오일러의 정리에 의해 p는 q-1을 나눈다.
따라서 \(q \equiv 1 \pmod p\).
그러므로 q는 \(2kp + 1\) 꼴이다. ■
- 정리
10k+1 꼴의 소수는 무한히 많다.
- 증명
10k+1 꼴의 소수가 유한하다고 가정하고 그 집합을 \(\{q_1,q_2,\cdots,q_r\}\) 이라 하자.
\(p=5\), \(n=q_1q_2\cdots q_r\)로 두고, \(n^{p-1} + n^{p-2} +\cdots + 1>5\)을 생각하면, \(n^{p-1} + n^{p-2} +\cdots + 1\)는 각 \(q_i\)로 나눈 나머지가 1이다.
보조정리에 의해 \(n^{p-1} + n^{p-2} +\cdots + 1\)는 \(q_1,q_2,\cdots,q_r\) 가 아닌 10k+1 꼴의 소인수를 가진다.
이는 10k+1 꼴의 소수의 집합이 \(\{q_1,q_2,\cdots,q_r\}\)라는 사실에 모순이다. ■
재미있는 사실
- 2010년 3월 KAIST 정수론 개론 시험 문제로 출제되었다
실험
- p=5인 경우
- 아래는 각각 {n, \(s=\sum_{k=0}^{p-1}n^{k}\), s의 약수}를 나타낸다.
1 5 {1,5}
2 31 {1,31}
3 121 {1,11,121}
4 341 {1,11,31,341}
5 781 {1,11,71,781}
6 1555 {1,5,311,1555}
7 2801 {1,2801}
8 4681 {1,31,151,4681}
9 7381 {1,11,61,121,671,7381}
10 11111 {1,41,271,11111}
11 16105 {1,5,3221,16105}
12 22621 {1,22621}
13 30941 {1,30941}
14 41371 {1,11,3761,41371}
15 54241 {1,11,4931,54241}
16 69905 {1,5,11,31,41,55,155,205,341,451,1271,1705,2255,6355,13981,69905}
17 88741 {1,88741}
18 111151 {1,41,2711,111151}
19 137561 {1,151,911,137561}
20 168421 {1,11,61,251,671,2761,15311,168421}
메모