정수론 #5-3 :: 메르센 소수와 완전수

Twin Prime Conjecture

• 2만큼 차이나는 소수 쌍은 무한할까?
  ex) (3, 5), (5, 7), (11, 13), …
• Primes are randomly distributed
  소수는 규칙성이 없다. ⇒ 증명 안됨.

 

---

 

Mersenne Prime

$\begin{gather*}2^p-1 \end{gather*}$

 

위와 같은 소수를 메르센 소수라고 한다.

ex)
2^2 - 1 = 3
2^3 - 1 = 7
…

2^11 - 1 = 2047 = 23 * 89

⇒ 2^p - 1이 항상 소수가 되는 것은 아님.

• Are there infinitely many mersenne prime? : 증명 안됨.

 

---

 

Euclid’s perfect number formula

만약 2^p - 1이 메르센 소수라면

 

$\begin{gather*}N=2^{p-1}(2^p-1) \end{gather*}$

 

위는 완전수(perfect number)이다.

 

완전수

$\begin{gather*}N = \sum_{d|N \ \ \ \ 1\le d< N}d \end{gather*}$

N의 약수중에서 자기 자신 N을 제외한 애들을 전부 더한 것이 N과 같으면 완전수.

 

---

 

증명

$\begin{gather*}q=2^p-1 : prime \end{gather*}$

 

$\begin{gather*}N=2^{p-1}q \end{gather*}$

 

라고 쓸 수 있다. N의 약수로는 다음과 같은 애들이 있다.

 

$\begin{gather*}1, 2,...,2^{p-1}, \\ q, 2q,4q,...,2^{p-2}q \end{gather*}$

 

전부 다 더해주면

 

$\begin{gather*}\frac{2^p-1}{2-1} + q\frac{2^{p-1}-1}{2-1}=2^p-1+q(2^{p-1}-1) \\ = q2^{p-1}=N \end{gather*}$

 

완전수가 맞다!

 

---

 

Euler’s perfect number theorem

Every even perfect number is of the form

 

$\begin{gather*}N = 2^{p-1}(2^p-1) \end{gather*}$

 

where 2^p-1 is a mersenne prime.

짝수 완전수라면 2^p - 1은 메르센 소수이다.

 

No odd perfect number has been found yet.

사실 지금까지 알려진 홀수 완전수는 존재 X ⇒ 증명 안됨.

 

σ(n) : n의 약수들의 합
주의 : n을 포함해서 더하기 때문에 완전수 계산과 다르다!

$\begin{gather*}σ(n)=\sum_{d|n}d \end{gather*}$

성질)

$\begin{gather*}σ(p)=1 + p \end{gather*}$

 

소수의 약수는 1과 자기자신이기 때문이다.

$\begin{gather*}σ(p^k)=1+p+p^2+...+p^k=\frac{p^{k+1}-1}{p-1} \end{gather*}$

 

$\begin{gather*}\gcd(m,n)=1 \Rightarrow σ(mn)=σ(m)σ(n) \end{gather*}$

gcd ≠ 1이면 σ(m)과 σ(n)에서 중복되는 약수가 존재.

 

---

 

증명

$\begin{gather*}n:perfect \ \ number \Leftrightarrow σ(n)=n+n=2n \end{gather*}$

 

suppose n is an even perfect number.

 

 

$\begin{gather*}n=2^km \ \ (k\ge1,\ \ m:odd) \end{gather*}$

 

n은 짝수이기 때문에 위처럼 어떤 짝수와 홀수의 조합으로 쓸 수 있다.

 

$\begin{gather*}σ(n)=σ(2^k)σ(m) = (2^{k+1}-1)σ(m) \end{gather*}$

 

짝수와 홀수는 서로소라서 분리할 수 있다.

 

$\begin{gather*}σ(n)=2n=2(2^km)=2^{k+1}m \end{gather*}$

 

원래 완전수라는 조건에 의해 위처럼도 쓸 수 있다.

 

$\begin{gather*}\Rightarrow 2^{k+1}m=(2^{k+1}-1)σ(m) \end{gather*}$

 

따라서 완전수 조건에 의한 결과와 직접 σ계산을 통해 얻은 결과는 같다.

 

$\begin{gather*}σ(m) = 2^{k+1}c \end{gather*}$

 

양변이 같아야 하기에 σ(m)에는 2^{k+1}이 들어간다. 즉, 짝수와 홀수의 조합으로 쓴다면,

 

$\begin{gather*}\Rightarrow m=(2^{k+1}-1)c \end{gather*}$

 

항을 넘겨줘서 계산하면 m은 위와 같다.

 

만약 c > 1 이라면 m은 적어도 다음과 같은 3개의 약수를 가진다.

 

$\begin{gather*}1, \ \ c, \ \ m \end{gather*}$

 

$\begin{gather*}σ(m) \ge 1+c+m=1+c+(2^{k+1}-1)c \\ =1+2^{k+1}c \end{gather*}$

 

$\begin{gather*}\Rightarrow σ(m) \ge 2^{k+1}c + 1 \end{gather*}$

 

이어야 하는데 위에서 σ(m) = 2^{k+1}c였으므로 더 커야한다는 결과는 모순된다.

즉, c = 1일 수 밖에 없다.

 

$\begin{gather*}σ(m)=2^{k+1} \end{gather*}$

 

$\begin{gather*}m=2^{k+1}-1 \\n = 2^k(2^{k+1}-1) \end{gather*}$

 

이제 우리는 k+1이 소수임을 보이면 된다.

 

$\begin{gather*}σ(m)= 2^{k+1} \\=2^{k+1}-1+1 \\= m + 1 \end{gather*}$

 

이므로 m은 소수이다.

 

$\begin{gather*}m = 2^{k+1}-1 :prime \end{gather*}$

 

이때 x^n-1을 다음과 같이 쓸 수 있다.

 

$\begin{gather*}x^n-1=(x-1)(x^{n-1}+x^{n-2}+...+x+1) \end{gather*}$

 

그런데 만약 n이 소수가 아니라면

 

$\begin{gather*}(2^3)^5-1=(8-1)(8^4+8^3+8^2+8+1) \end{gather*}$

 

는 소수가 아니다.

즉, n이 소수여아만

 

$\begin{gather*}2^p-1=(2-1)(2^{p-1}+2^{p-2}+...+2+1) \end{gather*}$

 

이 되어 소수가 된다.

따라서 m이 소수이므로 n = k+1역시 소수이다.

 

결론 : n이 완전수라면 2^p - 1은 메르센 소수이다.

 

$\begin{gather*}N = 2^{p-1}(2^p-1) \end{gather*}$