에우클레이데스-오일러 정리

에우클레이데스-오일러 정리(Euclid–Euler theorem)는 완전수를 메르센 소수와 연관시키는 수론의 정리이다. 이 정리는 짝수가 2^p−1(2^p − 1)의 형태를 가질 때에만 완전수이며, 여기서 2^p − 1은 소수임을 명시한다. 이 정리는 각각 정리의 "if" 부분과 "only if" 부분을 증명한 수학자 에우클레이데스와 레온하르트 오일러의 이름을 따서 명명되었다.

메르센 소수가 무한히 많을 것이라고 추측되어 왔다. 이 추측의 진실은 아직 알려지지 않았지만, 에우클레이데스-오일러 정리에 따르면 이는 짝수 완전수가 무한히 많다는 추측과 동등하다. 그러나 홀수 완전수가 존재하는지조차 알려져 있지 않다.^[1]

진술 및 예시

완전수는 자신보다 작고 자신을 정확히 나누는 (나머지가 0인) 약수의 합과 같은 자연수이다. 예를 들어, 6의 진약수는 1, 2, 3이며, 이들의 합은 6이므로 6은 완전수이다.

메르센 소수는 M_p = 2^p − 1 형태의 소수로, 2의 거듭제곱보다 하나 작은 수이다. 이 형태의 수가 소수이려면 p 자체도 소수여야 하지만, 모든 소수가 이런 방식으로 메르센 소수를 만들어내지는 않는다. 예를 들어, 2³ − 1 = 7은 메르센 소수이지만, 2¹¹ − 1 = 2047 = 23 × 89은 아니다.

에우클레이데스-오일러 정리는 짝수 자연수가 2^p−1M_p 형태를 가질 때에만 완전수이며, 여기서 M_p는 메르센 소수임을 명시한다.^[1] 완전수 6은 p = 2에서 2²⁻¹M₂ = 2 × 3 = 6으로 얻어지며, 메르센 소수 7은 같은 방식으로 완전수 28에 해당한다.

역사

에우클레이데스는 2^p − 1이 소수일 때마다 2^p−1(2^p − 1)이 짝수 완전수임을 증명했다. 이것은 에우클레이데스의 원론의 수론에 관한 마지막 결과이다. 원론의 후기 책들은 대신 무리수, 입체기하학, 황금비에 관한 내용이다. 에우클레이데스는 1에서 시작하여 공비 2를 가지는 유한 등비급수의 합 q가 소수이면, 이 합에 해당 급수의 마지막 항 t을 곱한 것이 완전수임을 진술함으로써 결과를 표현한다. 이러한 용어로 표현하면, 유한 급수의 합 q는 메르센 소수 2^p − 1이고 급수의 마지막 항 t은 2의 거듭제곱 2^p−1이다. 에우클레이데스는 qt가 완전수임을 관찰함으로써 증명하는데, 이는 q에서 시작하여 같은 항의 수를 가진 공비 2의 등비급수가 원래 급수에 비례한다는 것이다. 따라서 원래 급수의 합이 q = 2t − 1이므로, 두 번째 급수의 합은 q(2t − 1) = 2qt − q이고, 두 급수 모두 합하면 2qt가 되어 가정된 완전수의 두 배가 된다. 그러나 이 두 급수는 서로 겹치지 않으며 (q의 소수성에 의해) qt의 모든 약수를 소진하므로, qt는 약수들의 합이 2qt가 되어 완전수임을 보인다.^[2]

에우클레이데스 이후 천년이 지나 알하젠은 서기 1천년경 모든 짝수 완전수는 2^p−1(2^p − 1) 형태이며 여기서 2^p − 1은 소수라고 추측했지만, 이 결과를 증명하지는 못했다.^[3] 에우클레이데스 이후 2000년이 넘게 지난 18세기에 이르러서야^[4] 레온하르트 오일러가 공식 2^p−1(2^p − 1)이 모든 짝수 완전수를 생성한다는 것을 증명했다.^[1][5] 따라서 짝수 완전수와 메르센 소수 사이에는 일대일 관계가 성립한다. 각 메르센 소수는 하나의 짝수 완전수를 생성하고, 그 반대도 마찬가지이다. 오일러가 에우클레이데스-오일러 정리를 증명한 후 빅토르-아메데 레베그, 로버트 대니얼 카마이클, 레너드 유진 딕슨, 존 크노프마허, 웨인 L. 맥다니얼 등 다른 수학자가 다양한 증명을 발표했다. 특히 딕슨의 증명은 교과서에서 흔히 사용되었다.^[6]

이 정리는 1999년부터 "수학 100대 정리"의 웹 목록에 포함되었고, 이는 나중에 프릭 비데이크(Freek Wiedijk)가 다양한 증명 보조기의 성능을 테스트하는 벤치마크 세트로 사용되었다. 2025년 기준으로, 에우클레이데스-오일러 정리의 증명은 비데이크가 기록한 12개의 증명 보조기 중 7개에서 형식화되었다.^[7]

증명

오일러의 증명은 짧으며^[1] 약수의 합 함수 σ가 곱셈적이라는 사실에 의존한다. 즉, a와 b가 서로소인 두 정수이면, σ(ab) = σ(a)σ(b)가 성립한다. 이 공식이 유효하려면 어떤 수의 약수 합은 진약수뿐만 아니라 그 자신도 포함해야 한다. 어떤 수가 완전수이려면 약수 합이 그 값의 두 배와 같아야 한다.

충분조건

정리의 한 방향 (에우클레이데스가 이미 증명한 부분)은 곱셈적 성질로부터 즉시 도출된다. 모든 메르센 소수는 짝수 완전수를 생성한다. 2^p − 1이 소수일 때, ${\displaystyle \sigma (2^{p-1}(2^{p}-1))=\sigma (2^{p-1})\sigma (2^{p}-1).}$ 2^p−1의 약수는 1, 2, 4, 8, ..., 2^p−1이다. 이 약수의 합은 합이 2^p − 1인 등비급수이다. 다음으로, 2^p − 1은 소수이므로, 그 약수는 1과 자기 자신뿐이며, 따라서 약수들의 합은 2^p이다.

이것들을 결합하면, $${\displaystyle {\begin{aligned}\sigma (2^{p-1}(2^{p}-1))&=\sigma (2^{p-1})\sigma (2^{p}-1)\\&=(2^{p}-1)(2^{p})\\&=2(2^{p-1})(2^{p}-1).\end{aligned}}}$$ 따라서 2^p−1(2^p − 1)은 완전수이다.^[8][9][10]

필요조건

다른 방향으로, 짝수 완전수가 주어졌다고 가정하고, 이를 2^kx로 부분 인수분해하는데, 여기서 x는 홀수이다. 2^kx가 완전수가 되려면, 약수의 합이 그 값의 두 배여야 한다:

${\displaystyle 2^{k+1}x=\sigma (2^{k}x)=(2^{k+1}-1)\sigma (x).}$

(∗)

(∗)의 오른쪽 항에 있는 홀수 인자 2^k+1 − 1은 3 이상이며, 왼쪽 항의 유일한 홀수 인자인 x를 나누어야 하므로, x/(2^k+1 − 1)는 x의 진약수이다. (∗)의 양변을 공통 인자 2^k+1 − 1로 나누고 x의 알려진 약수인 x와 x/(2^k+1 − 1)을 고려하면 다음과 같다.

${\displaystyle 2^{k+1}x/(2^{k+1}-1)=\sigma (x)=x+x/(2^{k+1}-1)+{}}$다른 약수들${\displaystyle {}=2^{k+1}x/(2^{k+1}-1)+{}}$다른 약수들.

이 등식이 참이려면 다른 약수가 없어야 한다. 따라서 x/(2^k+1 − 1)은 1이어야 하고, x는 2^k+1 − 1 형태의 소수여야 한다.^[8][9][10]