teori bilangan

MODUL 3

KONGRUENSI

Gatot Muhsetyo

PENDAHULUAN

       Dalam modul Kongruensi ini diuraikan tentang sifat-sifat dasar kongruensi, keterkaitan kongruensi dengan fpb dan kpk, sistem residu yang lengkap dan system residu yang tereduksi, teorema Euler, teorema kecil Fermat, dan teorema Wilson.

       Kongruensi merupakan kelanjutan dari keterbagian, dan didefinisikan berdasarkan konsep keterbagian. Dengan demikian penjelasan dan pembuktian teorema-teoremanya dikembalikan ke konsep keterbagian. Bahan utama kongruensi adalah penggunaan bilangan sebagai modulo, dan bilangan modulo ini dapat dipandang sebagai perluasan dari pembahasan yang sudah ada di sekolah dasar sebagai bilangan jam, dan pada tingkat lebih lanjut disebut denga bilangan bersisa.

       Dengan bertambahnya uraian tentang sistem residu, pembahasan tentang kongruensi menjadi lebih lengkap sebagai persiapan penjelasan teorema Euler, teorema kecil Fermat, dan teorema Wilson, serta bahan penerapan yang terkait dengan teorema-teorema kongruensi dan teorema Euler.

KOMPETENSI UMUM

       Kompetensi umum dalam mempelajari modul ini adalah mahasiswa mampu memahami konsep kongruensi, penerapannya,  hubungannya dengan konsep keterbagian,  pengembangannya dalam system residu, dan peranannya dalam penjabaran teorema Euler, teorema kecil Fermat, dan teorema Wilson.

KOMPETENSI KHUSUS

       Kompetensi khusus dalam mempelajari modul ini adalah mahasiswa mampu menjelaskan konsep kongruensi dan sifat-sifatnya, konsep sistem residu yang lengkap dan sistem residu yang tereduksi, peranan  fpb dan kpk  dalam  pengembangan  sifat-sifat

kongruensi, pembuktian dan penerapan teorema Euler, teorema kecil Fermat, dan teorema Wilson.

SUSUNAN KEGIATAN BELAJAR

       Modul 3 ini terdiri dari dua kegiatan belajar. Kegiatan Belajar pertama adalah Kongruensi, dan Kegiatan Belajar kedua adalah Sistem Residu. Setiap kegiatan be;lajar memuat Uraian, Contoh/Bukan Contoh, Tugas dan Latihan, Rambu-Rambu Jawaban Tugas dan Latihan, Rangkuman, dan Tes Formatif. Pada bagian akhir modul ini ditempatkan Rambu-Rambu Jawaban Tes Formatif 1 dan Tes Formatif 2.

PETUNJUK BELAJAR

1. Bacalah Uraian dan Contoh dengan cermat dan berulang-ulang  sehingga  Anda  benar-

    benar memahami dan menguasai materi paparan.

2. Kerjakan Tugas dan Latihan yang tersedia secara mandiri. Jika dalam kasus atau tahap-

    An tertentu Anda mengalami  kesulitan  menjawab/menyelesaikan, maka lihatlah Ram-

    bu-Rambu  Jawaban  Tugas  dan Latihan. Jika   langkah  ini belum  banyak  membantu

    Anda keluar dari kesulitan, maka mintalah bantuan tutor Anda,  atau  orang  lain  yang

    lebih tahu.

3. Kerjakan Tes  Formatif  secara  mandiri,  dan  periksalah  Tingkat  Kemampuan  Anda

    dengan jalan mencocokkan jawaban Anda dengan  Rambu-Rambu  Jawaban  Tes For-

    matif. Ulangilah pengerjaan Tes Formatif  sampai  Anda  benar-benar  merasa  mampu

    mengerjakan semua soal dengan benar.

MODUL 3

KEGIATAN BELAJAR 1

KONSEP DASAR KONGRUENSI

Uraian

       Kongruensi merupakan bahasa teori bilangan karena pembahasan teori bilangan bertumpu kongruensi. Bahasa kongruensi ini diperkenalkan dan dikembangkan oleh Karl Friedrich Gauss,  matematisi paling terkenal dalam sejarah, pada awal abad sembilan belas, sehingga sering disebut  sebagai Pangeran Matematisi (The Prince of Mathematici-

ans). Meskipun Gauss tercatat karena temuan-temuannya di dalam geometri, aljabar, analisis, astronomi, dan fisika matematika, ia mempunyai minat khusus di dalam teori bilangan dan mengatakan bahwa “mathematics is the queen of sciences, and the theory of numbers is the queen of mathematics” . Gauss merintis untuk meletakkan teori bilangan modern di dalam bukunya Disquistiones Arithmeticae pada tahun 1801.

       Secara tidak langsung kongruensi sudah dibahas sebagai bahan matematika di sekolah dalam bentuk bilangan jam atau bilangan bersisa. Peragaan dengan menggunakan

tiruan jam dipandang bermanfaat karena peserta didik akan langsung praktek untuk lebih mengenal adanya system bilangan yang berbeda yaitu system bilangan bilangan jam, misalnya  bilangan jam duaan, tigaan, empatan, limaan, enaman, dan seterusnya.

     Kemudian, kita telah mengetahui bahwa bilangan-bilangan bulat lebih dari 4 dapat di “reduksi” menjadi 0, 1, 2, 3, atau 4 dengan cara menyatakan sisanya jika bilangan itu dibagi dengan 5, misalnya 13 dapat direduksi menjadi 3 karena 13 dibagi 5 bersisa 3, 50 dapat direduksi menjadi 0 karena 50 dibagi 5 bersisa 0, dan dalam bahasa kongruensi dapat dinyatakan sebagai 13 ≡ 3 (mod 5) dan 50 ≡ 0 (mod 5).

Definisi 3.1

       Ditentukan p,q,m adalah bilangan-bilangan bulat dan m  0

       p disebut kongruen dengan q  modulo m, ditulis  p ≡ q (mod m), jika  dan  hanya jika

       m │ p - q .

      Jika  m │ p – q maka ditulis  p ≡ q (mod m), dibaca p tidak kongruen q modulo m.

Contoh 3.1

10 ≡ 6 (mod 2) sebab 2 │ 10 – 6 atau 2 │ 4

13 ≡ -5 (mod 9) sebab 9 │ 13 – (-5) atau 9 │ 18

107 ≡ 2 (mod 15) sebab 7 │ (107 – 2) atau 15 │ 105

Teorema 3.1

       Jika p dan q adalah bilangan-bilangan bulat, maka p ≡ q (mod m) jika dan hanya jika

       ada bilangan bulat t sehingga p = q + tm

Bukti :

       Jika p ≡ q (mod m), maka m │ p – q . Ini berarti bahwa ada suatu bilangan bulat t se-

       hingga tm = p – q, atau p = q + tm.

       Sebaliknya, jika ada suatu bilangan bulat t yang  memenuhi  p = q + tm,  maka dapat

       ditentukan bahwa   tm = p – q,  dengan  demikian m │ p – q , dan akibatnya  berlaku

       p ≡ q (mod m).

             

Contoh 4.2

23 ≡ -17 (mod 8) dan 23 = -17 + 5.8

Teorema 3.2

       Ditentukan m adalah suatu bilangan bulat positif.

       Kongruensi modulo m memenuhi sifat-sifat berikut :

(a)    Sifat Refleksif.

Jika p adalah suatu bilangan bulat, maka p ≡ p (mod m) 

(b)   Sifat Simetris.

Jika p dan q adalah bilangan-bilangan bulat sedemikian hingga p ≡ q (mod m),

maka p ≡ q (mod m)

(c)    Sifat Transitif.

Jika p, q, dan r adalah bilangan-bilangan bulat sedemikian hingga p ≡ q (mod m)

dan q ≡ r (mod m), maka p ≡ r (mod m)

Bukti :

(a)    Kita tahu bahwa m │ 0, atau m │ p – p , berarti p ≡ q (mod m)

(b)   Jika p ≡ q (mod m), maka m │ p – q , dan menurut definisi keterbagian, ada suatu

bilangan bulat t sehingga tm = p – q, atau (-t)m = q – p , berarti  m │ q – p.

Dengan demikian  q ≡ p (mod m)

(c)    Jika p ≡ q (mod m) dan q ≡ r (mod m) , maka m│p – q dan m│q – r, dan menurut

definisi keterbagian, ada bilangan-bilangan bulat s dan t sehingga sm = p – q dan

tm = q – r . Dengan demikian dapat ditentukan  bahwa p – r = (p – q) + (q – r) =

sm + tm = (s + t)m. Jadi m│ p – r , dan akibatnya q ≡ r (mod m) 

Contoh 4.3

5 ≡ 5 (mod 7) dan -10 ≡ -10 (mod 15) sebab 7│5 – 5 dan 15│-10 – (-10)

27 ≡ 6 (mod 7) akibatnya  6 ≡ 27 (mod 7) sebab 7│6 – 27 atau 7│(-21)  

45 ≡ 21 (mod 3) dan 21 ≡ 9 (mod 3), maka 45 ≡ 9 (mod 3) sebab 3│45 – 9 atau 3│36

Teorema 3.3

       Jika  p, q, r, dan m  adalah  bilangan-bilangan  bulat  dan   m > 0  sedemikian  hingga

       p ≡ q (mod m) , maka :

       (a) p + r ≡ q + r (mod m)

       (b) p – r ≡ q – r (mod m)

       (c) pr ≡ qr (mod m)

Bukti :

       (a) Diketahui p ≡ q (mod m), maka m│ p – q . Selanjutnya dapat  ditentukan  bahwa

            p – q = (p + r) – (q + r) ,  berarti m│p – q berakibat  m │ (p + r) – (q + r). Dengan

            demikian p + r ≡ q + r (mod m).

       (b) Kerjakan, ingat bahwa p – q = (p – r) – (q – r) .

       (c)  Diketahui p ≡ q (mod m),  maka m│ p – q ,  dan  menurut  teorema  keterbagian,  

             m │ r(p – q) untuk sebarang bilangan bulat r, dengan demikian m │ pr – qr.

             Jadi pr │qr (mod m) .

Contoh 4.4

43│7 (mod 6) , maka 43 +5│ 7 + 5 (mod 6) atau 48│12 (mod 6)

27 │6 (mod 7) , maka 27 – 4 │6 – 4 (mod 7) atau 23│ 2 (mod 7)

35│3 (mod 8) , maka 35.4│3.4 (mod 8) atau 140│12 (mod 8)

Contoh 4.5

Perhatikan bahwa teorema 3.3.(c) tidak bisa dibalik, artinya  jika   pr ≡ qr (mod m),  maka

belum tentu bahwa p ≡ q (mod m), misalnya 24 = 4.6 , 12 = 4.3, dan 24 ≡ 12 (mod 6) atau 4.6  ≡ 4.3 (mod 6), tetapi 6 ≡ 3 (mod 6).

Teorema 3.4

       Jika  p, q, r, s, m   adalah   bilangan-bilangan   bulat  dan  m > 0  sedemikian   hingga

       p ≡ q (mod m) dan r ≡ s (mod m) , maka :

       (a) p + r ≡ q + s (mod m)

       (b) p – r ≡ q – s (mod m)

       (c) pr  ≡  qs (mod m) 

Bukti :

       (a) p ≡ q (mod m) dan r ≡ s (mod m), maka m│ p – q dan m│ r – s , maka tentu ada

            bilangan-bilangan bulat  t dan u  sehingga tm = p – q  dan  um = r – s , dan

            (p + r) – (q + s) = tm – um = m(t – u). Dengan demikian m│(p + r) – (q + s), atau

            p + r ≡ q + s (mod m).

       (b) Kerjakan, perhatikan bahwa (p – r) – (q – s) = (p – q) – (r – s)

       (c) p ≡ q (mod m) dan r ≡ s (mod m), maka m│ p – q dan m│ r – s , maka tentu ada

            bilangan-bilangan bulat  t dan u  sehingga tm = p – q  dan  um = r – s , dan

            pr – qs = pr – qr + qr – qs = r(p – q) + q(r – s) = rtm + qum = m (rt + qu). Dengan

           demikian m │ pr – qs , atau pr  ≡  qs (mod m) 

Contoh 3.6

36 ≡  8(mod 7) dan 53 ≡ 4 (mod 7), maka 36 + 53 ≡ 8 + 4 (mod 7) atau 89 ≡ 12 (mod 7)

72  ≡7 (mod 5) dan 43 ≡ 3 (mod 5), maka 72 – 43 ≡  7 – 3 (mod 5) atau 29 ≡ 4 (mod 5)

15 ≡ 3 (mod 4) dan 23 ≡ 7 (mod 4) maka 15.23 ≡ 3.7 (mod 4) atau 345 ≡ 21 (mod 4)

Teorema 3.5

       (a) Jika p ≡ q (mod m), maka pr ≡ qr (mod mr)

       (b) Jika p ≡ q (mod m) dan d│m , maka p ≡ q (mod d)

Bukti :

(a) p ≡ q (mod m), maka sesuai definisi 3.1, m│p – q , dan menurut teorema 2.8 dapat

     ditentukan bahwa rm│r(p – q) atau mr│pr – qr , dan berdasarkan definisi 3.1 dapat

     ditentukan bahwa pr ≡ qr (mod mr)

(b) p ≡ q (mod m), maka sesuai definisi 3.1, m│p – q .

     Berdasarkan teorema 2.2, d│m dan m│p – q berakibat d│p – q, dan sesuai dengan

     Definisi 3.1, p ≡ q (mod d)  

Teorema 3.6

Diketahui bilangan-bilangan bulat a, p, q, m, dan m > 0.

(a) ap ≡ aq (mod m) jika dan hanya jika p ≡ q (mod m/(a,m))

(b) p ≡ q (mod m ) dan p ≡ q (mod m) jika dan hanya jika p ≡ q (mod  [m, m])

Bukti :

 (a)  ()

       ap ≡ aq (mod m), maka sesuai definisi 3.1, m│ap – aq, dan sesuai definisi 2.1

       ap – aq = tm untuk suatu t  Z, berarti a(p – q) = tm. Karena (a,m)│a dan  (a,m)│ m

       maka (a/(a,m)(p – q) = (m/(a,m)t, dan sesuai dengan  definisi 2.1,  dapat   ditentukan

       bahwa (m/(a,m)│(a/(a,m)(p – q).   Menurut teorema 2.14, (m/(a,m),a/(a,m)) = 1, dan

       menurut teorema 2.15, dari  (m/(a,m),a/(a,m)) = 1 dan (m/(a,m)│(a/(a,m)(p – q)  ber-

       akibat (m/(a,m)│(p – q). Jadi menurut definisi 3.1, p ≡ q (mod m/(a,m)) .

      ()

       p ≡ q (mod m/(a,m)), maka menurut teorema 3.5(a), ap ≡ aq (mod am/(a,m)).  Selan-

       jutnya, karena m │am/(a,m), dan ap ≡ aq (mod am/(a,m)),  maka  berdasarkan  pada

       teorema 3.5 (b) , ap ≡ aq (mod m).

(b)  Buktikan ! 

Contoh 3.7

8p ≡ 8q  (mod 6) dan (8,6) = 2, maka p ≡ q (mod 6/2) atau p ≡ q (mod 3)

12p  ≡ 12q (mod 16) dan (12,16) = 4, maka p ≡ q (mod 16/4) atau p ≡ q (mod 4)

Contoh 3.8

p ≡ q (mod 6) dan p ≡ q (mod 8), maka p ≡ q (mod [6,8]) atau p ≡ q (mod 24) 

p ≡ q (mod 16) dan p ≡ q (mod 24), maka p ≡ q (mod [16,24]) atau p ≡ q (mod 48)

Tugas dan Latihan

Tugas

Bacalah suatu buku teori bilangan, dan carilah teorema-teorema yang belum dibuktikan

dalam kegiatan belajar 1. Selanjutnya buktikan bahwa :

1. Jika p, q, t, dan m adalah bilangan-bilangan bulat sedemikian hingga t > 0, m > 0 dan  

    p ≡ q (mod m), maka p≡  q (mod m)

2. Jika p, q  Z dan m, m, …, m  Z sedemikian hingga

    p ≡ q (mod m) , p ≡ q (mod m) , …, dan p ≡ q (mod m) , maka

    p ≡ q (mod [m, m, …, m])

Latihan

1. Diketahui p, q, m adalah bilangan-bilangan bulat dan m > 0 sedemikian hingga

    p ≡ q (mod m)

    Buktikan : (p,m) = (q,m)

2. Buktikan

    (a) jika p adalah suatu bilangan genap, maka  p≡ 0 (mod 4)

    (b) jika p adalah suatu bilangan ganjil, maka p≡ 1 (mod 4)

3. Buktikan jika p adalah suatu bilangan ganjil, maka p≡ 1 (mod 8)

4. Carilah sisa positif terkecil dari 1! + 2! + … + 100!

    (a) modulo 2

    (b) modulo 12

5. Tunjukkan bahwa jika n adalah suatu bilangan genap  positif, maka:

       1 + 2 + 3 + … + (n + 1)  ≡ 0 (mod n)

    Bagaimana jika n adalah suatu bilangan ganjil positif ?

6. Dengan menggunakan induksi matematika, tunjukkan bahwa  4≡ 1 + 3n (mod 9)

    jika n adalah suatu bilangan bulat positif.

Rangkuman

Dari materi Kegiatan Belajar 1 ini, beberapa bagian yang perlu diperhatikan adalah defi- nisi kongruensi, teorema-teorema kongruensi, dan keterkaitan konsep kongruensi dengan keterbagian, fpb, dan kpk.

1. Definisi 3.1. p ≡ q (mod m) jika dan hanya jika  m │ p – q

2. Terdapat 6 teorema kongruensi.

     Teorema 3. 1 :  p ≡ q (mod m) jika dan hanya jika  p = q + tm

     Teorema 3.2  :  Kongruensi modulo m memenuhi sifat-sifat

(a)    refleksif: p ≡ p (mod m)

(b)   simetris : jika p ≡ q (mod m), maka q ≡ p (mod m)

(c)    transitif : jika p ≡ q (mod m) , q ≡ r (mod m), maka p ≡ q (mod m)

    Teorema 3.3  :   Jika p ≡ q (mod m), maka :

(a)    p + r ≡ q + r (mod m)

(b)   p – r ≡ q – r  (mod m)

(c)    pr ≡ qr (mod m)

    Teorema 3.4  :   Jika p ≡ q (mod m) dan r ≡ s (mod m), maka :

(a)    p + r ≡ q + s (mod m)

(b)   p – r ≡ q – s (mod m)

(c)    pr ≡ qs (mod m)

    Teorema 3.5  :     (a) p ≡ q (mod m) , maka pr ≡ qr (mod mr)

                                (b) p ≡ q (mod m) dan d │ m , maka p ≡ q (mod d)

    Teorema 3.6.  :    (a) ap ≡ aq (mod m), maka p ≡ q (mod m/(a,m))

                                (b) p ≡ q (mod m) dan p ≡ q (mod m) jika dan hanya jika                 

                                     p ≡ q (mod  [m, m])                 

Tes Formatif 1

1. Skor 10

    Nyatakan dengan B (Benar) atau S (Salah)

    (a) Jika p ≡ q (mod 7) , maka 3p ≡ 3q (mod 7)

 (b) Jika 2p ≡ 3q (mod 5), maka 10p ≡ 10q (mod 25)

    (c) Jika p ≡ q (mod 11), maka 23p – 44  ≡ 12q + 22 (mod 11)

 (d) Jika 2p ≡ 2q (mod 5), maka p ≡ q (mod 5)

 (e) Jika 4p ≡ 4q (mod 6), maka p ≡ q (mod 6)

 (f)  Jika 6p ≡ 9q (mod 15), maka 2p ≡ 3q (mod 5)

 (g) Jika p ≡ 2q (mod 24), maka p ≡ 2q (mod 8)

 (h) Jika p ≡ q (mod 7), maka 14p+ 8p – 21 ≡ 15p + 28 (mod 7)

 (i) Jika p ≡ q (mod 8) dan p ≡ q (mod 12), maka p ≡ q (mod 96)

 (j) Jika p ≡ q (mod 24) dan p ≡ q (mod 36), maka p ≡ q (mod 72)

2. Skor 10

    (a) Carilah 2 angka terakhir lambang bilangan decimal dari 28

    (b) Carilah 3 angka terakhir lambang bilangan decimal dari 23

3. Skor 20.

    Tunjukkan bahwa 1 + 2 + … + (n – 1)≡ 0 (mod n) jika n adalah suatu bilangan

    bulat positif atau jika n adalah habis dibagi 4.

    Apakah pernyataan masih benar jika n adalah genap tetapi tidak habis dibagi 4 ?

4. Skor 20

    Buktikan dengan induksi matematika bahwa  5≡ 1 + 4n (mod 16) jika n adalah suatu

    bilangan bulat positif

5. Skor 20

    Carilah sisa positif terkecil dari 1! + 2! + … + 100!

    (a) modulo 7

    (b) modulo 25

6. Skor 20

    Carilah sisa positif terkecil dari :

(a)    6! modulo 7

(b)   12! modulo 13

(c)    18! modulo 19

    (d)  22! modulo 23

    Cobalah menebak suatu teorema dari hasil-hasil jawaban Anda

MODUL 3

KEGIATAN BELAJAR 2

SISTEM    RESIDU

Uraian

       Sistem residu merupakan topik yang memberikan dasar untuk mengembangkan pembahasan menuju teorema Euler, dan pada bagian lain terkait dengan fungsi-fungsi khas (special functions) dalam teori bilangan.

       Bagian-bagian dari system residu meliputi system residu yang lengkap dan system residu yang tereduksi. Sebagai suatu system, system residu mempunyai sifat-sifat khusus yang terkait dengan bagaimana membuat system residu, atau mencari contoh yang memenuhi syarat tertentu.

Definisi 3.2

       Suatu  himpunan {x, x, … , x} disebut suatu  system  residu  lengkap  modulo m    

       Jika dan hanya jika  untuk  setiap y dengan  0 ≤ y < m , ada  satu  dan  hanya  satu x

       dengan 1 ≤ i < m , sedemikian hingga y ≡ x(mod m) atau x≡ y (mod m).

Perhatikan bahwa indeks dari x yang terakhir adalah m, dan hal ini  menunjukkan  bahwa

banyaknya unsur dalam suatu system residu lengkap modulo m adalah m. Dengan demikian, jika ada suatu himpunan yang banyaknya unsur kurang dari m atau lebih dari m , maka himpunan itu tentu bukan merupakan suatu system residu lengkap modulo m.

Selanjutnya, karena pasangan-pasangan kongruensi antara y dan xadalah tunggal,  maka

tidak ada y  yang  kongruen dengan dua unsur x yang berbeda, misalnya  x dan x,  dan

tidak ada x yang kongruen dengan dua nilai y. Dengan  demikian, tidak ada dua unsur x

yang berbeda dan kongruen, artinya xtidak kongruen xmodulo m jika i  j.

Contoh 3.9

1. Himpunan A = {6, 7, 8, 9} bukan merupakan  system  residu  lengkap  modulo 5 sebab

    banyaknya unsur A kurang dari 5

2. Himpunan A = {6, 7, 8, 9, 10} adalah suatu system residu lengkap modulo 5 sebab  un-

    tuk setiap y dengan  dengan  0 ≤ y < 5 , ada  satu  dan  hanya  satu x  dengan  1 ≤ i < 5  

    sedemikian hingga y ≡ x(mod 5) atau x≡ y (mod 5).

    Nilai-nilai y   yang   memenuhi 0 ≤ y < 5 , adalah  y = 0, y = 1, y = 2, y = 3, y = 4,  atau

    y = 5 . Jika kita selidiki, maka kita peroleh bahwa :

        10 ≡ 0 (mod 5)                          8 ≡ 3 (mod m)                          6 ≡ 1 (mod m)

        9   ≡ 4 (mod 5)                          7 ≡ 2 (mod m)

    Dengan  demikian  untuk setiap y dengan  y = 0, 2, 3, 4, 5 , ada satu  dan hanya satu x

    dengan x= 6, 7, 8, 9, 10 , sedemikian hingga x≡ y (mod m). Jadi A adalah suatu sis-

    tem residu lengkap modulo 5.

3. Himpunan B = {4, 25, 82, 107} adalah suatu system  residu  lengkap  modulo 4 sebab

    untuk  setiap y  dengan  0 ≤ y < 4 , ada  satu   dan   hanya   satu x  dengan   1 ≤ i < 4

    sedemikian hingga y ≡ x(mod 4) atau x≡ y (mod 4).  

         4   ≡ 0 (mod 4)                          82  ≡ 2 (mod 4)

         25 ≡ 1 (mod 4)                         107 ≡ 3 (mod 4)

4. Himpunan C = {-33, -13, 14, 59, 32, 48, 12} adalah suatu system residu  lengkap  mo-     

    dulo 7 sebab untuk  setiap y  dengan 0 ≤ y < 7 , ada  satu   dan   hanya   satu xdengan

    1 ≤ i < 7 sedemikian hingga y ≡ x(mod 7) atau x≡ y (mod 7).

         -33 ≡ 0 (mod 7)                          59 ≡ 3 (mod 7)                          48 ≡ 1 (mod 7)

         -13 ≡ 0 (mod 7)                          32 ≡ 3 (mod 7)                          12 ≡ 1 (mod 7)

          14 ≡ 0 (mod 7)                      

5. Himpunan D = {10, -5, 27} adalah bukan suatu system residu lengkap modulo 3 sebab

    Untuk suatu   y = 1 dengan 0 ≤ y < 3 , ada  lebih dari satu x(yaitu 10 dan -5)  sehingga

          10 ≡ 1 (mod 3)                          -5  ≡ 1 (mod 3)

6. Algoritma pembagian menunjukkan bahwa  himpunan  bilangan  bulat  0, 1, … , m – 1

    merupakan suatu system residu lengkap modulo m, dan disebut sebagai residu nonne-

    gatif terkecil modulo m.

Definisi 3.3

       Suatu  himpunan  bilangan  bulat {x, x, … , x} disebut suatu system residu tere-

       duksi modulo m jika dan hanya jika :

       (a) (x, m) = 1 , 1 ≤  i <  k

       (b)  x ≡   x(mod m) untuk setiap  i  j

       (c) Jika (y,m) = 1, maka y ≡ x(mod m) untuk suatu i = 1, 2, … , k

Contoh 3.10

1. Himpunan {1,5} adalah suatu system residu tereduksi modulo 6 sebab :

       (a) (1,6) = 1 dan (5,6) = 1

       (b) 5 ≡ 1 (mod 6)

2. Himpunan {17, 91} adalah suatu system residu tereduksi modulo 6 sebab :

       (a) (17,6) = 1 dan (91, 6) = 1

       (b) 91 ≡ 17 (mod 6)

Suatu system residu tereduksi modulo m dapat diperoleh dari system residu lengkap modulo m dengan membuang unsur-unsur yang tidak relative  prima  dengan m. Hal  ini dapat dilakukan karena {0, 1, 2, … , m – 1 } adalah suatu system residu yang lengkap modulo m karena  untuk  setiap y  dengan  y = 0, 1, 2, … , m – 1, ada satu dan hanya satu

x= 0, 1, 2, … , m – 1 sehingga y ≡ x(mod m) . Keadaan y ≡ x(mod m) selalu dapat terjadi  dengan memilih y = 0 dan x= 0, y = 1 dan x= 1, … , y = m – 1 dan x= m – 1 .

Karena unsur-unsur {0, 1, 2, … , m – 1} memenuhi tidak ada sepasang yang kongruen, maka setelah unsur-unsur yang tidak relative prima dengan m dibuang, yang tertinggal adalah unsur-unsur yang relative prima dengan m dan tidak ada sepasang yang kongruen.

Dengan demikian unsur-unsur yang tertinggal memenuhi definisi 3.2

Contoh 3.11

1. Himpunan A = {0, 1, 2, 3, 4, 5, 6, 7} adalah suatu sistem residu lengkap modulo 8.

    Unsur-unsur  A  yang   tidak   relative  prima  dengan  8   adalah  0, 2, 4, dan 6   karena

    (0,8) = 8 1, (2,8) = 2   1, (4,8) = 4 1, dan (6,8) = 2 1. Misalkan B  adalah  him-

    punan dari unsur-unsur yang tertinggal, maka B = {1, 3, 5, 7}, dan B merupakan suatu

    sistem residu tereduksi modulo 8 karena memenuhi definisi 3.2

2. Himpunan A = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19} adalah

    suatu system residu lengkap modulo 20. Jika unsur-unsur A yang tidak  relative  prima

    dengan 20 dibuang, yaitu 0, 2, 4, 5, 6, 8, 10, 12, 14, 15, 16, dan 18 , maka  unsur-unsur

    yang tertinggal adalah 1, 3, 7, 9, 11, 13, 17, dan 19, dan B = {1, 3, 7, 9, 11, 13, 17, 19}

    merupakan suatu system residu tereduksi modulo 20.

Defini 3.4

       Ditentukan m adalah suatu bilangan bulat positif.

       Banyaknya residu di dalam suatu system residu tereduksi modulo m disebut fungsi

       -Euler dari m, dan dinyatakan dengan (m).

Contoh 3.12

(2)  = 1 , diperoleh dari unsur 1

(3)  = 2 , diperoleh dari unsur-unsur 1 dan 2

(4)  = 2 , diperoleh dari unsur-unsur 1 dan 3

(5)  = 4 , diperoleh dari unsur-unsur 1, 2, 3, dan 4

(16) = 8, diperoleh dari unsur-unsur 1, 3, 5, 7, 9, 11, 13, dan 15           

(27) = 18, diperoleh dari unsur-unsur 1, 2, 4, 5, 7, 8, 11, 13, 14, 16, 17, 19, 20, 22, 23,

              25, dan 26

(p)  = p – 1 jika p adalah suatu bilangan prima

Perhatikan bahwa himpunan {1,2,3,4} merupakan suatu system  residu  tereduksi  modu- lo 5. Sekarang, coba Anda selidiki, jika masing-masing unsur himpunan dikalikan dikalikan dengan suatu bilangan yang relative prima dengan 5, misalnya 2, 3, atau 4, se- hingga diperoleh himpunan yang lain, maka apakah himpunan-himpunan yang lain terse- but merupakan system-sistem residu yang tereduksi modulo 5 ?

Teorema 3.7

       Ditentukan (a,m) = 1

       Jika {x, x, … , x} adalah suatu system residu modulo m yang lengkap atau  tere-

       duksi, maka {ax, ax, … , ax} juga  merupakan  suatu  system  residu  modulo  m

       yang lengkap atau tereduksi.

Bukti :

       Ditentukan bahwa  {x, x, … , x}  adalah  suatu  system  residu  modulo  m  yang 

       lengkap, maka xtidak kongruen xmodulo m jika x x. Harus dibuktikan bahwa

       axtidak kongruen axmodulo m jika i  j

       Misalkan dari unsur-unsur {ax, ax, … , ax} terdapat i  j sehingga  berlaku  hu-

       bungan ax≡ ax(mod m).

       Karena (a,m) = 1 dan ax≡ ax(mod m), maka menurut teorema 3.6 (a), dapat diten-

       tukan bahwa x≡ x(mod m), bertentangan dengan ketentuan  {x, x, … , x} me-

       rupakan suatu system residu lengkap  modulo m. Jadi tentu  ax tidak  kongruen ax

       modulo m.

       Selanjutnya buktikan jika {x, x, … , x}  adalah  suatu  system  residu  modulo m

       yang tereduksi.

Contoh 3.13

(a)    Himpunan A = {0, 1, 2, 3, 4, 5} adalah merupakan suatu system residu lengkap modulo 6. Jika masing-masing unsur A  dikalikan  dengan 5, yang mana (5,6) = 1,

dan setelah dikalikan dimasukkan sebagai unsur himpunan B, maka dapat ditentu-

kan bahwa B = {0, 5, 10, 15, 20, 25}. Himpunan B merupakan suatu system residu yang lengkap modulo 6 sebab setiap unsur B kongruen dengan satu dan ha-

nya satu y  {0, 1, 2, 3, 4, 5}, yaitu :

      0 ≡ 0 (mod 6)                        10 ≡ 4 (mod 6)                        20 ≡ 2 (mod 6)

      5 ≡ 5 (mod 6)                        15 ≡ 3 (mod 6)                        25 ≡ 1 (mod 6)

       (b) Himpunan A = {1, 5, 7, 11} adalah merupakan suatu system residu tereduksi mo-

            dulo 12. Jika masing-masing  unsur A  dikalikan  dengan 17  dengan  (17,12) = 1,

            dan setelah dikalikan dimasukkan sebagai unsur himpunan B, maka  dapat  diten-

            tukan bahwa B = {17, 85, 119, 187}. Himpunan B merupakan suatu system residu tereduksi modulo 12 sebab setiap unsur B relative prima dengan 12, dan tidak ada sepasang unsur B yang kongruen, yaitu :

                  (17,12) = (85,12) = (119,12) = (187,12) = 1

                  17 ≡ 85 (mod 12)                  17 ≡ 119 (mod 12)               17 ≡ 187 (mod 12)

                  85 ≡ 119 (mod 12)                85 ≡ 187 (mod 12)               119 ≡ 187 (mod 12)

Teorema 3.8 (Teorema Euler)

       Jika a, m  Z dan m > 0 sehingga (a,m) = 1, maka a≡ 1 (mod m)

Bukti :

      Misalkan bahwa {x, x, … , x} adalah suatu system residu tereduksi modulo m dengan unsur-unsur bilangan bulat positif kurang dari m dan relative prima dengan m, maka menurut teorema 3.7, karena (a,m) = 1, maka {ax, ax, … , ax} juga merupakan suatu system residu tereduksi modulo m. Dengan demikian, residu-residu positif terkecil dari  ax, ax, … , axadalah bilangan-bilangan bulat yang terdapat pada  x, x, … , x dengan urutan tertentu. Akibatnya kita dapat mengalikan semua suku dari masing-masing system residu tereduksi, sehingga diperoleh :

                    ax, ax, … , ax≡   x, x, … , x (mod m)

      Dengan demikian dapat ditentukan bahwa :

                     a x. x …  x  ≡  x. x …  x(mod m)

      Selanjutnya, {x, x, … , x} adalah suatu system residu tereduksi modulo m, maka   menurut  definisi 3.3, berlaku  (x, m) = 1. Berdasarkan   teorema 2.16, karena

      (x, m) = 1, yaitu (x,m) = ( x, m) =  …   (x, m) = 1, maka dapat ditentukan bahwa (x. x …  x, m) = 1.

      Dari dua keadaan :

                     a x. x …  x  ≡  x. x …  x(mod m) , dan

                      (x. x …  x, m) = 1

      dapat ditentukan berdasarkan teorema 3.6 (a) bahwa :

                       a≡ 1 (mod m)

Kita dapat menggunakan teorema Euler untuk mencari inversi modulo m.

Jika a dan m adalah relative prima, maka dapat ditentukan bahwa :

                         a≡ 1 (mod m) 

Dengan demikian :

                         a =  a. a ≡ 1 (mod m)      

Jadi a adalah inversi dari a modulo m.

Contoh 3.14

Carilah dua digit terakhir lambang bilangan desimal dari 23

Soal ini dapat dijawab dengan menyatakan maknanya dalam bentuk lain, yaitu sama dengan mencari x jika 23 ≡ x (mod 100). Kemudian bentuk 23 ≡ x (mod 100) dapat dipecah menjadi 23 ≡ x (mod 4) dan 23 ≡ x (mod 25).

(a) mencari x dari 23 ≡ x (mod 4).

     23 ≡ 3 (mod 4), maka 23≡ 9 (mod 4) ≡ 1 (mod 4), sehingga 23 = (23)

     Dengan demikian 23 = (23)≡ 1(mod 4), atau x ≡ 1 (mod 4)

(b) mencari x dari 23 ≡ x (mod 25)

     23 ≡ -2(mod 25), maka 23≡  4(mod 25), 23⁴ ≡  16(mod 25), 23⁸ ≡  6(mod 25),

     23¹⁶ ≡  11(mod 25), 23³² ≡  -4(mod 25), 23⁶⁴ ≡ 16(mod 25), 23¹²⁸ ≡ 6(mod 25), dan

     23²⁵⁶ ≡  11(mod 25)

     Dengan demikian 23⁵⁰⁰ = 23²⁵⁶.23¹²⁸.23⁶⁴.23³².23¹⁶.23⁴ ≡ 11.6.16.(-4).11.16 (mod 25)

                                           ≡ (-4).6.(-4).6 (mod 25) ≡ 576 (mod 25) ≡ 1,  (mod 25), yaitu

                                       x ≡ 1 (mod 25)

Dari hasil (a) dan (b), yaitu x ≡ 1 (mod 4) dan x ≡ 1 (mod 25), maka berdasarkan pada

teorema 3.6 (b) , x ≡ 1 (mod [4,25]) x ≡ 1 (mod 100)

Jadi 23 ≡ 1 (mod 100) , berarti dua digit terakhir lambang bilangan decimal dari 23 

adalah 01.

Contoh 3.15

Tunjukkan jika (n,7) = 1, n  N, maka 7 │ n⁷ – n

Jawab : Karena (n,7) = 1, maka menurut teorema Euler, n ≡ 1 (mod 7).

              Selanjutnya  , sehingga diperoleh n⁶ ≡ 1 (mod 6) , dan sesuai dengan

              definisi 3.1, 7│ n⁶ – 1 , dan akibatnya, sesuai dengan teorema 2.1, 7│n( n⁶ – 1)

              atau 7│n⁷ – 1

Contoh 3.16

Jika bulan ini adalah bulan Mei, maka carilah 239⁴³ bulan lagi adalah bulan apa

Jawab : Permasalahan ini dapat diganti dengan mencari x jika 239⁴³ ≡ x (mod 12).

             Karena (239,12) = 1, maka menurut teorema Euler, 239≡ 1 (mod 12).

             Selanjutnya , sehingga diperoleh 239⁴ ≡1 (mod 12).

             239⁴³ = (239⁴)¹⁰.239³ ≡ 1.239³ (mod 12) ≡ (-1)(-1)(-1) (mod 12) ≡ 11 (mod 12)

             Jadi x = 11, dengan demikian 239⁴³ bulan lagi adalah bulan April.

Contoh 3.16

Kongruensi linier ax ≡ b (mod m) dapat diselesaikan dengan menggunakan teorema Euler sebagai berikut :

             ax ≡ b (mod m)

             a^-1.ax ≡ a^-1 .b (mod m)

             x ≡  a^-1 .b (mod m)                      

Penyelesian 7x ≡ 3 (mod 12) adalah x ≡ 7.3 (mod 12) ≡ 7^4-1.3 (mod 12)                    ≡ 7³.3 (mod 12) ≡ 21 (mod 12) ≡ 9 (mod 12).

Teorema 3.9. Teorema Kecil Fermat

       Jika p  adalah  suatu  bilangan  prima  dan p tidak membagi a, maka a^p-1  ≡  1 (mod p)                  

Bukti :

       Karena p  adalah suatu bilangan prima  dan p  tidak  membagi a, maka  (p,a) = 1 (jika

       (p,a) 1 yaitu p dan a tidak relative  prima, maka p dan a mempunyai  factor selain 1

       dan p, bertentangan dengan sifat p sebagai bilangan prima).

       Selanjutnya, karena (p,a) = 1, maka menurut teorema 3.8, a≡ 1 (mod p).

       p adalah suatu bilangan prima, berarti dari bilangan-bilangan bulat :

               0, 1, 2, 3, … , p – 1

       yang tidak relative prima dengan p hanya 0 ≡ p (mod p), sehingga :

               {1, 2, 3, … , p – 1 }

       merupakan system residu tereduksi modulo dengan (p – 1) unsure, dengan demikian:

                 

       Karena  dan a≡ 1 (mod p),  maka a≡ 1 (mod p)

Contoh 3.17

Carilah suatu x jika 2²⁵⁰ ≡ x (mod 7) dan 0 ≤ x < 7

Jawab :

       Karena 7 adalah bilangan prima, (2,7) = 1, dan , maka :

               2≡ 1 (mod 7)

               2⁶    ≡ 1 (mod 7)

               2²⁵⁰ = (2⁶)⁴¹.2⁴ ≡ 1.2⁴ (mod 7) ≡ 16 (mod 7) ≡2 (mod 7)

       Jadi : x = 2

Contoh 3.18

Carilah satu digit terakhir lambang bilangan basis 10 dari:

(a) 2⁵⁰⁰

(b) 7¹⁷⁵

Jawab :

       Untuk mencari digit terakhir dari lambang bilangan basis 10, permasalahan dapat

       dipandang sebagai mencari x jika y ≡ x (mod 10). Karena 2.5 = 10 dan (2,5) = 1,

       maka y ≡ x (mod 10) dapat dinyatakan sebagai :

              y ≡ x (mod 2) dan y ≡ x (mod 5)       

       (a) 2 ≡ 0 (mod 2), maka 2⁵⁰⁰ ≡ 0, 2, 4, 6, 8, … (mod 2)

            (5) = 4 dan (2,5) = 1, maka 2⁴ ≡ 1(mod 5),  sehingga

             2⁵⁰⁰ = (2⁴)¹²⁵ . 1 (mod 5)  ≡ 1, 6, 11, 16, 21, … (mod 5)

             Dengan demikian 2⁵⁰⁰ ≡ 6 (mod 2) dan 2⁵⁰⁰ ≡ 6 (mod 5), berarti

       2⁵⁰⁰ ≡ 6 (mod 10). Satu digit terakhir lambang bilangan basis 10 dari 2⁵⁰⁰  ada-

       lah 6.

 (b) 7 ≡ 1(mod 2), maka 7¹⁷⁵  ≡ 1, 3, 5, … (mod 2)

       (5) = 4 dan (7,5) = 1, maka 7⁴ ≡ 1 (mod 5), sehingga 

        7¹⁷⁵ = (7⁴)⁴³.7³ ≡  7³ (mod 5) ≡ 2.2.2 (mod 5) ≡ 8 (mod 5) ≡ 3 (mod 5)

        ≡ 3, 8, 13, 18, … (mod 5).

        Dengan demikian  7¹⁷⁵ ≡ 3 (mod 2) dan 7¹⁷⁵ ≡ 3 (mod 5), berarti

        7¹⁷⁵  ≡ 3 (mod 10. Satu digit terakhir lambing bilangan basis 10 dari 7¹⁷⁵ ada-

        lah 3. 

Teorema 3.10

       Jika (a,m) = 1, maka hubungan ax ≡ b (mod m) mempunyai selesaian

       x = a^-1 .b  + tm

Bukti :

       Dari hubungan  ax ≡ b (mod m) , ruas kiri dan kanan perlu dikalikan dengan

       suatu factor sehingga koeffisien a menjadi 1. Pilihan factor adalah   a^-1  

       sebab sesuai dengan teorema Euler,  a^-1.a  = a ≡ 1 (mod m).

                ax ≡ b (mod m)

                a^-1  .a x  ≡ a^-1  . b (mod m)

                a x ≡ a^-1  . b (mod m)

                x ≡ a^-1  . b (mod m)

       Karena tm ≡ 0 (mod m) untuk setiap bilangan bulat t, maka :

               x ≡  ≡  a^-1  . b + tm (mod m)

       Jadi x = a^-1 .b + tm  adalah selesaian ax ≡ b (mod m)

Teorema 3.11. Teorema Wilson

       Jika p adalah suatu bilangan prima, maka (p – 1)! ≡ -1 (mod p)

Bukti :

       Untuk p = 2, kita dapat menentukan bahwa (p – 1)! = 1! = 1 ≡ -1 (mod 2),

       dengan demikian teorema benar untuk p = 2.

       Untuk p > 2, berdasarkan teorema 3.9 dan teorema 3.10, jika ax ≡  1 (mod p),

       dan (a,p) = 1, maka x ≡ a^-1 , a dan x disebut saling inverse modulo p.

       Dengan demikian, setiap bilangan a yang memenuhi 1 ≤ a ≤  p – 1, tentu ada a^*

       yang memenuhi 1 ≤ a^* ≤  p – 1, sehingga a.a^* ≡ 1 (mod p).

       Perhatikan perkalian bilangan-bilangan:

                2.3. … ,(p – 3)(p – 2)

        yang dapat dipasang-pasangkan ke dalam (p – 3)/2 pasangan, masing-masing

        pasangan mempunyai hasil kali sama dengan 1 modulo p. Hal ini dapat dilaku-

        kan karena masing-masing bilangan relative prima dengan p, yaitu (a,p) = 1,

       sehingga masing-masing bilangan mempunyai inverse. Akibatnya :

                2.3. … ,(p – 3)(p – 2) ≡ 1 (mod p)

       sehingga :

                (p – 1)! = 1.2.3. … .(p – 3)(p – 2)(p – 1) ≡ 1.1.(p – 1) (mod p)

                             ≡ p – 1 (mod p)

                (p – 1)! ≡  – 1 (mod p)

Contoh 3.19

(7 – 1)! = 6! = 1.2.3.4.5.6 = 1.(2.4).(3.5).6 = 1.8.15.6 ≡ 1.1.1.6 (mod 7) ≡ – 1(mod 7)

(13 – 1)! = 12! = 1.2.3.4.5.6.7.8.9.10.11.12 = 1.(2.7).(3.9).(4.10).(5.8).(6.11).12

              = 1.14.27.40.40.66.12 ≡ 1.1.1.1.1.1.12 (mod 13) ≡ – 1 (mod 13)

Teorema 3.13

       Jika n adalah suatu bilangan bulat positif sehingga (n – 1)!  ≡ – 1 (mod n),

       maka n adalah suatu bilangan prima. 

Buktikan !          

Teorema 3.12 dan teorema 3.13 memberikan petunjuk kepada kita untuk mengguna-

kan teorema-teorema itu dalam pengujian keprimaan suatu bilangan.

Contoh 3.20

(15 – 1)! = 14! = 1.2.3.4.5.6.7.8.9.10.11.12.13.14 = 1.2.(15).4.6.7.8.9.10.11.12.13.14

               ≡ 0 (mod 15)

(15 – 1)! = 14! tidak kongruen dengan – 1 (mod 15), maka 15 bukan suatu bilangan

prima.

Tugas dan Latihan

Tugas

Carilah suatu buku teori bilangan yang membahas tentang Metode (p – 1) Pollard

Jelaskan Metode Pollard itu untuk apa, dan uraikan secara lengkap.

Berikan paling sedikit satu contoh penggunaan Metode (p – 1) Pollard

Latihan

1. Carilah satu contoh  system  residu  tereduksi  modulo 16  yang  mempunyai  dua

    unsure negative.

2. Jelaskan mengapa S = {-9, -33, 37, 67} bukan merupakan system residu tereduksi

    modulo 10.

3. Carilah satu contoh system residu A yang lengkap modulo 12. Tambah  setiap un-

    sur dalam system residu dengan sebarang bilangan kelipatan 12, sehingga  dipero-

    leh himpunan B. Selidiki apakah B merupakan system residu lengkap modulo 12.

4. Carilah sisanya jika 11³⁵ dibagi 13.

5. Jika hari ini hari Rabu, maka carilah hari apa 97¹⁰¹ hari lagi.

6. Carilah dua digit terakhir lambang bilangan desimal dari 39¹²⁵

7. Carilah suatu bilangan bulat positif terkecil x jika 61! ≡ x – 1 (mod 71)

8. Carilah suatu bilangan bulat positif terkecil x jika  7x ≡ 9 (mod 20)

Rangkuman

Secara keseluruhan, bagian-bagian utama yang perlu diperhatikan dalam Kegiatan Belajar 2 adalah Definisi dan Teorema, yaitu:

1. Definisi 3.2 tentang system residu yang lengkap modulo m

2. Definisi 3.3 tentang system residu tereduksi modulo m

3. Definisi 3.4 tentang fungsi -Euler

5. Teorema-Teorema :

    3.7. Jika (a,m) = 1 sedemikian hingga {x, x, … , x} adalah suatu system residu

           yang lengkap atau tereduksi, maka {ax, ax, … , ax}  juga  merupakan  sis-

           tem residu yang lengkap atau tereduksi modulo m.

    3.8. Teorema Euler

           Jika a, m  Z dan m > 0 sehingga (a,m) = 1, maka a≡ 1 (mod m)

    3.9. Teorema Kecil Fermat

            Jika p adalah suatu  bilangan  prima  dan p tidak membagi a, maka

            a^p-1 ≡ 1 (mod p)

    3.10. Jika (a,m) = 1, maka hubungan ax ≡ b (mod m) mempunyai selesaian

             x = a^-1 .b  + tm

    3.11.Teorema Wilson

            Jika p adalah suatu bilangan prima, maka (p – 1)! ≡ -1 (mod p)

Tes Formatif 2

1. Skor 10

    Carilah suatu x jika 5x ≡ 7 (mod 23)

2. Skor 10

    Tunjukkan jika n adalah suatu bilangan komposit dan n  4 , maka

    (n – 1) ! ≡ 0 (mod n)

3. Skor 10

    Tunjukkan jika p adalah suatu bilangan prima ganjil, maka

    2(p – 3)! ≡ – 1 (mod p)

4. Skor 10

    Tunjukkan jika n adalah suatu bilangan ganjil dan n tidak membagi tiga, maka

    n² ≡ 1 (mod 24)

5. Skor 10

    Tunjukkan jika p dan q adalah bilangan-bilangan prima yang berbeda, maka

    p^q-1 + q^p-1 ≡ 1 (mod pq)

6. Skor 10

    Tunjukkan jika p adalah suatu bilangan prima ganjil, maka

    1²3² … (p – 4)²(p – 2)² ≡ (-1)^(p+1)/2(mod p)

7. Skor 10

    Tunjukkan jika p adalah suatu bilangan prima ganjil dan p ≡ 3(mod 4), maka

    ((p – 1)/2)! ≡  1(mod p)

8. Skor 20

    Carilah bilangan-bilangan bulat positif n jika n⁴ + 4ⁿ adalah bilangan prima

9. Skor 10

    Tunjukkan jika p adalah suatu bilangan prima dan a adalah suatu bilangan bulat,

     maka p │ (a^p + (p – 1)!a)

  

    

Daftar Kepustakaan

Niven, I., Zuckerman, H.S., & Montgomery, H.L. (1995). An Introduction to The The-

       Ory of Numbers. New York : John Wiley & Sons.

Redmond, D. (1996). Number Theory. New York : Marcel Dekker.

Rosen, K.H. (1993). Elementary Number Theory and Its Applications. Massachusetts:

       Addison-Wesley.