Modul perkuliahan

Menurut dalil keterbagian:

Jika m │a-b dan a-b │ aⁿ – bⁿ , maka a-b │ aⁿ – bⁿ

Jadi a-b │ aⁿ – bⁿ atau aⁿ bⁿ (mod m)

1. Dalil 3.2

Andaikan f adalah suatu polinomial dengan koefisien-koefisien bilangan bulat, Jika Jika a b (mod m), maka f(a) f(b) (mod m).

Bukti

Misal f(x) = t_nxⁿ + t_n-1x^n-1 + t_n-2x^n-2 + t_n-3x^n-3 + ..... + t₁x + t_o

Dengan t_n, t_n-1, t_n-2, t_n-3, t₁x, t_{o Z.}

Jika x = a maka f(a) = t_naⁿ + t_n-1a^n-1 + t_n-2a^n-2 + t_n-3a^n-3 + ..... + t₁a + t_o

Jika x = b maka f(b) = t_nbⁿ + t_n-1b^n-1 + t_n-2b^n-2 + t_n-3b^n-3 + ..... + t₁b + t_o

_{--------------------------------------------------------------------------------------------------- -}

f(a) – f(b) = t_n(aⁿ - bⁿ ) + t_n-1(a^n-1 - b^n-1 ) + t_n-2(a^n-3 –b^n-3) + ..... + t₁(a-b)

Dengan menggunakan sifat sebelumnya diperoleh

a b (mod m) atau m │a-b sehingga m │t₁(a-b)

a² b² (mod m) atau m │a²-b² sehingga m │t₂(a²-b²)

a³ b³ (mod m) atau m │a³-b³ sehingga m │t₃(a²-b²)

a⁴ b⁴ (mod m) atau m │a⁴-b⁴ sehingga m │t₄(a⁴-b⁴)

.............................................................................

aⁿ bⁿ (mod m) atau m │aⁿ-bⁿ sehingga m │t_n(aⁿ-bⁿ)

Dengan menggunakan definisi keterbagian pada bilangan bulat maka:

m │t_n(aⁿ-bⁿ) + t_n-1(a^n-1-b^n-1) + t_n-2(a^n-2-b^n-2) + t_n-3(a^n-3-b^n-3) + ..... + t₁(a¹-b¹), hal ini berarti

m │f(a) – f(b) atau f(a) f(b) (mod m)

Perhatikan beberapa contoh berikut ini!

Perhatikan beberapa contoh berikut ini!

1. 
   41 1 (mod 8) hal ini berarti 8 │ (41-1) atau 8 │40. Dengan kasus yang sama maka 8│ (1- 41) atau 8 │ - 40, sehingga 1 41 (mod 8).
   
2. 
   Karena 0 habis dibagi oleh sebarang bilangan bulat m, dan 0 dapat diperoleh dari hasil pengurangan sebarang dua bilangan yang sama, maka dapat ditentukan
   

1. 
   3│0 3 │5-5 5 5 (mod 3)
   
2. 
   7│0 7 │9-9 7 7 (mod 9)
   
3. 
   11│0 11 │20 20 20 (mod 9)
   

1. 
   25 11 (mod 7), karena 7 │25-11 atau 7 │14.
   

99 1 (mod 44), karena 44 │99-1 atau 44 │98

1. 
   26 1 (mod 5), karena 5 │26-1 atau 5│25
   

5 │25 5 │3.25 5 │10.25 5 │11.25 5 │100.25

Apakah 7 │2(30-2)

Apakah 7 │10(30-2)

Apakah 2.30 2.2 (mod 7)

Apakah 10.30 10.2 (mod 7)

1. 
   26 1 (mod 5), karena 5 │26-1 atau 5│25
   

36 1 (mod 5), karena 5 │36-1 atau 5│35

Apakah 5 │26+36 atau 5│1+1

Apakah 5 │(26+36) – (1+1) atau apakah 5 │62 –2

1. 
   13 3 (mod 5), karena 5 │13 –3
   

7 2 (mod 5), karena 5 │7–2, Apakah 91 6 (mod 5)

Jika kita perhatikan contoh di atas nampak bahwa dalam kongruensi berlaku sifat-sifat yang sama dalam pembagian bilangan bulat

3.2 Sistem Residu

Untuk membahas pengertian sistem residu, perlu diingat kembali tentang algoritma pembagian. Menurut teorema algoritma pembagian terdapat bilangan bulat q dan r sehingga untuk setiap bilangan bulat a dan m berlaku hubungan a = qm +r, dengan 0 ≤ 0 < r. Selanjutnya persamaan a = qm + r dapat dinyatakan dalm bentuk kongruensi a q (mod m) Akibatnya, setiap bilangan bulat a kongruen modulo m dengan salah satu bilangan bulat berikut: 0, 1, 2, 3, ..... , m-1. Dengan demikian jelaslah bahwa tidak ada sepasangpun dari bilangan-bilangan 0, 1, 2, 3, ..... , m-1 yang kongruen satu sama lain. Maka m buah bilangan tersebut dapat membentuk suatu sistem residu lengkap modulo m.

Definisi 3.3

1. 
   Jika x y (mod m) maka y disebut residu dari x modulo m.
   
2. 
   Misal A = { x₁, x₂, x₃, ..... , x_m }, disebut suatu sistem residu modulo m yanglengkap jika dan hanya jika untuk setiap y (0 y i sedemikian sehingga y x_i (mod m) atau x_i y (mod m) y
   

Contoh

1. 
   {6, 7, 8, 9, 10} adalah suatu sistem residu modulo 5 yang lengkap sebab untuk setiap
   

y dan (0 y <5 ) terdapat hubungan

10 0 (mod 5)

9 4 (mod 5)

8 3 (mo 5)

7 2 (mod 5)

6 1 (mod 5)

1. 
   {-5, 10, 27} adalah bukan suatu sistem residu modulo 5 yang lengkap sebab:
   

10 1 (mod 3)

27 0 (mod 3)

-5 1 (mod 3)

1. 
   {4, 25, 82, 107} adalah suatu sistem residu modulo 4 yang lengkap sebab untuk setiap
   

y dan (0 y <4 ) terdapat hubungan

4 0 (mod 4)

25 1 (mod 5)

82 2 (mo 5)

107 3 (mod 5)

6 1 (mod 5)

Misal diberikan kongruensi 5 2 (mod 3).

Bilangan-bilangan bulat yang bersisa 2 jika dibagi 3 adalah

2, (2 3), (2 2.3), (2 3.3), (2 4.3), ...... , (2 (m-1).3),

= 2, 5, 8, 11, 14, ....

= ....., -10, -7, -4, -1, 2, .....

Jika keduanya digabungan didapat himpunan

{ ...., -10, -7, -4, -1, 2, 5, 8, 11, ..... }

disebut sebagai himpunan residu (kongruen) 2 modulo 3 yang dilambangkan dengan [ 2 ], sehingga:

[ 2 ] = { ...., -10, -7, -4, -1, 2, 5, 8, 11, ..... }

Untuk modulo 3 terdapat tiga himpunan residu, yaitu:

[ 0 ] = { ...., -12, -9, -6, -3, 0, 3, 6, 9, .... }

[ 1 ] = { ...., -11, -8, -5, -2, 1, 4, 7, 8 , ..... }

[ 2 ] = { ...., -10, -7, -4, -1, 2, 5, 8, 11, ..... }

Ketiga himpunan residu modulo 3 membentuk suatu klas residu modulo 3 yaitu

{ [ 0 ], [ 1 ], [ 2 ] }

Dengan demikian untuk sebarang m Z dan m > 0, terdapat (m-1) himpunan residu modulo m dan kelas residu modulo m yang mempunyai (m-1) anggota, yaitu:

{ [ 0 ], [ 1 ], [ 2 ], [ 3 ], ..... , [ m-1 ] }

Dengan demikian untuk sebarang x,r Z dan 0 r < m, maka nilai-nilai x yang memenuhi hubungan x ≡ r (mod m) membentuk barisan aritmatika sebagai berikut:

....., r-4m, 2-3m, r-2m, 2-m, r, r+m, r+2m, r+3m, .....

•