Makalah teori fermat, wilson dan euler

BAB I

PENDAHULUAN

A.      Latar belakang masalah

Dalam mengenal teori-teori bilangan ada tiga matematikawan yang memberikan kontribusi besar dalam pengembangan teori bilangan yaitu Fermat, Wilson, dan Euler. Ketiga matematikawan ini menciptakan teorema-teorema yang diberikan nama sesuai nama mereka yaitu Teori Fermart, Teori Wilson dan Teori Euler.

Teorema dan konsep terkait yang dikembangkan oleh tiga matematikawan ini memotivasi kami sebagai mahasiswa untuk membuat makalah agar pembaca  lebih mengenal bagaimana teori ini digunakan dalam pengembangan ilmu pengetahuan. Dengan mempelajari teorema ini juga, kita bisa mengetahui apa sebenarnya teorema yang didedikasikan oleh Fermat, Wilson, dan Euler serta bagaimana keterkaitan antara ketiga teorema ini. Untuk lebih jelasnya akan dibahas pada makalah ini.

B.       Rumusan masalah

A.    Bagaimanakah teorema dari Fermat, Wilson dan Euler ?

B.     Bagaimanakah keterkaitan antara teorema dari Fermat, Wilson, dan Euler?

C.      Tujuan

A.    Untuk mengetahui bagaimanakah teorema dari Fermat, Wilson dan Euler.

B.     Untuk mengetahui bagaimanakah keterkaitan antara teorema dari Fermat, Wilson, dan Euler.

BAB II

KAJIAN TEORI

Teori Fermat, Wilson Dan Euler

Teori Fermat, walaupun bukan suatu teorema besar, pada tahun 1622 atau sekitar itu, Pierre de Fermat telah membuat suatu teorema yang membuat dirinya sangat terkenal, yang saat ini dikenal dengan teorema kecil Fermat dengan rumusan an + bn = cn dengan n>2 dan merupakan bilangan asli. Fermat pertama kali menuliskannya pada sebuah buku perpustakaan dengan mencoret-coret buku tersebut. Masalahnya, bukan itu yang membuat teorema kecil Fermat begitu terkenal. Yang membuatnya terkenal adalah bahwa sampai saat ini teorema Fermat belum dapat dibuktikan, padahal dalam bukunya beliau menuliskan “saya bisa membuktikan dengan mudah, tetapi sayang pinggiran-pinggiran halaman ini terlalu kecil untuk memuatnya”. Dalam “keputusasaan” karena tidak sanggup membuktikan, banyak orang berpendapat bahwa sesungguhnya Fermat sendiri pun tidak mampu membuktikannya.

A.      Teori Fermat

Menguji keprimaan suatu bilangan bulat n dengan cara membaginya dengan sejumlah bilangan prima yang    tentu kurang efektif untuk n yang besar, karena kita harus menentukan terlebih dahulu semua bilangan  prima yang lebih kecil dari . Terdapat metode lain yang dapat digunakan untuk menguji keprimaan suatu bilangan bulat yang dikenal dengan nama teorema Fermat (biasanya disebut dengan Fermat’s little theorem).

Sebelum teorema Fermat dijelaskan, teorema berikut perlu diperhatikan.

Teorema 1 Jika (a,m)=1 maka sisaan terkecil suatu mod m barisan: a, 2a, 3a,..., (m-1)a adalah suatu permutasi dari 1,2,3,...,(m-1)

 

Dengan perkataan lain, berdasarkan teorema 1 dapat dikatakan bahwa jika (a,m)=1 maka himpunaniap bilangan bulat akan kongruen modulo m dengan tepat satu dari 0, a, 2a,..., (m-1)a. Perlu diingat bahwa himpunaniap bilangan bulat akan kongruen modulo m dengan tepat satu dari 0,1,2,3,..., (m-1).

Bukti:

Perhatikan barisan bilangan: a, 2a, 3a, ..., (m-1)a        ...(*)

Bilangan pada barisan (*) tidak ada satu pun yang kongruen modulo m dengan

0 (nol). Selanjutnya, kita harus membuktikan bahwa bilangan dalam barisan (*) masing-masing kongruen modulo m dengan tepat satu dari 1,2,3,..., (m-1).

Andaikan ada dua suku dari barisan (*) yang kongruen modulo m, misalnya

ra  sa(mod m) dengan . Karena (a,m) 1, maka kita dapat menggunakan sifat penghapusan a dari kekongruenan itu, sehingga diperoleh

r  s(mod m). Tetapi, karena ra dan sa adalah suku-suku dari barisan (*), maka

r dan s adalah sisaan terkecil modulo m, sehingga r = s. Hal ini kontradiksi dengan pengandaian bahwa , sehingga pengandaian tersebut tidak benar. Jadi, tidak ada dua bilangan dari barisan (*) yang kongruen modulo m. Ini berarti bahwa bilangan dalam barisan (*) masing-masing kongruen modulo m dengan tepat satu dari 1, 2, 3,.., (m-1).

Teorema 2 (Teorema kecil Fermat) Jika p suatu bilangan prima dan (a,p) =1 untuk suatu bilangan bulat a, maka ap-1  1(mod p).

 

Teorema ini dapat dinyatakan dengan cara lain, “jika p adalah bilangan prima dan a prima relatif dengan p maka a^p-1 – 1 dapat dibagi oleh p”.

Bukti:

Ambil sembarang bilangan prima p dan bilangan bulat a sedemikian (a,p) =1. Menurut teorema 1, sisaan terkecil mod p dari a, 2a, 3a, ..., (p-1)a adalah suatu permutasi dari 1, 2, 3, ...,(p-1) sehingga hasilkalinya akan kongruen mod p juga, yaitu a.2a.3a....(p-1)a   (mod p).

Dengan demikian,

a^p-1    (p-1) (mod p)

                         a^p-1(p-1)  (p-1) (mod p).

Karena p dan (p-1) saling prima, maka kita dapat menggunkan sifat penghapusan (p-1)  dari kekongruenan terakhir ini, sehingga diperoleh

a^p-1  1 (mod p), dimana a^p-1  1 (mod p) bermakna sama   (a^p-1 - 1).

Contoh 2.1:

Jika p=5 dan a=2 berarti (2,5)=1 maka a^p-1 – 1 = 2^5-1 – 1= 2⁴ – 1 = 16 – 1 = 15 dapat dibagi oleh p=5 atau dapat ditulis 16  1 (mod 5).

Teorema Fermat tersebut diatas dapat dinyatakan secara lebih umum dengan menghilangkan syarat (a,p)=1 sebagai berikut.

Teorema 3 Jika p suatu bilangan prima, maka ap  a(mod p) untuk himpunaniap bilangan bulat a.

 

Bukti:

Ambil sembarang bilangan prima p dan sembarang bilangan bulat a, maka (a,p)=1 atau (a,p)=p. Jika (a,p)=1, menurut teorema 2 diperoleh bahwa

a^p-1  1(mod p). Selanjutnya, jika kedua ruas dikalikan a, maka diperoleh

a^p  a(mod p). Jika (a,p)=p maka a, sehingga a 0(mod p) dan

a^p  0(mod p) pula. Jadi, a^p  a(mod p).

Bukti alternatif teorema 3 dapat digunakan dengan menggunakan induksi matematika pada a sebagai berikut:

Jika a = 1, maka pernyataan 1^p  1(mod p) jelas benar. Demikian pula jika diambil a=0, pernyataan pun benar. Selanjutnya, diasumsikan bahwa pernyataan kekongruenan a^p  a(mod p) benar untuk suatu bilangan bulat positif a. Kemudian, harus ditunjukkan bahwa untuk a+1, yaitu (a+)^p  (a+)(mod p) juga benar. Hal ini ditunjukkan sebagai berikut. Menurut teorema binom,

(a+)^p = a^p + a^p-1 + a^p-2 + ... + a^p-k + ... + a+1 (**)

Selanjutnya, =  = , dan

k    = p(p-1)(p-2)...(p-k+1)  0 (mod p). Ini berarti k  atau . Tetapi, k  yang berarti j untuk suatu j yang memenuhi

. Hal ini tidak mungkin. Jadi, haruslah  atau

   0 (mod p) untuk . Ini berarti koefisien untuk a^p-k pada persamaan (**) semuanya kelimpatan p, sehingga diperoleh

(a+1)^p   (a+1)^p  (mod p)

 a^p (mod p) + 1 (mod p)

 a (mod p) + 1 (mod p)

 (a+1) (mod p).

Dengan demikian, dapat disimpulkan bahwa, jika p suatu bilangan prima, maka

a^p   a (mod p) untuk himpunaniap bilangan bulat a.

Selanjutnya, jika a suatu bilangan bulat negatif, bukan lagi menjadi persoalan, sebab untuk himpunaniap bilangan bulat negatif a berlaku bahwa a  r(mod p) dengan . Jadi, a^p  r^p(mod p)  r(mod p)  a(mod p).

Contoh 3.1:

Ambil a=8 dan p=3, (a,p)=1 atau p – a. Dengan demikian, diperoleh

a^p-1 = 8^3-1 = 8² = 64. Tetapi, 64  1(mod 3) (sesuai dengan teorema 2). Menurut teorema 3, 8³ = 512 dan 512  8(mod 3).

Teorema Fermat mempunyai banyak kegunaan khususnya dalam mengembangkan teori bilangan. Salah satu kegunaan teori Fermat dijelaskan dalam contoh berikut.

Contoh 3.2:

Menurut teori Fermat, 5¹⁰  1(mod 11), yaitu dari hasil a^p-1  1(mod p). Untuk a=5 dan p=1, (a,p) = 1. Selanjutnya, 5³⁸ = 5^(10)(3)+8 = (5¹⁰)³(5²)⁴, sehingga

5³⁸  (1)³(3)⁴(mod 11)

       81(mod 11)

       4(mod 11)

Jadi, 5³⁸ dibagi 11 bersisa 4.

Kontraposisi dari teorema 3 juga benar, yaitu jika untuk suatu bilangan bulat a, dengan a^p  a(mod p) maka p bukan bilangan prima. Jadi, teori Fermat dapat pula digunakan untuk menguji apakah suatu bilangan bulat merupakan bilangan komposit atau bilangan prima.

Contoh 3.4:

Apakah 117 suatu bilangan prima atau komposit?

Penyelesaian:

Misalkan kita mengambil bilangan bulat a=2 (boleh a bilangan lain). Kita akan memeriksa kebenaran 2¹¹⁷ = 2^7(16)+5 x 2⁵, dan 2⁷ = 128  11(mod 117), sehingga  2¹¹⁷  (11⁶ x 2⁵)(mod 117)

                                     121⁸ x 2⁵(mod 117)

                                     4⁸ x 2⁵(mod 117)

                                     2²¹(mod 117)

                                     (2⁷)³(mod 117)

                                     11³(mod 117)

                                     121 x 11(mod 117)

                                     4 x 11(mod 117)

                                     44(mod 117)

Jadi, diperoleh 2¹¹⁷  44(mod 117), dan ini berarti 2¹¹⁷  2(mod 117). Dengan demikian, 117 bukan bilangan prima tetapi bilangan komposit. Kenyataan memang 117 = 13 x 9.

Teorema 4 Misalkan p dan q adalah dua bilangan prima yang tidak sama. Jika ap  a(mod q) dan aq  a(mod p), maka apq  a(mod pq).

 

 Bukti:

Menurut teorema 3, (a^p)^q  a^q(mod p) sebab p suatu bilangan prima. Selanjutnya, karena diketahui a^q  a(mod p) maka kekongruenan tersebut menjadi (a^q)^p  a (mod p) ini berarti bahwa p  (a^pq - a). Menurut teorema 3 lagi, (a^p)^q  a^q(mod q) sebab q suatu bilangan prima. Selanjutnya karena diketahui bahwa a^p  a(mod q) maka kekongruenan tersebut menjadi:

a^pq  a(mod q). Ini berarti q   (a^pq - a). Menurut teorema terdahulu, jika

p  (a^pq - a) dan q   (a^pq - a) serta (p,q) = 1 maka pq  (a^pq - a), akibatnya

a^pq  a(mod pq).

Teorema 4 menunjukkan bahwa kebalikan pernyataan teori Fermat (teori 2) tidak benar yakni, jika hubungan a^n-1 = 1(mod n) untuk suatu bilangan bulat a, maka n tidak perlu suatu bilangan prima.

Contoh 4.1:

Tunjukkanlah bahwa 2³⁴⁰  1(mod 341).

Penyelesaian:

Perhatikan bahwa 341 = 31 x 11 dan 2¹⁰ = 1024 = 31 x 33 + 1.

Dengan demikian, 2¹⁰  1(mod 31). Selanjutnya, 2¹¹ = 2 x 2¹⁰  2(mod 31) dan 2¹⁰ = 1024 = 31 x 3 x 11 + 1, sehingga 2¹⁰  1(mod 11). Jika kedua ruas dipangkatkan dengan 3 maka 2³⁰  1(mod 11)  2³¹  2(mod 11). Menurut teorema 4, 2¹¹  2(mod 31) dan 2³¹  2(mod 11).

Karena 11 dan 31 bilangan prima maka (2¹¹)³¹  2(mod 11 x 31), sehingga

2³⁴¹  2(mod 341). Jika kedua ruas dibagi 2, diperoleh 2³⁴⁰  1(mod 341).

Contoh 4.2:

Berapa sisa jika 20⁵⁰ dibagi 7?

Penyelesaian:

Diketahui 20  -1(mod 7), sehingga 20⁵⁰  (-1) ⁵⁰(mod 7) atau

20⁵⁰  1(mod 7). Jadi, 20⁵⁰ dibagi 7 bersisa 1.

Contoh 4.3:

Berapa sisa jika 3¹⁹ dibagi 14?

Penyelesaian:

3¹⁹ (mod 14)  3^{3 x 6 + 1} (mod 14)

                             (3³) ⁶.3¹(mod 14)

                             ((27) ⁶ x 3)(mod 14)

                             (2 x 14 - 1) ⁶ x 3¹ (mod 14)

                             (-1) ⁶ x 3¹ (mod 14)

                             3(mod 14)

Jadi, 3¹⁹  3 (mod 14), sehingga sisa pembagian 3¹⁹ oleh14 adalah 3.

Contoh 4.4:

Berapa sisa jika 3¹⁹⁹⁰ dibagi 41?

Penyelesaian:

3¹⁹⁹⁰ (mod 41)   3^{4 x 497 + 2} (mod 41)

                                 ((3⁴) ⁴⁹⁷ x 3²)(mod 41)

                                 ((81) ⁴⁹⁷ x 3² ) (mod 41)

                                 ((2 x 41 - 1) ⁴⁹⁷ x 3²)(mod 41)

                                 ((-1) ⁴⁹⁷ x 9)(mod 41)

                                 (-9)(mod 41)

                                 (41-9)(mod 41)

                                 32(mod 41)

Jadi, sisa pembagian 3¹⁹⁹⁰ jika dibagi 41 adalah 32.

Dalam sejarah matematika, minat terhadap bilangan berbentuk 2ⁿ – 2 sudah lama ada. Bilangan berbentuk 2ⁿ – 2 ditemukan oleh matematikawan Cina dan menyatakan bahwa n suatu bilangan prima jika n (2ⁿ – 2), dan kenyataannya kriteria ini benar untuk semua bilangan prima n<340. Contoh 4.1 meruntuhkan pernyataan ini. Kita memperoleh fakta bahwa

341   (2³⁴¹ – 2),walaupun 341 bukan bilangan prima. Suatu bilangan komposit m yang memenuhi m   (2^m – 2) dinamakan bilangan prima semu. Beberapa diantara bilangan prima semu adalah 341, 561, 645 dan 1105.

B.  Teori Wilson

Dalam buku yang dipublikasikan tahun 1770, seorang matematikawan Inggris Edward Waring menyatakan bahwa muridnya menemukan bahwa

(p-1)!+1 habis dibagi oleh p berapapun p yang merupakan bilangan prima. Namun, tidak ada dari keduanya yang mampu membuktikannya. Tahun 1771, Joseph Lagrange membuktikan teorema ini, yang selanjutnya dikenal sebagai teorema Wilson.

Teorema Wilson adalah salah satu teorema yang menggambarkan sifat dari bilangan prima. Menurut teorema wilson,   adalah bilangan prima jika  membagi  . Begitu pula sebaliknya suatu bilngan   yang membagi    maka bilangan tersebut adalah prima.

Secara formal teorema Wilson ditulis sebagai berikut:

Teorema Wilson Bilangan bulat   adalah prima jika dan hanya jika

 

Bukti: Karena teorema ini berbentuk bi-implikasi, kita harus membuktikannya secara dua arah:

ü  Diberikan bilangan prima   maka dapat dibentuk himpunan bilangan  yang merupakan grup atas perkalian modulo  . Karena   grup maka himpunaniap elemen  mempunyai elemen invers a^-1  G   aa^-1  1(mod p). Jika   maka:

.

 atau

Diperoleh nilai   atau  . Dengan kata lain hanya 1 dan  yang merupakan invers terhadap dirinya sendiri sedangkan elemen lainnya pada   mempunyai invers yang berbeda. Itu berate himpunaniap elemen di   berbentuk pasangan   dengan  kecuali untuk 1 dan  . Jika semua elemen   dikalikan, diperoleh

 

Dengan kata lain hasil dari   pada   adalah   dengan  . Dapat disimpulkan

ü  Diketahui   andaikan   kompositetidak prima maka   mempunyai faktor prima    dengan  . Itu berarti    membagi   dan juga membagi  , Jelas itu suatu mustahil. Dengan kata lain   adalah hal yang mustahil jika   tidak prima.

Contoh soal:

1.      Berapakah sisa   jika dibagi  ?

Jawab:

Dengan teorema Wilson didapat 

2.      Tentukan sisa pembagian (7-1)! dibagi 7.

Jawab:

(7-1)! = 6! = 1.2.3.4.5.6.

Selain 1 dan 6, maka kita akan menyusun pasangan-pasangan yang merupakan invers modulo.  ,  Oleh karenanya, kita lakukan grouping sebagai berikut: 6! = 1.(2.4).(3.5).6 Jadi,  .

Selain mod 7, kalian juga bisa coba misalnya dengan modulo yang lain, misalnya modulo 11.

C.  Teorema Euler

Teorema Euler adalah Teorema dasar aritmatika yang menyatakan bahwa himpunan bilangan bulat positif N dapat difaktorkan ke dalam bentuk N = p1q1,p2q2, ...pnqn, dimana pi adalah bilangan prima yang berbeda, dan qi adalah bilangan bulat positif. Berapa banyak bilangan bulat 1 ≤ k ≤ N yang ada sehingga

gcd (k, N) = 1? Hal ini tampaknya sulit untuk menghitung secara langsung, jadi alih-alih, mempertimbangkan bilangan bulat 1 ≤ k ≤ N sedemikian rupa sehingga gcd (k, N) ≠ 1 (k adalah bilangan bulat habis dibagi pi untuk beberapa i). Dari bilangan bulat kurang dari N, NP1 dari mereka adalah kelipatan p1. Demikian pula, NP2 dari bilangan bulat kurang dari N merupakan kelipatan dari p2.

Namun, kami telah menyertakan kelipatan p1p2 di kedua perangkat ini, sehingga pendataan ganda. Prinsip Inklusi dan Pengecualian (PIE) adalah suatu metode untuk menghitung jumlah elemen dalam himpunan tumpang tindih. Untuk i = 1 sampai n, biarkan Pi adalah himpunan bilangan bulat kecil dari atau sama dengan N yang merupakan kelipatan dari pi. Kemudian jumlah bilangan bulat yang merupakan kelipatan dari pi | Pi | = NPI. Jumlah bilangan bulat yang merupakan kelipatan dari pipj adalah | Pi ∩ Pj | = Npipj.

Hal ini berlaku secara umum: untuk himpunaniap bagian S dari {1,2, ..., n}, jumlah bilangan bulat yang merupakan kelipatan dari Πs ∈ Sps ini | ⋂ s ∈ SPs | = NΠs ∈ Sps.Kemudian, himpunan bilangan yang memenuhi gcd (k, N) = 1 adalah persis himpunan bilangan yang bukan kelipatan dari himpunaniap pi, maka tidak di salah satu himpunan Pi. Dengan Prinsip Inklusi dan Pengecualian, Jumlah bilangan bulat kecil daripada N yang koprima ke N adalah Euler phi fungsi φ (N).

Euler Teorema: Jika gcd (a, N) = 1, maka ≡ 1 (mod N).

 

Bukti:

Misalkan S adalah himpunan bilangan bulat yang koprima N. Maka aS adalah himpunan (mungkin diulang) bilangan bulat dari bentuk {sebagai: s ∈ S} diambil modulo N. Pertama, kami menunjukkan bahwa tidak ada pengulangan. Jika ada ulangan, yaitu, ASI ≡ ASJ (mod N), maka modulo aritmatika properti H menyiratkan si ≡ sj (mod N). Tapi karena himpunaniap elemen dalam S lebih kecil dari N, hal ini tidak mungkin. Kedua, kami menunjukkan bahwa aS terkandung dalam S. Hal ini benar karena diberikan s unsur S, 1 ≤ gcd (s, N) ≤ gcd (a, N) × gcd (s, N) = 1 × 1 = 1 , sehingga gcd (s, N) = 1 yang menunjukkan bahwa s unsur S. Karena aS adalah seperangkat φ (N) elemen yang berbeda yang terkandung dalam S, yang juga satu himpunan φ (N) unsur yang berbeda, sehingga perangkat ini adalah sama modulo N.

Sejak himpunan berisi persis sama elemen modulo N, produk dari semua unsur aS sama dengan produk dari semua elemen S modulo N. Oleh karena itu,
 as1 ⋅ ⋅ ... ⋅ as2 asφ (N) ≡ s1 s2 ⋅ ⋅ ⋅ ... sφ (N) (modN). Sejak s1 s2 ⋅ ⋅ ⋅ ... sφ (N) adalah koprima ke N, maka dari Modulo Aritmatika Properti H yang:

aφ (N) ≡ 1 (mod N).

Catatan: Himpunan S juga disebut sistem residu modulo N. Berkurang Bekerja

Contoh
1. Apa unit digit dari 9753?

Solusi:

Menemukan unit digit nomor adalah himpunan dengan bekerja modulo 10. Dengan teorema Euler, kita hanya perlu menentukan nilai eksponen

753 Modulo φ (10) = 10 × (1-12) × (1-15) = 4. Kita hanya perlu menentukan nilai eksponen 53 Modulo φ (4) = 4 × (1-12) = 2. Kemudian

537539753 ≡ 137.193 131 ≡  3729 9 (mod 2) (mod 4) (mod 10)

Catatan: Pendekatan lain adalah untuk menyadari bahwa 9 N (mod10) adalah urutan 9,1,9,1,9,1, ... yang memiliki periode 2. Karena paritas (kesamaan nilai) eksponen aneh, ini berarti digit terakhir adalah 9.

2.  [Fermat Little Teorema] Jika p adalah prima dan integer, menunjukkan bahwa ap ≡ a (mod p).

Solusi:

Perhatikan bahwa jika p adalah prima, maka φ (p) = p × (1-1p) = p-1. Oleh karena itu, oleh teorema euler, jika gcd (a, p) = 1, maka ap-1 ≡ 1 (mod p) ⇒ ap ≡ a (mod p). Bagaimana nilai-nilai sedemikian rupa sehingga gcd (a, p) ≠ 1? Dalam hal ini, akan menjadi kelipatan p, jadi ap ≡  0p 0 ≡ a (mod p).

3.    Tunjukkan bahwa jika n adalah bilangan bulat ganjil, maka n membagi 2n! -1

Solusi:

Teorema Euler Himpunan tiap bilangan bulat dan  bilangan bulat positif  yang koprima ke  maka

Dengan teorema Euler, n membagi 2φ (n) -1. Karena φ (n) <n, kita memiliki n! = Φ (n) ⋅ k untuk suatu bilangan bulat k. Sejak 2n! -1 = (2φ (n) -1) (2φ (n) ⋅ (k-1) +2 φ (n) ⋅ (k-2) + ... +1),

Perhatikan jika  prima maka , teorema euler berubah menjadi teorema kecil fermat. Dengan demikian kita bisa menganggap teorema euler sebagai generalisasi teorema kecil fermat
Dalam teori bilangan, teorema Euler (juga dikenal sebagai teorema Fermat-Euler) yang menyatakan bahwa jika n adalah bilangan bulat positif, dan a adalah prima relatif, maka aφ(n) =1(mod n) dimana φ(n) melambangkan fungsi phi Euler.

Contoh

ü  1, 2, 4, 5, 7, 8 adalah sistem residu tereduksi modulo 9.
Jumlah bilangannya harus 6 yaitu 1,2,4,5,7,8 Perhatikan juga bahwa bilangan-bilangan itu harus koprima dengan 9, dan mempunyai kelas sisa yang berbeda satu sama lain.

ü  -5, 7, 14, 19, 29, 35 adalah sistem residu tereduksi modulo 9.
Perhatikan bahwa semua bilangannya koprima dengan 9.
Tiap bilangan juga memiliki kelas sisa yang berbeda:
-5=4(mod 9) =7(mod9)
14= 5(mod 9)
19=1(mod 9)
29=2(mod 9)
35=8(mod 9)

Jika ada    adalah sistem residu yang tereduksi modulo n,
dan a  adalah integer positif dimana  , maka:  juga merupakan sistem residu yang tereduksi modulo n.

Bukti

Karena    juga merupakan sistem residu tereduksi modulo n, maka tentunya sisa residu positif dari   adalah dalam urutan tertentu (acak). Dengan mengalikan elemen-elemen tersebut, kita dapatka:


Karena   , maka 

Untuk  positif integer dan adalah integer dimana , maka:

Perhatikan apabila  adalah bilangan prima ( ), maka FLT berlaku:

Konsep yang melandasi bukti teorema euler adalah sistem residu yang tereduksi.

Sistem Residu yang tereduksi (reduced residue system) modulo  adalah kumpulan  bilangan integer yang totatif (koprima) dengan  dan tidak ada 2 integer yang mempunyai kelas sisa yang sama.

Contoh 1
1, 2, 4, 5, 7, 8 adalah sistem residu tereduksi modulo 9.
Perhatikan bahwa . Jadi, jumlah bilangannya harus 6. .
Perhatikan juga bahwa bilangan-bilangan itu harus koprima dengan 9, dan mempunyai kelas sisa yang berbeda satu sama lain.

Contoh 2
-5, 7, 14, 19, 29, 35 adalah sistem residu tereduksi modulo 9.
Perhatikan bahwa semua bilangannya koprima dengan 9.
Tiap bilangan juga memiliki kelas sisa yang berbeda:
-5 4 (mod 9)____7 7 (mod 9)_____14 5 (mod 9)
19 1 (mod 9)____29 2 (mod 9)____35 8 (mod 9)

Contoh 3
1, 5, 7, 11, 13 BUKAN sistem residu tereduksi modulo 12, karena jumlah bilangannya ada 5, padahal

Teorema Jika adalah sistem residu yang tereduksi modulo , dan adalah integer positif dimana , maka:  juga merupakan sistem residu yang tereduksi modulo .

Contoh 4
-7, 11, 13, 17 BUKAN sistem residu tereduksi modulo 12, karena
-7 dan 17 memiliki kelas sisa yang sama.
-7 5 (mod 12). 17 5 (mod 12)_

Contoh 5
-7, 11, 13, 51 BUKAN sistem residu tereduksi modulo 12, karena 51 dan 12 bukan koprima.

Bukti:
(i) Bukti bahwa tiap elemen  koprima dengan .
     Karena  dan , maka .
(ii) Bukti bahwa tiap dua elemen memiliki kelas sisa yang berbeda.
     Asumsikan bahwa ada dua elemen, misalkan dan yang kongruen modulo . Karena , maka: Namun, kita tahu bahwa dan inkongruen (karena keduanya berasal dari sistem residu tereduksi). Oleh karenanya, kontradiksi dengan asumsi awal. Jadi, dan yanginkongruenmodulo .
Dari poin (i) dan (ii) dapat disimpulkan bahwa juga merupakan sistem residu yang tereduksi modulo .

Contoh 6

1, 3, 5, 7 merupakan sistem residu tereduksi modulo 8.
Karena gcd( 3, 8 ) = 1, maka: 3, 9, 15, 21 juga merupakan sistem residu tereduksi modulo 8. Karena juga merupakan sistem residu tereduksi modulo , maka tentunya sisa residu positif dari adalah dalam urutan tertentu (acak). Dengan mengalikan elemen-elemen tersebut, kita dapatkan:

Karena , maka

 TERBUKTI.

Contoh 7
Tentukan digit terakhir dari .

Jawab:
Mencari digit terakhir sama seperti mencari sisanya juga dibagi 10.
Sesuai dengan teorema euler, maka:

Jadi, kita kelompokkan berdasarkan 4.

 Digit terakhirnya adalah 1.

Contoh 8
Berapakah sisa pembagian jika dibagi .
Jawab:
Sesuai teorema Euler,

Maka, kita kelompokkan berdasarkan 24.

Selanjutnya, gunakan cara biasa:

___________

Jadi, sisanya adalah 11.

Contoh 9
Tentukan solusi kongruensi dari .
Jawab:

Teorema euler berguna untuk mencari invers modulo:

Berarti, adalah invers dari modulo .

Dengan demikian,

Contoh 10
Jika  koprima dengan 32760, buktikan bahwa:

Jawab:
Perhatikan bahwa
Teorema Euler menyatakan bahwa:
__, maka
__, maka
__, maka
__, maka

Karena 8, 9, 5, 7, dan 13 semuanya koprima, maka

Terbukti.

Contoh 11

Jika dan  koprima, buktikan bahwa:

Jawab:
Menurut teorema Euler:

(i) ,maka
(ii) ,maka
Sesuai dengan sifat keterbagian,

Terbukti.Bottom of Form

BAB III

PENUTUP

A.  Kesimpulan

Himpunanelah kita mempelajari teorema-teorema di atas dapat ditarik kesimpulan bahwa:

1.      Teorema Fermat

(Teorema kecil Fermat) Jika p suatu bilangan prima dan (a,p) =1 untuk suatu bilangan bulat a, maka ap-1  1(mod p).

 

2.      Teorema Wilson

Teorema Wilson Bilangan bulat   adalah prima jika dan hanya jika

 

3.     

Teorema Euler Jika m merupakan suatu bilangan bulat positif dan (a,m) = 1, maka    1 (mod m)

Teori Euler

4.      Antara teorema Fermat, Wilson, dan Euler memiliki keterkaitan antara satu sama lain, dimana teorema Wilson mengembangkan teorema Fermat, dan teorema Euler mengembangkan 2 teorema yaitu teorema Fermat dan teorema Wilson.

B.  Saran

Untuk lebih memahami materi mengenai teorema Fermat, Wilson, dan Euler sebaiknya menggunakan berbagai referensi. Namun sebelum mempelajari ketiga teorema ini maka terlebih dahulu kita harus mempelajari dan memahami mengenai materi bilangan prima dan kekongruenan agar lebih memudahkan dalam memahami teorema ini.

DAFTAR PUSTAKA

Arif Muhammad, dkk. 2009. Pengenalan Teori Bilangan. Makassar: CV. Andira Karya Mandiri

Anonim. 2012. Theorema Euler. Tersedia: http://odeittelkom.blogspot.com/2012/04/theorema-euler.html

Anonim. 2010. Theorema Terakhir Euler. Tersedia: http://mathmagics.wordpress.com/2010/02/06/teorema-terkahir-fermat/

Anonim. 2008. Theorema Terakhir Euler. Tersedia: https://ariaturns.wordpress.com/2008/09/13/teorema-terakhir-fermet/