유클리드의 완전수 공식 유도

유클리드의 완전수 공식 유도

공식 1

$2^{p}-1$ 이 소수면 $2^{p-1}(2^{p} - 1)$ 은 완전수다.

설명

모든 완전수가 저런 형태일지는 확실하지 않지만, 저런 형태는 반드시 완전수다.

예를 들면 소수 $(2^2 -1) = 3$ 에 대해 $2^{2-1}(2^2 -1) = 6$ 은 완전수다.완전수와 메르센 소수가 이러한 관계를 가지고 있음은 메르센 소수의 등비급수전개에서 어느정도 짐작을 할 수가 있었다.

유도

$2^{p}-1$ 이 소수이므로, $2^{p-1}(2^{p} - 1)$ 의 약수는 $$ 1,2, \cdots , 2^{p-1} \\ (2^{p}-1), 2 (2^{p}-1), \cdots , 2^{p-2} (2^{p}-1) $$ 두 부류로 나뉜다. 등비수열의 합 공식에 의해 $$ 1 + 2 + \cdots + 2^{p-1} = { {2^{p}-1} \over {2 - 1} } = 2^{p}-1 $$ 마찬가지로 $$ (2^{p}-1) + 2 (2^{p}-1) + \cdots + 2^{p-2} (2^{p}-1) = ( 2^{p-1} - 1 ) (2^{p}-1) $$ 이다. 둘을 더하면 $$ 2^{p}-1 + ( 2^{p-1} - 1 ) (2^{p}-1) = 2^{p-1}(2^{p} - 1) $$ 이고, 따라서 $2^{p-1}(2^{p} - 1)$ 은 완전수다.


  1. Silverman. (2012). A Friendly Introduction to Number Theory (4th Edition): p102. ↩︎

댓글