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

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

2020년 12월 28일 (월) 02:47 기준 최신판

개요


증명

보조정리

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}




메모

관련된 항목들

원본 주소 "https://wiki.mathnt.net/index.php?title=10k%2B1_꼴의_소수는_무한히_많다&oldid=47779"