Teorema Euler 📖 Wikipedia

Dalam teori bilangan, teorema Euler (dikenal juga sebagai teorema Fermat–Euler atau teorema totien Euler) menyatakan bahwa jika $a$ dan $n$ merupakan bilangan asli yang saling prima, maka $a^{\varphi (n)}$ akan kongruen dengan $1$ dalam modulo $n$ , dengan $\varphi (n)$ menyatakan fungsi phi Euler. Secara simbolis, maka hal ini dapat dinyatakan sebagai

$a^{\varphi (n)}\equiv 1{\pmod {n}}$

Pada tahun 1736, Leonhard Euler menerbitkan bukti dari teorema kecil Fermat^[1] (yang dikemukakan oleh Fermat tetapi tanpa bukti), yang merupakan kasus khusus dari teorema Euler ketika $n$ merupakan bilangan prima. Euler kemudian memberikan bukti lain dari teorema tersebut, yang berpuncak pada paper tahun 1763 miliknya, di mana ia membuktikan perumuman untuk kasus $n$ bukan bilangan prima.^[2]

Konvers dari teorema Euler juga berlaku: jika berlaku kekongruenan di atas, maka $a$ haruslah relatif prima dengan $n$ .

Teorema Euler dapat diperumum lebih lanjut dengan teorema Carmichael.

Teorema Euler dapat digunakan untuk menyederhanakan nilai pangkat yang besar pada modulo $n$ . Misalnya, untuk mencari digit terakhir dari $7^{222}$ (atau dengan kata lain, mencari nilai dari $7^{222}$ dalam modulo $10$ ), perhatikan bahwa nilai $\varphi (10)=4$ , dan pasangan bilangan 7 dan 10 saling koprima. Berdasarkan teorema Euler, maka didapatkan $7^{4}\equiv 1{\pmod {10}}$ . Akibatnya,

$7^{222}\equiv 7^{4\times 55+2}\equiv (7^{4})^{55}\times 7^{2}\equiv 1^{55}\times 7^{2}\equiv 49\equiv 9{\pmod {10}}$

Secara umum, saat menyederhanakan nilai pangkat dari $a$ pada modulo $n$ (dengan $a$ koprima dengan $n$ ), maka cukup bekerja pada modulo $\varphi (n)$ dari perpangkatan $a$ :

jika

x\equiv y{\pmod {\varphi (n)}}

, maka

a^{x}\equiv a^{y}{\pmod {n}}

.

Teorema Euler menjadi dasar kriptosistem RSA, yang banyak digunakan dalam komunikasi di internet. Dalam kriptosistem ini, teorema Euler digunakan dengan memilih bilangan $n$ sebagai hasil kali dari dua bilangan prima besar. Tingkat keamanan dari sistem ini didasarkan pada tingkat kesulitan dari proses pemfaktoran bilangan $n$ .

Bukti

sunting

Terdapat beberapa cara untuk membuktikan Teorema Euler, berikut dua diantaranya.

Teori grup

sunting

Teorema Euler dapat dibuktikan dengan menggunakan konsep dari teori grup:^[3]

Bukti —

Diambil sembarang $n\in \mathbb {N}$ . Misalkan $N$ menyatakan himpunan kelas-kelas residu modulo $n$ yang relatif prima dengan $n$ . Perhatikan bahwa $N$ membentuk struktur aljabar grup terhadap operasi perkalian (lihat artikel Grup perkalian bilangan bulat modulo $n$ ). Orde dari grup $N$ ini ialah $\varphi (n)$ .

Untuk sembarang $a\in N$ , maka terdapat suatu bilangan asli $k$ sedemikian sehingga $a^{k}\equiv 1{\pmod {n}}$ Akibatnya, himpunan $A=\left\{a,\,a^{2},\,a^{3},\,\ldots ,\,a^{k}\right\}$ membentuk subgrup dari $N$ terhadap operasi perkalian. Berdasarkan teorema Lagrange, maka orde dari $A$ harus membagi orde dari $N$ . Dengan kata lain, terdapat suatu $m\in \mathbb {N}$ sedemikian sehingga $\varphi (n)=mk$ . Hal ini mengakibatkan ${\begin{aligned}a^{k}&\equiv 1{\pmod {n}}\\(a^{k})^{m}&\equiv 1^{m}{\pmod {n}}\\a^{km}&\equiv 1{\pmod {n}}\\a^{\varphi (n)}&\equiv 1{\pmod {n}}\end{aligned}}$

Bukti langsung

sunting

Teorema Euler juga dapat dibuktikan secara langsung:^[4]^[5]

Bukti —

Diambil sembarang $n\in \mathbb {N}$ . Misalkan $R=\left\{x_{1},\,x_{2},\,x_{3},\,\ldots ,\,x_{\varphi (n)}\right\}$ adalah sistem residu tereduksi modulo $n$ . Telah dibuktikan sebelumnya bahwa himpunan $aR=\left\{ax_{1},\,ax_{2},\,ax_{3},\,\ldots ,\,ax_{\varphi (n)}\right\}=R$ untuk setiap bilangan asli $a$ yang relatif prima dengan $n$ . Dengan kata lain, himpunan $R$ identik dengan himpunan $aR$ —keduanya memiliki anggota yang sama, tetapi urutannya mungkin saja berbeda. Akibatnya, darab dari semua bilangan pada $aR$ akan kongruen dengan darab dari semua bilangan pada $R$ .

${\begin{aligned}(ax_{1})(ax_{2})(ax_{3})\ldots (ax_{\varphi (n)})&\equiv x_{1}\cdot x_{2}\cdot x_{3}\cdot \ldots \cdot x_{\varphi (n)}{\pmod {n}}\\a^{\varphi (n)}\cdot x_{1}\cdot x_{2}\cdot x_{3}\cdot \ldots \cdot x_{\varphi (n)}&\equiv 1\cdot x_{1}\cdot x_{2}\cdot x_{3}\cdot \ldots \cdot x_{\varphi (n)}{\pmod {n}}\end{aligned}}$

Oleh karena setiap $x_{i}$ relatif prima dengan $n$ , maka setiap $x_{i}$ memiliki elemen invers dalam modulo $n$ , sehingga dengan "mencoret" setiap $x_{i}$ pada kedua ruas, didapatkan teorema Euler.

${\begin{aligned}a^{\varphi (n)}\cdot {\cancel {x_{1}}}\cdot {\cancel {x_{2}}}\cdot {\cancel {x_{3}}}\cdot \ldots \cdot {\cancel {x_{\varphi (n)}}}&\equiv 1\cdot {\cancel {x_{1}}}\cdot {\cancel {x_{2}}}\cdot {\cancel {x_{3}}}\cdot \ldots \cdot {\cancel {x_{\varphi (n)}}}{\pmod {n}}\\a^{\varphi (n)}&\equiv 1{\pmod {n}}\end{aligned}}$

Lihat pula

sunting

Catatan

sunting

^
Lihat:
- Euler, Leonhard. Theorematum quorundam ad numeros primos spectantium demonstratio [Bukti dari beberapa teorema mengenai bilangan prima] (dalam bahasa Latin). Vol. 8. hlm. 141–146. ISSN 2686-7079.
- Untuk informasi lebih lanjut mengenai paper ini, termasuk terjemahan bahasa Inggris, lihat: The Euler Archive.
^
Lihat:
- Euler, Leonhard (1763). Theoremata arithmetica nova methodo demonstrata [Bukti metode baru dalam teori aritmetika] (dalam bahasa Latin). Vol. 8. hlm. 74–104. ISSN 2658-5065. Teorema Euler muncul sebagai "Teorema 11" pada halaman 102. Paper ini pertama kali dipresentasikan ke Akademi Berlin pada 8 Juni 1758 dan ke Akademi St. Petersburg pada 15 Oktober 1759. Dalam paper ini, fungsi totient Euler, $\varphi (n)$ , tidak dinamai tetapi disebut sebagai "numerus partium ad $N$ primarum" (banyaknya bagian prima dengan $N$ ; yaitu, banyaknya bilangan asli yang kurang dari $N$ dan relatif prima dengan $N$ )
- Untuk informasi lebih lanjut mengenai makalah ini, lihat: The Euler Archive.
- Untuk ulasan pekerjaan Euler selama bertahun-tahun yang mengarah ke teorema Euler, lihat: Sandifer, Ed (2005). "Euler's proof of Fermat's little theorem" [Bukti Euler atas teorema kecil Fermat] (PDF) (dalam bahasa Inggris). Diarsipkan dari asli (PDF) tanggal 28-08-2006.
^ Ireland & Rosen, corr. 1 to prop 3.3.2
^ Hardy, G. H.; Wright, E. M. (1980), An Introduction to the Theory of Numbers (Fifth edition) [Pengantar Teori Bilangan (edisi kelima)] (dalam bahasa Inggris), Oxford: Oxford University Press, hlm. 63, ISBN 978-0-19-853171-5
^ Landau, Edmund (1966). Elementary Number Theory [Teori Bilangan Elementer] (dalam bahasa Inggris). New York: Chelsea. hlm. 50.

Referensi

sunting

Disquisitiones Arithmeticae telah diterjemahkan dari bahasa Latin Ciceronian Gauss ke dalam bahasa Inggris dan Jerman. Edisi Jerman mencakup semua paper teori bilangan miliknya: semua bukti dari timbal balik kuadratik, penentuan tanda dari jumlah Gauss, penyelidikan timbal balik bikuadratik, serta catatan yang tidak diterbitkan.

Gauss, Carl Friedrich; Clarke, Arthur A. (translated into English) (1986), Disquisitiones Arithemeticae (Second, corrected edition), New York: Springer, ISBN 0-387-96254-9
Gauss, Carl Friedrich; Maser, H. (translated into German) (1965), Untersuchungen uber hohere Arithmetik (Disquisitiones Arithemeticae & other papers on number theory) (edisi kedua), New York: Chelsea, ISBN 0-8284-0191-8
Hardy, G. H.; Wright, E. M. (1980), An Introduction to the Theory of Numbers (Fifth edition) [Pengantar Teori Bilangan (edisi kelima)] (dalam bahasa Inggris), Oxford: Oxford University Press, ISBN 978-0-19-853171-5
Ireland, Kenneth; Rosen, Michael (1990), A Classical Introduction to Modern Number Theory (Second edition) [Pengantar Klasik dari Teori Bilangan Modern (edisi kedua)], New York: Springer, ISBN 0-387-97329-X
Landau, Edmund (1966), Elementary Number Theory [Teori Bilangan Elementer] (dalam bahasa Inggris), New York: Chelsea

Pranala luar

sunting

(Inggris) Weisstein, Eric W. "Euler's Totient Theorem". MathWorld.
(Inggris) (Inggris) Teorema Euler di PlanetMath.

[1] Lihat:
Euler, Leonhard. Theorematum quorundam ad numeros primos spectantium demonstratio [Bukti dari beberapa teorema mengenai bilangan prima] (dalam bahasa Latin). Vol. 8. hlm. 141–146. ISSN 2686-7079.

Untuk informasi lebih lanjut mengenai paper ini, termasuk terjemahan bahasa Inggris, lihat: The Euler Archive.

[2] Euler, Leonhard. Theorematum quorundam ad numeros primos spectantium demonstratio [Bukti dari beberapa teorema mengenai bilangan prima] (dalam bahasa Latin). Vol. 8. hlm. 141–146. ISSN 2686-7079.

[3] Untuk informasi lebih lanjut mengenai paper ini, termasuk terjemahan bahasa Inggris, lihat: The Euler Archive.

[2] Lihat:
Euler, Leonhard (1763). Theoremata arithmetica nova methodo demonstrata [Bukti metode baru dalam teori aritmetika] (dalam bahasa Latin). Vol. 8. hlm. 74–104. ISSN 2658-5065. Teorema Euler muncul sebagai "Teorema 11" pada halaman 102. Paper ini pertama kali dipresentasikan ke Akademi Berlin pada 8 Juni 1758 dan ke Akademi St. Petersburg pada 15 Oktober 1759. Dalam paper ini, fungsi totient Euler, $\varphi (n)$ , tidak dinamai tetapi disebut sebagai "numerus partium ad $N$ primarum" (banyaknya bagian prima dengan $N$ ; yaitu, banyaknya bilangan asli yang kurang dari $N$ dan relatif prima dengan $N$ )

Untuk informasi lebih lanjut mengenai makalah ini, lihat: The Euler Archive.

Untuk ulasan pekerjaan Euler selama bertahun-tahun yang mengarah ke teorema Euler, lihat: Sandifer, Ed (2005). "Euler's proof of Fermat's little theorem" [Bukti Euler atas teorema kecil Fermat] (PDF) (dalam bahasa Inggris). Diarsipkan dari asli (PDF) tanggal 28-08-2006.

[5] Euler, Leonhard (1763). Theoremata arithmetica nova methodo demonstrata [Bukti metode baru dalam teori aritmetika] (dalam bahasa Latin). Vol. 8. hlm. 74–104. ISSN 2658-5065. Teorema Euler muncul sebagai "Teorema 11" pada halaman 102. Paper ini pertama kali dipresentasikan ke Akademi Berlin pada 8 Juni 1758 dan ke Akademi St. Petersburg pada 15 Oktober 1759. Dalam paper ini, fungsi totient Euler, $\varphi (n)$ , tidak dinamai tetapi disebut sebagai "numerus partium ad $N$ primarum" (banyaknya bagian prima dengan $N$ ; yaitu, banyaknya bilangan asli yang kurang dari $N$ dan relatif prima dengan $N$ )

[6] Untuk informasi lebih lanjut mengenai makalah ini, lihat: The Euler Archive.

[7] Untuk ulasan pekerjaan Euler selama bertahun-tahun yang mengarah ke teorema Euler, lihat: Sandifer, Ed (2005). "Euler's proof of Fermat's little theorem" [Bukti Euler atas teorema kecil Fermat] (PDF) (dalam bahasa Inggris). Diarsipkan dari asli (PDF) tanggal 28-08-2006.

[3] Ireland & Rosen, corr. 1 to prop 3.3.2

[4] Hardy, G. H.; Wright, E. M. (1980), An Introduction to the Theory of Numbers (Fifth edition) [Pengantar Teori Bilangan (edisi kelima)] (dalam bahasa Inggris), Oxford: Oxford University Press, hlm. 63, ISBN 978-0-19-853171-5

[5] Landau, Edmund (1966). Elementary Number Theory [Teori Bilangan Elementer] (dalam bahasa Inggris). New York: Chelsea. hlm. 50.

[1]

[2]

[3]

[4]

[5]

Teorema Euler 📖 Wikipedia

Daftar isi

Bukti

Teori grup

Bukti langsung

Lihat pula

Catatan

Referensi

Pranala luar

📚 Artikel Terkait di Wikipedia

Daftar hal-hal yang dinamai dari Leonhard Euler

Aritmetika modular

Bilangan prima

Daftar topik teori bilangan

Kasus khusus

Teorema kecil Fermat

Daftar teorema

Teorema Euclid-Euler