Modul perkuliahan

Dalil 3.2

Jika b ≡ c (mod m), maka (b,m) = (c,m)

Bukti.

Karena b ≡ c (mod m) berarti m │ b-c

Berdasarkan teorema sebelumnya dalam keterbagian, sehingga:

Bila (b,m) │m dan m │ b-c maka (b,m) │b-c

Bila (b,m) │b dan (b,m) │ b-c maka (b,m) │c.

Jadi bila (b,m) │m dan (b,m) │c maka (b,m) adalah pembagi persekutuan m dan c.

Hal ini berarti (b,m)│(c,m). ..................(1)

c b (mod m) berarti m │c-b

Berdasarkan teorema sebelumnya dalam keterbagian, sehingga:

Bila (c,m) │m dan m │ c-b maka (c,m) │c-b

Bila (c,m) │c dan (c,m) │ c-b maka (c,m) │b.

Jadi bila (c,m) │m dan (c,m) │b maka (c,m) adalah pembagi persekutuan m dan b.

Hal ini berarti (c,m)│(b,m). ..................(2)

Dari (1) dan (2) dapat disimpulkan (b,m) = (c,m).

• Definisi 3.4

Misal { x₁, x₂, x₃, x₄, ..., x_k}, selanjutnya himpunan tersebut dinamakan sistem residu modulo m yang tereduksi jika:

1. 
   (x_i,m) = 1
   
2. 
   x_i / x_j (mod m) untuk setiap i j.
   
3. 
   Jika (y,m) = 1 maka y x_i (mod m) untuk i = 1,2,3, .... k, 0 y < m
   

Contoh

1. 
   {1,5} adalah suatu sistem residu modulo 6 yang tereduksi, karena
   
2. 
   (1,6) = 1 dan (5,6) =1
   
3. 
   5 / 1 (mod 6)
   
4. 
   (7,6) =1 sehingga 7 1 (mod 6)
   

(11,6) = 1 sehingga 11 5 (mod 6)

(13,6) = 1 sehingga 13 7 (mod 6)

1. 
   {17,19} juga merupakan suatu sistem residu modulo 6 tereduksi.
   

Sistem ini dapat diperoleh dari sistem residu modulo 6 yang lengkap , dengan mengambil atau membuang anggota-anggotanya yang tidak relatip prima dengan 6.

{17, 30, 44, 91, -3, -14} adalah sistem residu lengkap modulo 6.

Anggota sistem yang tidak relatip prima dengan 6 adalah 30, 44, -3, -14. Setelah bilangan yang tidak relatip prima dengan 6 dibuang diperoleh 17 dan 91, sehingga (17,91) merupakan suatu sistem residu modulo 6 terduksi.

Ambil sistem residu modulo 6 lengkap yang lain, misalny {24, 49, 74, 33, 58, 83}. Dari himpunan tersebut yang tidak relatip prima dengan 6 adalah 24, 74, 33, dan 58, sehingga yang relatip prima dengan 6 adalah 49 dan 83.

Dengan demikian terlihat bahwa {49, 83} merupakan suatu sistem residu modulo 6 yang terduksi.

Berdasarkan contoh 2 di atas, jelaslah bahwa suatu sistem residu tereduksi modulo m dapat diperoleh dengan cara menghapus beberapa anggota sistem residu lengkap modulo m yang tidak relatip prima dengan m. Selanjutnya dapat diperhatikan bahwa semua sistem residu tereduksi modulo m akan mempunyai banyak anggota yang sama, yaitu suatu bilangan yang biasanya disimbulkan dengan fungsi -Euler.

• Teorema 3.2

1. 
   Bilangan (m) merupakan banyaknya biangan bulat positip kurang dari atau sama dengan m yang relatif prima denganm.
   
2. 
   Diberikan (a,m) = 1
   

Jika r₁, r₂, r₃, ... r_n sebagai sistem residu lengkap modulo m, maka ar₁, ar₂, ar₃, ... ar_n juga merupakan sistem residu lengkap modulo n.

Bukti

Menurut teorem keterbagian

Jika (a,m) = 1 maka (ar,m) = 1

Banyaknya bilangan ar₁, ar₂, ar₃, ... ar_n sama dengan r₁, r₂, r₃, ... r_n.

Oleh karena itu yang perlu ditunjukkan hanya

ar_i / ar_j (mod m), bila i j.

Akan tetapi menurut teorema yang lain terlihat bahwa ar_i ar_j (mod m), dan (a,m) = 1.

Dengan demikian haruslah i = j.

Dalil 3.3

Jika (a,m) = 1, maka a ^(m) 1 (mod m)

Contoh

1. 
   Untuk m = 4, (4) = 2
   
2. 
   Untuk m = 25, (25) = 20
   
3. 
   Untuk m = 3, (3) = 2
   
4. 
   Untuk m = 10, (10) = 4
   
5. 
   Tentukan 0 x < 5 sedemikiam sehingga 9¹⁰¹ x (mod 5)
   

Jawab.

Untuk m = 5, maka (5) = 4 sehingga

9⁴ x (mod 5) 1 (mod 5)

9¹⁰¹ = 9¹⁰⁰.9 ¹ (9⁴)²⁵.9 (mod 5)

9 (mod 5)

4 (mod 5)

diperoleh x = 4.

1. 
   Tentukan 0 x < 19 sedemikiam sehingga 43²⁰⁰ p (mod 19)
   

Jawab.

Untuk m = 19, maka (19) = 18 sehingga

43¹⁹ p (mod 5) 1 (mod 19) karena (43,19) = 1

43²⁰⁰ = 43¹⁹⁸.43 ² (43¹⁸)¹¹.43² (mod 19)

1. 43.43 (mod 19)

1.5.5 (mod 19)

6 (mod 19)

diperoleh p = 6.

1. 
   Carilah angka terakhir dari 2 ⁵⁰⁰.
   

Jawab

Untuk menentukan angka terakhir dari 2 ⁵⁰⁰. maka persoalan di atas harus dipangang sebagai y x (mod 10)

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

2 0 (mod 2), sehingga 2 ⁵⁰⁰ 0 (mod 2)

(5) = 4 dan 5 ┼ 2 maka 2 ⁴ 1 (mod 5)

2 ⁵⁰⁰ (2 ⁴ )¹²⁵ 1 (mod 5)

2 ⁵⁰⁰ 0 (mod 2) → 2 ⁵⁰⁰ 6 (mod 2)

2 ⁵⁰⁰ 1 (mod 5) → 2 ⁵⁰⁰ 6 (mod 5)

2 ⁵⁰⁰ 6 (mod 2) dan 2 ⁵⁰⁰ 6 (mod 5), maka

2 ⁵⁰⁰ 0 (mod 2.5) atau 2 ⁵⁰⁰ 6 (mod 10).

Jadi angka terakhir dari 2 ⁵⁰⁰ adalah 6.

1. 
   Carilah angka terakhir dari 3⁶⁰⁰.
   

Jawab

Untuk menentukan angka terakhir dari 3 ⁶⁰⁰. maka persoalan di atas harus dipangang sebagai y x (mod 10)

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

3 1 (mod 2), sehingga 3 ⁶⁰⁰ 1 (mod 2)

(5) = 4 dan 5 ┼ 3 maka 3 ⁴ 1 (mod 5)

3 ⁵⁰⁰ (3 ⁴ )¹⁵⁰ 1 (mod 5)

3 ⁶⁰⁰ 1 (mod 2) dan 3 ⁶⁰⁰ 1 (mod 5)

3 ⁶⁰⁰ 1 (mod 2.5) atau 3 ⁶⁰⁰ 1 (mod 10).

Jadi angka terakhir dari 3 ⁶⁰⁰ adalah 1.

BAB IV

KONGRUENSI LINEAR
4.1 Kongruensi Linear

Kongruensi mempunyai beberapa sifat yang sama dengan persamaan dalam Aljabar. Dalam Aljabar, masalah utamanya adalah menentukan akar-akar persamaan yang dinyatakan dalam bentuk f(x) = 0, f(x) adalah polinomial. Demikian pula halnya dengan kongruensi, permasalahannya adalah menentukan bilangan bulat x sehingga mememnuhi kongruensi

f(x) 0 (mod m)

Definisi 4.1

Jika r₁, r₂, r₃, ... r_m adalah suatu sistem residu lengkap modulo m. Banyaknya selesaian dari kongruensi f(x) 0 (mod m) adalah banyaknya r_i sehingga f(r_i) 0 (mod m)

Contoh:

1. 
   f(x) = x³ + 5x – 4 0 (mod 7)
   

Jawab

Selesaiannya adalah x = 2, karena

f(2) = 2³ + 5(2) – 4 = 14 0 (mod 7)

Ditulis dengan x 2 (mod 7).

Untuk mendapatkan selesaian kongruensi di atas adalah dengan mensubstitusi x dari 0, 1, 2, 3, ...., (m-1).

1. 
   x³ –2x + 6 0 (mod 5)
   

Jawab

Selesaiannya adalah x = 1 dan x = 2, sehingga dinyatakan dengan

x 1 (mod 5) dan x 2 (mod 5).

1. 
   x² + 5 0 (mod 11)
   

Jawab

Tidak mempunyai selesaian, karena tidak ada nilai x yang memenuhi kongruensi tersebut.

Bentuk kongruensi yang paling sederhana adalah kongruensi yang berderajat satu dan disebut dengan kongruensi linear. Jika dalam aljabar kita mengenal persamaan linear yang berbentuk ax = b, a 0, maka dalam teori bilangan dikenal kongruensi linear yang mempunyai bentuk ax b (mod m).

•