Dalam teori bilangan, Teorema Euclid-Euler adalah teorema yang menghubungkan bilangan sempurna dengan bilangan prima Mersenne. Teorema tersebut menyatakan bahwa suatu bilangan genap adalah bilangan sempurna jika dan hanya jika bilangan tersebut memiliki bentuk umum ${\displaystyle 2^{p-1}\left(2^{p}-1\right)}$, dengan ${\displaystyle 2^{p}-1}$ adalah bilangan prima. Teorema ini dinamai dari Euclid dan Leonhard Euler, yang berturut-turut membuktikan aspek "jika" dan "hanya jika" dari teorema ini.

Terdapat konjektur yang menyatakan bahwa terdapat tak terhingga banyaknya bilangan prima Mersenne. Walaupun kebenaran konjektur tersebut masih belum diketahui, menurut teorema Euclid-Euler, hal tersebut ekuivalen dengan konjektur bahwa terdapat tak terhingga banyaknya bilangan sempurna genap. Namun, tidak diketahui juga apakah terdapat setidaknya satu bilangan sempurna ganjil.^[1]

Suatu bilangan asli disebut sebagai bilangan sempurna jika bilangan tersebut sama dengan jumlahan pembagi wajarnya, yaitu bilangan yang kurang dari dan habis membagi bilangan tersebut (atau dengan kata lain, sisa pembagiannya adalah ${\displaystyle 0}$). Sebagai contoh, pembagi wajar dari ${\displaystyle 6}$ adalah ${\displaystyle 1}$, ${\displaystyle 2}$, dan ${\displaystyle 3}$, dan karena hasil jumlahnya sama dengan ${\displaystyle 6}$, maka ${\displaystyle 6}$ adalah bilangan sempurna.

Suatu bilangan prima disebut bilangan prima Mersenne apabila bilangan tersebut dapat dinyatakan sebagai ${\displaystyle 2^{p}-1}$, dengan ${\displaystyle p}$ adalah bilangan prima. Perhatikan bahwa tidak semua ${\displaystyle p}$ akan menghasilkan bilangan prima Mersenne. Misalnya, ${\displaystyle 2^{3}-1=7}$ adalah bilangan prima Mersenne, tetapi ${\displaystyle 2^{11}-1=2047=23\cdot 89}$ bukan.

Teorema Euclid-Euler menyatakan bahwa suatu bilangan asli genap adalah bilangan sempurna jika dan hanya jika bilangan tersebut memiliki bentuk umum ${\displaystyle 2^{p-1}\cdot M_{p}}$, dengan ${\displaystyle M_{p}}$ adalah bilangan prima Mersenne.^[1] Bilangan sempurna ${\displaystyle 6}$ diperoleh dengan memilih ${\displaystyle p=2}$, sebab ${\displaystyle M_{2}=2^{2}-1}$ dan ${\displaystyle 2^{2-1}\cdot M_{2}=2\cdot 3=6}$, dan bilangan prima Mersenne ${\displaystyle 7}$ berkorespondensi (dengan cara serupa) dengan bilangan sempurna ${\displaystyle 28}$.

Bukti Euler tergolong pendek^[1] dan mengandalkan fakta bahwa fungsi jumlah pembagi ${\displaystyle \sigma }$ bersifat multiplikatif; yaitu, jika ${\displaystyle a}$ dan ${\displaystyle b}$ adalah dua bilangan bulat yang relatif prima, maka berlaku ${\displaystyle \sigma (ab)=\sigma (a)\cdot \sigma (b)}$. Agar rumus ini dapat digunakan, semua bilangan positif yang habis membagi bilangan tersebut harus dijumlahkan, termasuk bilangan itu sendiri. Dengan menggunakan fungsi ini, suatu bilangan asli adalah bilangan sempurna jika dan hanya jika hasil jumlah dari pembaginya bernilai dua kali bilangan tersebut.

Salah satu arah dari teoremanya (bagian yang telah dibuktikan oleh Euclid) diakibatkan langsung dari sifat multiplikatif: setiap bilangan prima Mersenne akan menghasilkan bilangan sempurna genap. Saat ${\displaystyle 2^{p}-1}$ adalah bilangan prima, maka ${\displaystyle 2^{p-1}}$ dan ${\displaystyle 2^{p}-1}$ akan relatif prima, sehingga berlaku $${\displaystyle \sigma (2^{p-1}\cdot \left(2^{p}-1\right))=\sigma (2^{p-1})\cdot \sigma (2^{p}-1)}$$ Perhatikan bahwa

1. Pembagi positif dari ${\displaystyle 2^{p-1}}$ adalah ${\displaystyle \left\{1,\,2,\,4,\,8,\,\ldots ,\,2^{p-1}\right\}}$, sehingga hasil jumlah dari pembagi bilangan ${\displaystyle 2^{p-1}}$ adalah deret geometri yang nilainya adalah ${\displaystyle 2^{p}-1}$.
2. Oleh karena ${\displaystyle 2^{p}-1}$ adalah bilangan prima, maka pembagi positifnya ialah ${\displaystyle \left\{1,\,2^{p-1}-1\right\}}$, sehingga hasil jumlah pembagi bilangan ${\displaystyle 2^{p}-1}$ adalah ${\displaystyle 2^{p}}$.

Dengan menggabungkan dua hasil di atas, jika bilangan asli ${\displaystyle N}$ dapat dinyatakan sebagai ${\displaystyle 2^{p-1}\cdot \left(2^{p}-1\right)}$, maka $${\displaystyle {\begin{aligned}\sigma (N)&=\sigma (2^{p-1}\cdot \left(2^{p}-1\right))\\&=\sigma (2^{p-1})\cdot \sigma \left(2^{p}-1\right)\\&=\left(2^{p}-1\right)\cdot \left(2^{p}\right)\\&=2\cdot 2^{p-1}(2^{p}-1)\\&=2N\end{aligned}}}$$ Akibatnya, bilangan asli ${\displaystyle N}$ adalah bilangan sempurna.^[2][3][4]

Untuk membuktikan arah lainnya, misalkan diberikan suatu bilangan sempurna genap ${\displaystyle N}$. Dari informasi tersebut, maka ${\displaystyle N}$ dapat dinyatakan sebagai $${\displaystyle N=2^{k}x}$$ dengan ${\displaystyle x}$ adalah bilangan ganjil. Oleh karena ${\displaystyle N}$ adalah bilangan sempurna, maka berlaku $${\displaystyle {\begin{aligned}\sigma (N)&=2N\\\sigma \left(2^{k}x\right)&=2\left(2^{k}x\right)\\\sigma \left(2^{k}\right)\cdot \sigma (x)&=2^{k+1}\cdot x\\\left(2^{k+1}-1\right)\cdot \sigma (x)&=2^{k+1}\cdot x\end{aligned}}}$$ Perhatikan bahwa faktor ${\displaystyle 2^{k+1}-1}$ pada ruas kiri bernilai ganjil, sehingga ${\displaystyle 2^{k+1}-1\mid x}$, satu-satunya faktor ganjil pada ruas kanan. Berdasarkan definisi dari "habis membagi", maka terdapat suatu bilangan bulat ${\displaystyle c}$ sedemikian sehingga ${\displaystyle c\left(2^{k+1}-1\right)=x}$. Akibatnya, $${\displaystyle {\begin{aligned}\left(2^{k+1}-1\right)\cdot \sigma (x)&=2^{k+1}\cdot x\\c\left(2^{k+1}-1\right)\cdot \sigma (x)&=2^{k+1}\cdot cx\\x\cdot \sigma (x)&=2^{k+1}\cdot cx\\\sigma (x)&=2^{k+1}\cdot c\end{aligned}}}$$ Oleh karena nilai ${\displaystyle 2^{k+1}-1}$ tidak kurang dari ${\displaystyle 3}$, maka ${\displaystyle c}$ adalah pembagi wajar dari ${\displaystyle x}$. Akibatnya, $${\displaystyle {\begin{aligned}\sigma (x)&=x+c+\,{\text{faktor-faktor lainnya}}\\\sigma (x)&=2^{k+1}\cdot c+\,{\text{faktor-faktor lainnya}}\\2^{k+1}\cdot c&=2^{k+1}\cdot c+\,{\text{faktor-faktor lainnya}}\\\end{aligned}}}$$

Agar persamaan di atas bernilai benar, maka tidak ada faktor lain yang habis membagi ${\displaystyle x}$ selain ${\displaystyle c}$ dan ${\displaystyle x}$ itu sendiri, sehingga ${\displaystyle c}$ haruslah ${\displaystyle 1}$ dan ${\displaystyle x}$ adalah bilangan prima dengan bentuk umum ${\displaystyle 2^{k+1}-1}$.^[2][3][4]