teori residu

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 yyangmemenuhi 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   relativeprima dengan 8 adalah 0, 2, 4, dan 6karena

    (0,8) = 81, (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 xx. 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 menurutdefinisi 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 relativeprima 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)

                ax ≡ 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.

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 yyangmemenuhi 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   relativeprima dengan 8 adalah 0, 2, 4, dan 6karena

    (0,8) = 81, (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 xx. 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 menurutdefinisi 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 relativeprima 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)

                ax ≡ 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.