Teorema Euler

Teorema mengenai eksponensiasi modularTemplat:SHORTDESC:Teorema mengenai eksponensiasi modular

Artikel ini berisi tentang Teorema Euler dalam teori bilangan. Untuk kegunaan lain, lihat Daftar topik yang dinamai berdasarkan Leonhard Euler.

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

a φ ( n ) ≡ 1 ( mod n ) {\displaystyle a^{\varphi (n)}\equiv 1{\pmod {n}}} $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 {\displaystyle n} $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 {\displaystyle n} $n$ bukan bilangan prima.^[2]

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

Teorema Euler dapat diperumum lebih lanjut dengan teorema Carmichael.

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

7 222 ≡ 7 4 × 55 + 2 ≡ ( 7 4 ) 55 × 7 2 ≡ 1 55 × 7 2 ≡ 49 ≡ 9 ( mod 10 ) {\displaystyle 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}}} $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 {\displaystyle a} $a$ pada modulo n {\displaystyle n} $n$ (dengan a {\displaystyle a} $a$ koprima dengan n {\displaystyle n} $n$ ), maka cukup bekerja pada modulo φ ( n ) {\displaystyle \varphi (n)} $\varphi (n)$ dari perpangkatan a {\displaystyle a} $a$ :

jika x ≡ y ( mod φ ( n ) ) {\displaystyle x\equiv y{\pmod {\varphi (n)}}} $x\equiv y{\pmod {\varphi (n)}}$ , maka a x ≡ a y ( mod n ) {\displaystyle a^{x}\equiv a^{y}{\pmod {n}}} $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 {\displaystyle n} $n$ sebagai hasil kali dari dua bilangan prima besar. Tingkat keamanan dari sistem ini didasarkan pada tingkat kesulitan dari proses pemfaktoran bilangan n {\displaystyle n} $n$ .

Bukti

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

Teori grup

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

Bukti —

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

Untuk sembarang a ∈ N {\displaystyle a\in N} $a\in N$ , maka terdapat suatu bilangan asli k {\displaystyle k} $k$ sedemikian sehingga a k ≡ 1 ( mod n ) {\displaystyle a^{k}\equiv 1{\pmod {n}}} $a^{k}\equiv 1{\pmod {n}}$ Akibatnya, himpunan A = { a , a 2 , a 3 , … , a k } {\displaystyle A=\left\{a,\,a^{2},\,a^{3},\,\ldots ,\,a^{k}\right\}} $A=\left\{a,\,a^{2},\,a^{3},\,\ldots ,\,a^{k}\right\}$ membentuk subgrup dari N {\displaystyle N} $N$ terhadap operasi perkalian. Berdasarkan teorema Lagrange, maka orde dari A {\displaystyle A} $A$ harus membagi orde dari N {\displaystyle N} $N$ . Dengan kata lain, terdapat suatu m ∈ N {\displaystyle m\in \mathbb {N} } $m\in \mathbb {N}$ sedemikian sehingga φ ( n ) = m k {\displaystyle \varphi (n)=mk} $\varphi (n)=mk$ . Hal ini mengakibatkan a k ≡ 1 ( mod n ) ( a k ) m ≡ 1 m ( mod n ) a k m ≡ 1 ( mod n ) a φ ( n ) ≡ 1 ( mod n ) {\displaystyle {\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}}} ${\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

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

Bukti —

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

( a x 1 ) ( a x 2 ) ( a x 3 ) … ( a x φ ( n ) ) ≡ x 1 ⋅ x 2 ⋅ x 3 ⋅ … ⋅ x φ ( n ) ( mod n ) a φ ( n ) ⋅ x 1 ⋅ x 2 ⋅ x 3 ⋅ … ⋅ x φ ( n ) ≡ 1 ⋅ x 1 ⋅ x 2 ⋅ x 3 ⋅ … ⋅ x φ ( n ) ( mod n ) {\displaystyle {\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}}} ${\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 {\displaystyle x_{i}} $x_{i}$ relatif prima dengan n {\displaystyle n} $n$ , maka setiap x i {\displaystyle x_{i}} $x_{i}$ memiliki elemen invers dalam modulo n {\displaystyle n} $n$ , sehingga dengan "mencoret" setiap x i {\displaystyle x_{i}} $x_{i}$ pada kedua ruas, didapatkan teorema Euler.

a φ ( n ) ⋅ x 1 ⋅ x 2 ⋅ x 3 ⋅ … ⋅ x φ ( n ) ≡ 1 ⋅ x 1 ⋅ x 2 ⋅ x 3 ⋅ … ⋅ x φ ( n ) ( mod n ) a φ ( n ) ≡ 1 ( mod n ) {\displaystyle {\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}}} ${\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

Catatan

↑ 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.{{cite book}}: |journal= diabaikan
- 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.{{cite book}}: |journal= diabaikan 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, φ ( n ) {\displaystyle \varphi (n)} $\varphi (n)$ , tidak dinamai tetapi disebut sebagai "numerus partium ad N {\displaystyle N} $N$ primarum" (banyaknya bagian prima dengan N {\displaystyle N} $N$ ; yaitu, banyaknya bilangan asli yang kurang dari N {\displaystyle N} $N$ dan relatif prima dengan N {\displaystyle N} $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.{{cite web}}: Periksa nilai tanggal dalam: |archive-date=
↑ 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

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

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

Portal:

Matematika

l b s Leonhard Euler
Karya	Mechanica Introductio in analysin infinitorum Institutiones calculi differentialis Institutiones calculi integralis Letters to a German Princess
Konsep dan teori	Beban kritis Euler Bilangan Euler Bilangan Euler (fisika) Fungsi Euler Identitas empat kuadrat Euler Identitas Euler Konjektur jumlah pangkat Euler Konstanta Euler–Mascheroni Metode Euler Metode Euler–Maruyama Persamaan Euler (dinamika fluida) Persamaan Euler–Lagrange Persamaan Euler–Lotka Persamaan Euler–Poisson–Darboux Persamaan Euler–Tricomi Persamaan pompa dan turbin Euler Rumus Euler–Maclaurin Rumus Euler–Rodrigues Rumus pecahan berlanjut Euler Rumus Euler Teorema berkas Euler–Bernoulli Teorema Euler Teorema rotasi Euler
Lain-lain	Penyematan nama Euler Committee Johann Euler Johann Bernoulli (keluarga Bernoulli) Georg Gsell Keluarga Merian Sekolah Basel (matematika)