Modul perkuliahan

Teorema 2.1

Persamaan Diophantine Linear ax + by = c dikatakan mempunyai selesaian jika dan hanya jika d │c dimana d = (a,b), Jika x_o dan y_o adalah sebarang selesaian khusus dari ax + by = c

Maka seluruh selesaian yang lain diberikan oleh x = x_o + (b/d)t dan y = y_o – (a/d)t, untuk sebarang bilangan bulat t.

Bukti.

Misal x_o dan y_o adalah selesaian persamaan yang diketahui, jika x’ dan y’ selesaian yang lain maka ax_o + by_o = c = ax’ + by’

a(x’ – xo) = b(yo – y’)

Dengan menggunakan teorema sebelumnya pada Algoritma Pembagian, dimana ada bilangan bulat relatif prima r dan s sehingga a = dr dan b = ds. Sehingga diperoleh r(x’-x_o) = s(y_o-y’). Bentuk ini memberikan fakta bahwa r │ s(y_o-y’). Dengan (r,s) = 1. dengan menggunakan Lemma Euclid diperoleh r │ (y_o-y’) atau dengan kata lain

(y_o-y’) = rt, untuk suatu bilangan bulat t.

x’-x_o = st.

x’ = x_o + st

x’ = x_o + (b/d)t .....................(1)

Dengan cara yang sama diperoleh

y_o – y’ = rt.

y’ = y_o - rt

y’ = y_o - (a/d)t ..................... (2)

dari (1) dan (2) dapat dilihat bahwa:

ax’ + by’ = a[x_o + (b/d)t] + b [y_o - (a/d)t]

= (ax_o + by_o) + (ab/d – ab/d)t

= c + 0

= c

Dengan demikian terdapat tak hingga selesaian dari persamaan Diophantine yang diberikan, sebut saja selesaian tersebut adalah t.

Contoh:

Tentukan selesaian persamaan Diophantine 172x + 20y = 1000.

Jawab

Dengan menggunakan Algoritma Euclid diperoleh (172,20) diperoleh

172 = (8) 20 + 12

20 = (1) 12 + 8

12 = (1) 8 + 4

8 = (2) 4

Sehingga (172,20) = 4.

Karena 4 │1000 maka 172x + 20y = 1000 mempunyai selesaian.

Dengan menggunakan jalan mundur pada langkah di atas diperoleh

4 = 12 – (1) 8

= 12 – (1) [20 – (1) 12]

= (2) 12 – (1) 20

= 2 [172 – (8)20] – 20

= (2) 172 + (-17) 20 atau

4 = (2) 172 + (-17) 20.

Kalikan kedua ruas dengan 250 diperoleh

1000 = 250.4 = 250 {(2) 172 + (-17) 20}

= 500.172 + (-4250) 20

didapat x = 500 dan y = -4250.

Semua selesaian dari persamaan 172x + 20y = 1000 adalah

x = 500 + (20/4)t = 500 + 5t

y = -4250 - (172/4)t = -4250 - 43t, untuk suatu bilangan bulat t.

Untuk memilih t, gunakan ketentuan 500 + 5t >0 dan –4250 –43t > 0 (mengapa?).

Akibat dari teorema di atas adalah, Jika (a,b) = 1 dan jika x_o dan y_o adalah selesaian khusus dari persamaan Diophantine linear ax + by = c, maka seluruh selesaian dari persamaan yang diberikan adalah x = x_o + bt dan y = y_o - at
2.4 Ciri-ciri Habis Dibagi

Banyak definisi dan dalil yang telah dipaparkan di atas yang berkaitan dengan keterbagian. Dalam banyak hal lain sering diperlukan suatu jawaban apakah suatu bilangan habis atau tidak jika dibagi oleh bilangan tertentu. Jawaban yang dimaksud menyangkut ciri-ciri suatu bilangan habis dibagi oleh bilangan yang lain. Ciri-ciri habis dibagi dikembangkan dan dijabarkan dari definisi dan dalil yang telah dibicarakan. Sebelum ciri-ciri habis dibagi dibahas, perlu dipaparkan beberapa sifat dasar keterbagian, hal ini dilakukan karena sangat diperlukan.

1. 
   k │ 0, untuk semua k Z. dan k ≠ 0.
   

Karena 0 = 0 dan 0 Z, maka jelaslah bahwa k │0.

Jadi 2 │0, 10 │0, -2 │0, 122│0 adalah semua pernyataan yang bernilai benar

1. 
   1 │ k, untuk semua k Z.
   

Karena k = k.1 dan k Z, maka jelaslah bahwa 1│k.

Jadi 1 │2, 1│20, 1│-10, 1 │22 0 adalah semua pernyataan yang bernilai benar

1. 
   k │ m → k │x.m untuk semua x Z.
   

Karena 0 = 0 dan 0 Z, maka jelaslah bahwa k │0.

Jadi 3 │6 → 3 │3.6, 3│10.6 , 3 │22 6 adalah pernyataan yang bernilai benar

1. 
   k │ m₁, k │m₂ → k │(m₁ ± m₂)
   

k │ m₁, k │m₂, ....... k │m_i → k │(m₁ ± m₂ ± ... ± m_i )

Jadi 3 │9, 3 │3 → 3 │(9+3) 3 │(9-3) adalah pernyataan yang bernilai benar

1. 
   k │ k, untuk semua k Z. dan k ≠ 0.
   

Karena k = 1.k dan 1 Z, maka jelaslah bahwa k │k.

Jadi 2 │2, -4│-4 , 1│1, 22 │22 adalah pernyataan yang bernilai benar

1. 
   (k,m) = 1 dan k │ mn → k │n.
   

Jadi (3,5) =1 dan 3 │5.9 → 3 │9.

(4,7) =1 dan 4 │7.4 → 4 │4.

(3,4) =1 dan 3 │4.12 → 3 │12.

1. 
   k │m, k │m + n → k │n
   

k │ m₁, k │m₂, ....... k │(m₁ + m₂ + ... + m_i ), → k │n

Jadi 3 │6, 3 │12, 3 │15, 3 │6 + 12 + 15 + 21 → 3 │21

Selanjutnya suatu bilangan asli

N = a_k.10^k + a_k-1.10^k-1 + a_k-2.10^k-2 + a_k-3.10^k-3 + a_k-4.10^k-4 + .... + a₁.10 + a_o

Ditulis dalam bentuk sederhana

N = (a_ka_k-1a_k-2a_k-3a_{k-4 ....}a₁a_o)

Ciri-ciri habis dibagi 2.

Perhatikan

N = a_k.10^k + a_k-1.10^k-1 + a_k-2.10^k-2 + a_k-3.10^k-3 + a_k-4.10^k-4 + .... + a₁.10 + a_o.

Dimana

2 │10 → 2 │a₁.10

2 │10 → 2 │10.10 → 2 │10² → 2 │a₂.10².

2 │10 → 2 │100.10 → 2 │10³ → 2 │a₃.10³.

2 │10 → 2 │1000.10 → 2 │10⁴ → 2 │a₄.10⁴.

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

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

2 │10 → ............................................................... 2 │a_k.10^k.

maka:

2 │a_k.10^k , 2 │a_k-110^k-1 , 2 │a_k-210^k-2 , 2 │a_k-310^k-3 , 2│a_k-410^k-4 , ...,

2 │a₁.10

2 │(a_k.10^k + a_k-110^k-1 + a_k-210^k-2 + a_k-310^k-3 +a_k-410^k-4 + ..... + a₁.10)

2 │N → 2 │ a_k.10^k + a_k-110^k-1 + a_k-210^k-2 + a_k-310^k-3 +a_k-410^k-4 + ..... + a₁.10 + a_o.

2 │ a_k.10^k + a_k-110^k-1 + a_k-210^k-2 + a_k-310^k-3 +a_k-410^k-4 + ..... + a₁.10

Jadi 2 │ a_o

Kesimpulan suatu bilangan asli N habis dibagi 2 jika angka terakhir lambang bilangan N (yaitu a_o) habis dibagi 2. Jadi haruslah a_o bilangan genap.

Contoh

1. 
   Selidiki apakah 6831078103 habis dibagi 2?
   

Jawab

Misal N = 6831078103, dan angka terakhir dari N adalah 3 (ganjil) dan 2 ┼ 3 , maka

2 ┼ 6831078103

1. 
   Selidiki apakah 435655433216 habis dibagi 2
   

Jawab

Karena angka terakhir dari N = 435655433216 adalah bilangan 6 (genap) dan

2 │6, maka 2 │435655433216.
Ciri-ciri habis dibagi 4.

Perhatikan

N = a_k.10^k + a_k-1.10^k-1 + a_k-2.10^k-2 + a_k-3.10^k-3 + a_k-4.10^k-4 + .... + a₁.10 + a_o.

Dimana

4│100 → 4 │10² → 4 │a₂.10²

4│100 → 4 │10.100 → 4 │10³ → 4│a₃.10³

4 │100 → 4 │100.100 → 4 │10⁴ → 4 │a₄.10⁴.

4 │100 → 4 │1000.100 → 4 │10⁵ → 4 │a₅.10⁵.

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

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

4 │100 → ............................................................... 4 │a_k.10^k.

maka:

4 │a_k.10^k , 4 │a_k-110^k-1, 4│a_k-210^k-2 , 4│a_k-310^k-3 , 4 │a_k-410^k-4 , ... ,

4 │a₂.10²

4 │(a_k.10^k + a_k-110^k-1 + a_k-210^k-2 + a_k-310^k-3 +a_k-410^k-4 + ..... + a₂.10²)

4 │N → 4 │( a_k.10^k + a_k-110^k-1 + a_k-210^k-2 + a_k-310^k-3 +a_k-410^k-4 + ..... + a₂.10² + a₁.10 + a_o.

4 │ (a_k.10^k + a_k-110^k-1 + a_k-210^k-2 + a_k-310^k-3 +a_k-410^k-4 + ..... + a₂.10²

Jadi 4 │ a₁.10 + a_o atau 4│ a₁a_o

Kesimpulan suatu bilangan asli N habis dibagi 4 jika bilangan yang dibentuk oleh dua angka terakhir dari lambang bilangan N habis dibagi 4.

Contoh

1. 
   Selidiki apakah 6831078103 habis dibagi 4
   

Jawab

Misal N = 6831078103 = (a₉a₈a₇a₆a₅a₄a₃a₂a₁a₀) ,

dan Dua angka terakhir dari N a₁ = 3 dan a_o = 0, sehingga diperoleh bilangan 30 dan dan 4 ┼ 30 , maka 4 ┼ 6831078103

1. 
   Selidiki apakah 435655433216 habis dibagi 4
   

Jawab

Misal N = 435655433216 = (a₁₁a₁₀a₉a₈a₇a₆a₅a₄a₃a₂a₁a_o ) , dan

Dua angka terakhir dari N a₁ = 1 dan a_o = 6, sehingga diperoleh bilangan 16 dan 4 │16 , maka 4│435655433216
Ciri-ciri habis dibagi 8.

Perhatikan

N = a_k.10^k + a_k-1.10^k-1 + a_k-2.10^k-2 + a_k-3.10^k-3 + a_k-4.10^k-4 + .... + a₁.10 + a_o.

Dimana

8 │1000 → 8 │10³ → 8 │ a₃.10³.

8 │1000 → 8 │10.1000 → 8 │10⁴ → 8 │ a_4.10⁴.

8 │1000 → 8 │100.1000 → 8 │10⁵ → 8 │ a_5.10⁵.

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

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

8 │1000 → ............................................................... 8 │a_k.10^k.

maka:

8 │a_k.10^k , 8 │a_k-110^k-1 , 8│a_k-210^k-2 , 8 │a_k-310^k-3 , 2 │a_k-410^k-4 , ...,

8 │a₃.10³

8 │( a_k.10^k + a_k-110^k-1 + a_k-210^k-2 + a_k-310^k-3 + a_k-410^k-4 + ....+ a₃.10³

8 │N → 8 │ a_k.10^k + a_k-110^k-1 + a_k-210^k-2 + a_k-310^k-3 +a_k-410^k-4 + ..... + a₁.10 + a_o.

8 │ a_k.10^k + a_k-110^k-1 + a_k-210^k-2 + a_k-310^k-3 +a_k-410^k-4 + ..... + a₃.10³

Jadi 8 │ a₂.10² +a₁.10¹ + + a₀ atau 8 │ a₂a₁a₀

Kesimpulan : suatu bilangan asli N habis dibagi 8 jika bilangan yang dibentuk oleh tiga angka terakhir dari lambang bilangan N habis dibagi 8.

Contoh

1. 
   Selidiki apakah 435655433242 habis dibagi 8
   

Jawab

Misal N = 435655433242 = (a₁₁a₁₀a₉a₈a₇a₆a₅a₄a₃a₂a₁a_o ) , dan

Tiga angka terakhir dari N adalah a₂ = 2 , a₁ = 4 dan a_o = 2, sehingga diperoleh bilangan 242 dan dan 8 ┼ 242.

Jadi 8 ┼ 435655433242

Ciri-ciri habis dibagi 16.

Perhatikan

N = a_k.10^k + a_k-1.10^k-1 + a_k-2.10^k-2 + a_k-3.10^k-3 + a_k-4.10^k-4 + .... + a₁.10 + a_o.

Karena

16 │10000 → 16 │10⁴ → 16 │a₄.10⁴

16 │10000 → 16 │10.10000 → 16 │10⁵ → 16 │a₅.10⁵.

16 │10000 → 16 │100.10000 → 16│10⁶ → 16 │a₆.10⁶.

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

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

16 │10000 → ............................................................... 16 │a_k.10^k.

maka:

16│a_k.10^k ,16│a_k-110^k-1 , 16│a_k-210^k-2 , 16│a_k-310^k-3 ,

16│a_k-410^k-4,.....,16│a₄.10⁴

16│(a_k.10^k + a_k-110^k-1 + a_k-210^k-2 + a_k-310^k-3 +a_k-410^k-4 + ..... + a₄.10⁴ )

16 │N → 16 │ a_k.10^k + a_k-110^k-1 + a_k-210^k-2 + a_k-310^k-3 +a_k-410^k-4 + ..... + a₁.10 + a_o.

16 │ a_k.10^k + a_k-110^k-1 + a_k-210^k-2 + a_k-310^k-3 +a_k-410^k-4 + ..... + a₄.10⁴

Jadi 16 │ a_3.10³ +a_2.10² + a₁.10 + a_o atau 16 │ a₃a₂a₁a_o

Kesimpulan : suatu bilangan asli N habis dibagi 16 jika bilangan yang dibentuk oleh empat angka terakhir dari lambang bilangan N habis dibagi 16.

Contoh

1. 
   Selidiki apakah bilangan 1212646 habis dibagi 2, 4, 8, dan 16
   

1212646 = (a₄a₃a₂a₁a₀)

Karena (a_o) = 6 dan 2│6 maka 2 │1212646

Karena (a₁a₀) = 46 dan 4 ┼ 46 maka 4 ┼ 1212646

Karena (a₂a₁a₀) = 646 dan 8 ┼ 646 maka 4 ┼ 1212646

Karena (a₃a₂a₁a₀) = 2646 dan 16 ┼ 2646 maka 16 ┼ 1212646

1. 
   Selidiki apakah 44768 habis dibagi 2, 4, 8, dan 16
   

44768 = (a₄a₃a₂a₁a₀)

Karena (a_o) = 8 dan 2 │8 maka 2 │44768

Karena (a₁a₀) = 68 dan 4 │68 maka 4 │44768

Karena (a₂a₁a₀) = 768 dan 8 ┼ 768 maka 8 │44768

Karena (a₃a₂a₁a₀) = 4768 dan 16 │4768 maka 16 ┼ 4476
Ciri-ciri habis dibagi 3.

Perhatikan

N = a_k.10^k + a_k-1.10^k-1 + a_k-2.10^k-2 + a_k-3.10^k-3 + a_k-4.10^k-4 + .... + a₁.10 + a_o.

Karena

a₁.10 = a₁ ( 9 + 1 ) = a_1. 9 + a₁

a₂.10² = a₁ ( 99 + 1 ) = a_1.99 + a₂

a₃.10³ = a₃ ( 999 + 1 ) = a_3.999 + a₃

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

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

a_k.10^k = ..... = a_k ( 999...9 + 1 ) = a_k.999...9 + a_k

maka:

N = a_k.10^k + a_k-1.10^k-1 + a_k-2.10^k-2 + a_k-3.10^k-3 + a_k-4.10^k-4 + .... + a₁.10 + a_o.

= (a_3.999...9 + a_k ) + ... + (a_3.999 + a₃ ) + (a_2.99 + a₂ ) + (a_1. 9 + a₁ ) + a_o

= (a_3.999...9 + ... + a_3.999 + a_2.99 + a_1. 9 ) + (a_k + ... + a₃ + a₂ + a₁ + a_o )

Dari hasil ini dapat ditentukan bahwa

3│9 → 3│a₁.9

3│9 → 3 │11.9 → 3│99 → 3│a₂.99

3│9 → 3 │111.9 → 3│999 → 3│a_3.999

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

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

3│9 → ............................................................... 3│a_k.999 ... 9

sehingga

3│a_k.999 ... 9, ... , 3│a_3.999, 3│a₂.99, 3│a₁.9

atau 3│(a_k.999 ... 9) + ... + (a_3.999) + (a₂.99) + (a₁.9)

3│N → 3│(a_k.999...9 + ... + a_3.999 + a_2.99 + a_1. 9 ) + (a_k + ... + a₂ + a₁ + a_o )

maka 3 │(a_k + ... + a₂ + a₁ + a_o )

Kesimpulan suatu bilangan bulat N habis dibagi3 jika jumlah angka-angka dari lambang bilangan N habis dibagi 3.

Contoh

1. 
   Selidiki apakah 3462 habis dibagi 3 ?
   

Jawab:

Misal N = 3462 = (a₃a₂a₁a₀)

Dan a₃ + a₂ + a₁ + a_o = 3 + 4 + 6 + 2 = 15

Karena 3 │15 maka 3 │3462

1. 
   Selidiki apakah 564350098 habis dibagi 3?
   

Jawab:

Misal N = 564350098 = (a₈a₇a₆a₅a₄a₃a₂a₁a₀), diperoleh

a₈ + a₇ + a₆ + a₅ + a₄ + a₃ + a₂ + a₁ + a_o = 5 + 6 + 4 + 3 + 5 + 0 + 0 + 9 + 8 = 40

Karena 3 ┼ 40 maka 3 ┼ 564350098

Ciri-ciri habis dibagi 9.

Dari uraian pembagian dengan bilangan 3 diketahui bahwa:

N = a_k.10^k + a_k-1.10^k-1 + a_k-2.10^k-2 + a_k-3.10^k-3 + a_k-4.10^k-4 + .... + a₁.10 + a_o.

= (a_3.999...9 + ... + a_3.999 + a_2.99 + a_1. 9 ) + (a_k + ... + a₃ + a₂ + a₁ + a_o )

Karena

9│9 → 9│a₁.9

9│9 → 9 │11.9 → 9│99 → 9│a₂.99

9│9 → 9 │111.9 → 9│999 → 9│a_3.999

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

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

9│9 → ............................................................... 9│a_k.999 ... 9

sehingga

9│a_k.999 ... 9, ... , 9│a_3.999, 9│a₂.99, 9│a₁.9

atau 9│(a_k.999 ... 9) + ... + (a_3.999) + (a₂.99) + (a₁.9)

9│N → 9│(a_k.999...9 + ... + a_3.999 + a_2.99 + a_1. 9 ) + (a_k + ... + a₂ + a₁ + a_o )

maka 9 │(a_k + ...+ a₂ + a₁ + a_o )

Kesimpulan suatu bilangan bulat N habis dibagi 9 jika jumlah angka-angka dari lambang bilangan N habis dibagi 9.

Contoh :

Selidiki apakah 142323331011 habis dibagi 3 dan 9

N = 142323331011→ (a₁₁a₁₀a₉a₈a₇a₆a₅a₄a₃a₂a₁a_o)

a₁₁+ a₁₀+ a₉+ a₈ + a₇ + a₆ + a₅ + a₄+ a₃ + a₂ + a₁+ a_o = 1 + 4 + 2 + 3 + 2 + 3 + 3 + 3 + 1 + 0 + 1 + 1 = 24

Karena 3 │24 maka 3 │142323331011

Karena 9 ┼ 24 maka 3 ┼142323331011

Ciri-ciri habis dibagi 5

Perhatikan

N = a_k.10^k + a_k-1.10^k-1 + a_k-2.10^k-2 + a_k-3.10^k-3 + a_k-4.10^k-4 + .... + a₁.10 + a_o.

Karena :

5 │10 → 5 │a₁.10

5 │10 → 5 │10.10 → 5 │10² → 5 │a₂.10².

5 │10 → 5 │100.10 → 5 │10³ → 5 │a₃.10³.

5 │10 → 5 │1000.10 → 5 │10⁴ → 5 │a₄₃.10⁴.

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

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

5 │10 → ............................................................... 5 │a_k.10^k.

5 │a_k.10^k , 5│a_k-110^k-1 , 5│a_k-210^k-2 , 5│a_k-310^k-3 , 5 │a_k-410^k-4 , .... , 5│a₁.10

5 │(a_k.10^k + a_k-110^k-1 + a_k-210^k-2 + a_k-310^k-3 +a_k-410^k-4 + ..... + a₁.10)

5 │N → 5 │ (a_k.10^k + a_k-110^k-1 + a_k-210^k-2 + a_k-310^k-3 +a_k-410^k-4 + ..... + a₁.10) + a_o.

5│ a_k.10^k + a_k-110^k-1 + a_k-210^k-2 + a_k-310^k-3 +a_k-410^k-4 + ..... + a₁.10

Jadi 5│ a_o. Kemungkinannya a_o = 0 atau a_o = 5

Kesimpulan suatu bilangan asli N habis dibagi 5 jika angka terakhir lambang bilangan N adalah 0 atau 5.

Contoh:

1. 
   Bilangan 2456 tidak habis dibagi 5 karena angka terakhir dari 2456 yaitu 6 tidak habis dibagi 5. atau 5 ┼ 6. sehingga 5 ┼ 2456.
   
2. 
   Bilangan 450980 habis dibagi 5 karena angka terakhir dari 450980 adalah 0 dan
   

5 │0, sehingga 5 │450980

Ciri-ciri habis dibagi 6.

Jika diketahui 6│N, maka 6 merupakan pembagi (faktor) dari N, sehingga:

N = 6k untuk k Z.

N = 6k dan 6 = 2.3, maka N = (2.3)k

N = 2(3.k) → 2 │N

N = 3(2.k) → 3 │N

Jadi suatu bilangan bulat N habis dibagi 6 jika N habis dibagi oleh 2 dan 3.Dengan kata lain suatu bilangan N habis dibagi 6 jika angka terakhir adalah genap dan jumlah angka-angka dari lambang bilangan N habis dibagi 3.

Contoh :

1. 
   Selidiki apakah 4356 habis dibagi 6
   

4356 habis dibagi 2, karena angka terakhir dari bilangan 4356 yaitu 6 habis dibagi 2, sehingga 2 │4356. 4 + 3 + 5 + 6 = 18, dan 3 │18, maka 3│4356.

Karena 2 │4356 dan 3│4356 maka 6 │4356.

1. 
   Selidiki apakah 9854098 habis dibagi 6!
   

9854098 habis dibagi 2 karena 2 │8, dan 9 + 8 + 5 + 4 + 0 + 9 + 8 = 43, sehingga

3 ┼ 43. Karena 2 │9854098, akan tetapi 3 ┼ 9854098, maka 6 ┼ 9854098.

Ciri-ciri habis dibagi 7.

Perhatikan

N = a_k.10^k + a_k-1.10^k-1 + a_k-2.10^k-2 + a_k-3.10^k-3 + a_k-4.10^k-4 + .... + a₁.10 + a_o.
Karena

a₁.10 = a₁( 7 + 3 ) = 7a₁ + 3a₁

a₂.10² = a_2. 100 = a₂( 98 + 2 ) = 98 a₂ + 2a₂

a₃.10³ = a_3. 1000 = a₃( 1001 –1 ) = 1001 a₃ - a₃

a₄.10⁴ = a_4. 10000 = a₄( 10003 - 3 ) = 10003a₄ - 3a₄

a₅.10⁵ = a_5. 100000 = a₅( 100002 – 2 ) = 100002 - 2a₅

dan seterusnya

sehingga:

N = a_k.10^k + a_k-1.10^k-1 + a_k-2.10^k-2 + a_k-3.10^k-3 + a_k-4.10^k-4 + .... + a₁.10 + a_o.

= a_k.10^k + .... + a₅10⁵ + a₄.10⁴ + a₃.10³ + a_-2 .10² + a₁.10 + a_o.

= a_k.10^k + ..... + (100002 a₅ - 2a₅) + (10003a₄ - 3a₄ ) + (1001 a₃ - a₃ ) +

( 98 a₂ + 2a₂ ) + ( 7a₁ + 3a₁) + a₀.

= (7a₁ + 98a₂ + 1001a₃ - 10003a₄ - 100002a₅ + ... 7.t.10^k ) + (a₀ +3a₁ + 2a₂ )

- (a₃ + 3a₄ + 2a₅) + ...

= 7m + (a₀ +3a₁ + 2a₂ ) - (a₃ + 3a₄ + 2a₅) + ...

7 │N dan 7 │m , maka 7 │(a₀ +3a₁ + 2a₂ ) - (a₃ + 3a₄ + 2a₅) + ...

Kesimpulan bilangan N = (a_ka_k-1a_k-2a_k-3a_{k-4 ....}a₁a_o) habis dibagi jika

7 │(a₀ +3a₁ + 2a₂ ) - (a₃ + 3a₄ + 2a₅) + ...

Contoh

1. 
   Selidiki apakah 1234 habis dibagi 7.
   

Misal 1234 = (a₃a₂a₁a₀) , maka diperoleh

a_{3 =} 1, a₂ = 2, a₁= 3, a₀= 4

a₀ + 3a₁ + 2a₂ = 4 + 3(3) + 2(2) = 17 dan a₃ = 1

sehingga (a₀ + 3a₁ + 2a₂ ) - a₃ = 17 – 1 = 6

Karena 7 ┼ 2, maka 7 ┼ 1234.

1. 
   Selidiki apakah 3976 habis dibagi 7.
   

Jawab

Dengan cara lain dapat diselidiki apakah 7 │ 3976.

Ambil N = 3976 dan andaikan 7 │ 3976.

Karena 7 │ 21, maka 7 │ 6.21 sehingga 7 │ 3976 – 6.21

7 │ 3976 – 6.21 7 │ 3.10³ + 9.10² + 7.10¹ + 6.10⁰ – 6.21

7 │ 3.10³ + 9.10² + 7.10¹ + 6.10⁰ – 6.20

7 │ 10(3.10² + 9.10¹ + 7 – 2.6

7 │ 10(3397 – 2.6)

Karena (7,10) = 1 dan 7 │10(397 – 2.6), maka menurut dalil sebelumnya

7│ 397 – 2.6. atau 7 │ 385

Jika cara tersebut diteruskan akan diperoleh

7 │ 385 7 │ 38 – 2.5 atau 7 │ 28

7 │ 18 7 │ 2 – 2.8 atau 7 │ -14.

Dengan demikian 7 │ 3976. dan bilangan 2 disebut dengan pengali.
Ciri-ciri habis dibagi 10.

Perhatikan

N = a_k.10^k + a_k-1.10^k-1 + a_k-2.10^k-2 + a_k-3.10^k-3 + a_k-4.10^k-4 + .... + a₁.10 + a_o.

Karena

10 │10 10 │a₁.10

10 │10 10│10.10 10 │10² 10 │a₂.10².

10 │10 10 │100.10 10 │10³ 10 │a₃.10³.

10 │10 10 │1000.10 10 │10⁴ 10 │a₄.10⁴.

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

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

10 │10 ............................................................... 10 │a_k.10^k.

10 │a_k.10^k , 10 │a_k-110^k-1 , 10│a_k-210^k-2 , 10│a_k-310^k-3 , 10│a_k-410^k-4 , ....., 10 a₁.10

10 │(a_k.10^k + a_k-110^k-1 + a_k-210^k-2 + a_k-310^k-3 +a_k-410^k-4 + ..... + a₁.10)

10│N 10│ a_k.10^k + a_k-110^k-1 + a_k-210^k-2 + a_k-310^k-3 +a_k-410^k-4 + ..... + a₁.10 + a_o.

10│ a_k.10^k + a_k-110^k-1 + a_k-210^k-2 + a_k-310^k-3 +a_k-410^k-4 + ..... + a₁.10

Jadi 10 │ a_o , nilai yang mungkin untuk a_o = 0.

Kesimpulan : Suatu bilangan asli N habis dibagi 10 jika angka terakhir lambang bilangan N (yaitu a_o) adalah 0.
Ciri-ciri habis dibagi 11.

Perhatikan

N = a_k.10^k + a_k-1.10^k-1 + a_k-2.10^k-2 + a_k-3.10^k-3 + a_k-4.10^k-4 + .... + a₁.10 + a_o.

Karena

a₁.10 = a₁( 11 – 1 ) = 11a₁ - a₁

a₂.10² = a_2. 100 = a₂( 99 + 1 ) = 99 a₂ + a₂

a₃.10³ = a_3. 1000 = a₃( 1001 –1 ) = 1001 a₃ - a₃

a₄.10⁴ = a_4. 10000 = a₄( 9999 + 1 ) = 9999a₄ + a₄

a₅.10⁵ = a_5. 100000 = a₅( 100001 - 1 ) = 100001a₅ - a₅

dan seterusnya

sehingga:

N = a_k.10^k + a_k-1.10^k-1 + a_k-2.10^k-2 + a_k-3.10^k-3 + a_k-4.10^k-4 + .... + a₁.10 + a_o.

= a_k.10^k + .... + a₅10⁵ + a₄.10⁴ + a₃.10³ + a_-2 .10² + a₁.10 + a_o.

= a_k.10^k + ..... + (99999 a₅ + a₅) + (10003a₄ - 3a₄ ) + (1001 a₃ - a₃ ) +

( 99a₂ + a₂ ) + ( 11a₁- a₁) + a₀.

= (11a₁ + 99 a₂ + 1001 a₃ + 10003a₄ + 99999 + ... ) + (a₀ + a₂ + a₄ ) -

(a₂ + a₄ + a₆) + ...

= 11.t + (a₀ + a₂ + a₄ ) - (a₂ + a₄ + a₆) + ...

11 │N dan 11 │11.t , maka 11│(a₀ + a₂ + a₄ ) - (a₂ + a₄ + a₆) + ...

Kesimpulan bilangan N = (a_ka_k-1a_k-2a_k-3a_{k-4 ....}a₁a_o) habis dibagi 11 jika selisih jumlah angka-angka pada urutan genap dengan jumlah angka pada urutan ganjil habis dibagi 11.

Contoh:

1. 
   Bilangan 8685204 habis dibagi 11, mangapa?
   
2. 
   Bilangan 25902646 habis dibagi 11, mengapa?
   
3. 
   Bilangan 456233311 tidak habis dibagi 11, mengapa?
   

Ciri-ciri habis dibagi bilangan Prima.

Berdasarkan hasil pembagian dengan bilangan 7 dan 11 dapat diketahui bahwa secara bertahap, bilangan yang diselidiki direduksi menjadi suatu bilangan yang dengan mudah dapat ditentukan habis dibagi 7 atau 11. Untuk proses reduksi, dalam penyelidikan setiap bilangan yang habis dibagi 7 maupun 11 digunakan suatu pengali (multiplier) yaitu 2 untuk pembagian 7 dan 1 untuk pembagian 11.

Untuk bilangan prima yang lebih dari 11, dengan proses uraian seperti pembagian 7 dan 11 dapat dicari pengali-pengali yang sesuai. Sebagai contoh pengali dari pembagian 13 adalah 9 dan pengali dari pembagian oleh 17 adalah 5.

1. 
   Mencari Pengali dari pembagian 13.
   

N = (a_ka_k-1a_k-2a_k-3a_{k-4 ....}a₁a_o)

13 │91 maka 13 │91 a_o.

13 │N dan 13 │91 a_o. → 13 │N - 91 a_o.

↔ 13 │ (a_ka_k-1a_k-2a_k-3a_{k-4 ....}a₁a_o ) - 91 a_o.

↔ 13 │10(a_ka_k-1a_k-2a_k-3a_{k-4 ....}a₁ - 9 a_o)

Karena (13,10) = 1, maka 13 │(a_ka_k-1a_k-2a_k-3a_{k-4 ....}a₁ - 9 a_o)

Dari hasil ini jelaslah bahwa pengali untuk pembagian oleh 13 adalah 9.

1. 
   Mencari Pengali dari pembagian 17.
   

N = (a_ka_k-1a_k-2a_k-3a_{k-4 ....}a₁a_o)

17 │51 maka 17 │51 a_o.

17 │N dan 17 │51 a_o. → 17│N - 51 a_o.

↔ 17 │ (a_ka_k-1a_k-2a_k-3a_{k-4 ....}a₁a_o ) - 51 a_o.

↔ 17 │10(a_ka_k-1a_k-2a_k-3a_{k-4 ....}a₁ - 5 a_o)

Karena (17,10) = 1, maka 17 │(a_ka_k-1a_k-2a_k-3a_{k-4 ....}a₁ - 5a_o)

Dari hasil ini jelaslah bahwa pengali untuk pembagian oleh 17 adalah 5.

1. 
   Mencari Pengali dari pembagian 19.
   

N = (a_ka_k-1a_k-2a_k-3a_{k-4 ....}a₁a_o)

19 │171 maka 13 │171a_o.

19 │N dan 19 │171a_o. → 19 │N - 171 a_o.

↔ 19 │ (a_ka_k-1a_k-2a_k-3a_{k-4 ....}a₁a_o ) - 171 a_o.

↔ 19 │10(a_ka_k-1a_k-2a_k-3a_{k-4 ....}a₁ - 17a_o)

Karena (19,17) = 1, maka 19│(a_ka_k-1a_k-2a_k-3a_{k-4 ....}a₁ - 17a_o)

Dari hasil ini jelaslah bahwa pengali untuk pembagian oleh 19 adalah 17.

Dengan cara yang sama jika dibuat daftar pengali dari bilangan-bilangan prima 7,11,13, 17, ..., maka dapat diperoleh bilangan pengali sbagai berikut:

Pembagi 71113171923293137414347....Pengali 219517162631143014.....

Contoh

1. 
   Selidiki apakah 36062, habis dibagi 11 dan 13
   

Jawab

Bilangan pengali pada pembagian dengan 11 adalah 1, maka:

36062 = 3606 – 1.2 = 3604

3604 = 360 – 1.4 = 356

356 = 35 – 1.6 = 29

Karena 11 ┼ 29 , maka 11 ┼ 36062

Bilangan pengali pada pembagian dengan 13 adalah 9, maka:

36062 = 3606 – 9.2 = 3594

3594 = 359 – 9.4 = 323

323 = 32 – 9.3 = 5

Karena 13 ┼ 5 , maka 13 ┼ 36062

1. 
   Selidiki apakah 16788979 habis dibagi 17 dan 19
   

Jawab

Bilangan pengali pada pembagian dengan 17 adalah 5, maka:

16788979 = 1678897 – 5.9 = 1678852

1678852 = 167885 – 5.2 = 167875

167875 = 16787 – 5.5 = 16762

16762 = 1676 – 5.2 = 1666

1666 = 166 – 5.6 = 136

136 = 13 – 5.6 = -17

Karena 17 │-17, maka 17 │16788979

Bilangan pengali pada pembagian dengan 19 adalah 17, maka:

16788979 = 1678897 – 17.9 = 1678744

1678744 = 167874 – 17.4 = 167806

167806 = 16780 – 17.6 = 16618

16618 = 1661 – 17.8 = 1525

1525 = 152 – 17.5 = 67

Karena 19 ┼ 67, maka 19 ┼ 16788979

2.5 Pembagian dengan Metode Pencoretan (Scratch Method).

Metode ini digunakan untuk mengetahui apakah suatu bilangan habis dibagi 7, 11, 13, 77, 91, atau 143. Meskipun pembagian dengan cara biasa dapat dilakukan dengan mudah. Metode ini dapat memberikan tambahan ilmu baru dengan teknik yang lebih sederhana dan relatif singkat.

Perhatikan bahwa hasil kali 7, 11, dan 13 adalah:

7 x 11 x 13 = 1001. Jadi jelaslah bawa 7 │1001, 11 │1001, dan 13 │1001.

Jika suatu bilangan bulat N dibagi 1001, maka ada beberapa keadaan yang terjadi.

1. 
   1001│N.
   

Karena 7 │1001, 11 │1001, dan 1001│N, maka jelaslah bahwa 1001.

7│N, 11│N dan 13 │N.

1. 
   11 ┼ N
   

Karena 11 ┼ N, maka N dapat dinyatakan sebagai

N = 1001.q + r (r )

1. 
   7│r
   

Karena 7│1001.q dan 7 │r, maka 7 │1001.q + r, atau 7 │N,

1. 
   11│r
   

Karena 11│1001.q dan 11 │ r, maka 11 │1001.q + r, atau 11│N,

1. 
   13│r
   

Karena 13│1001.q dan 13 │r, maka 13 │1001.q + r, atau 13 │N,

1. 
   7│r dan 11│r ( 13 ┼ r)
   

Karena 7│r dan 11│r, dan (7,11) = 1 maka 77│r.

Karena 77│1001.q dan 77 │r, maka 77 │1001.q + r, atau 77 │N,

1. 
   7│r dan 13│r ( 11 ┼ r)
   

Karena 7│r dan 13│r, dan (7,13) = 1 maka 91│r.

Karena 91│1001.q dan 91 │r, maka 91 │1001.q + r, atau 91 │N,

1. 
   11│r dan 13│r ( 7 ┼ r)
   

Karena 11│r dan 13│r, dan (11,13) = 1 maka 143│r.

Karena 143│1001.q dan 143 │r, maka 143 │1001.q + r, atau 143│N,

Berdasarkan analogi tersebut di atas, dapat disimpulkan bahwa suatu bilangan habis dibagi 7, 11, 13, 77, 91, 143, dapat dilakukan dengan pembagian 1001. selanjutnya dilihat sisa hasil pembagian yaitu bagaimana keadaan dari r. Untuk lebih jelasnya perhatikan contoh berikut ini.

1. 
   Bagilah 231764587 dengan 1001
   

Misal N = 231764587, dengan 2 adalah angka ke-1, 3 angka ke-2, ..... 7 angka ke 9.

1. 
   Perhatikan angka ke-1 dan ke-4 dan kurangkan diperoleh 7-2 = 5 dan hasilnya letakkan diatas N.
   

5

2 3 1 7 6 4 5 8 7

1. 
   Selanjuntnya perhatikan angka ke-2 dan ke-5, dan kurangkan maka diperoleh
   

4 – 1 = 3, hasilnya letakkan di atas N

5 3

2 3 1 7 6 4 5 8 7,

1. 
   Lanjutkan sampai angka ke-9 maka diperoleh:
   

5 3 3 1 5 4

2 3 1 7 6 4 6 8 7,

Perhatikan bahwa tiga bilangan terakhir yang tidak dicoret adalah sisa pembagian yaitu 154. Selanjutnya dapat diselidiki apakah 154 habis dibagi 7, 11, 13, dan seterusnya.

Karena 7 │154, maka 7 │231764587. Karena 13 ┼ 154, maka 13 ┼ 231764587

1. 
   Misal N = 3526766958 dibagi 1001
   

Analog dengan contoh soal 1 diperoleh hasil sisa pembagian.

3 2 4 3 7 1 5

3 5 2 6 7 6 6 9 5 8

Perhatikan bahwa tiga bilangan terakhir yang tidak dicoret adalah sisa pembagian yaitu 715. Selanjutnya dapat diselidiki apakah 715 habis dibagi 7, 11, 13, dan seterusnya.

Contoh 1 dan 2 di atas, disebut juga dengan metode pembagian dengan pencoretan (scratch merthod)

Kesimpulan

Suatu bilangan asli N habis dibagi :

1. 
   Selalu habis dibagi 1.
   
2. 
   2 jika angka terakhir lambang bilangan N habis dibagi 2 (genap).
   
3. 
   3 jika jumlah angka-angka dari lambang bilangan N habis dibagi 3.
   
4. 
   4 jika bilangan yang dibentuk oleh dua angka terakhir dari lambang bilangan N habis bagi 4.
   
5. 
   5 jika angka terakhir dari lambang bilangan N adalah 0 atau 5.
   
6. 
   6 jika N habis dibagi oleh 2 dan 3.
   
7. 
   7 jika N = (a_ka_k-1a_k-2a_k-3a_{k-4 ....}a₁a_o) habis dibagi jika 7 │(a₀ +3a₁ + 2a₂ ) - (a₃ + 3a₄ + 2a₅) + ...
   
8. 
   8 jika bilangan yang dibentuk oleh tiga angka terakhir dari lambang bilangan N habis dibagi 8
   
9. 
   9 jika jumlah angka-angka dari lambang bilangan N habis dibagi 9.
   
10. 
    10 jika angka terakhir dari lambang bilangan N adalah 0.
    
11. 
    N = (a_ka_k-1a_k-2a_k-3a_{k-4 ....}a₁a_o) habis dibagi 11 jika selisih jumlah angka-angka pada urutan genap dengan jumlah angka pada urutan ganjil habis dibagi 11.
    
12. 
    habis dibagi 12 jika N habis dibagi 3 dan 4.
    
13. 
    habis dibagi 13 jika sisa pembagian dengan methode pencoretan habis dibagi 13.
    
14. 
    habis dibagi 14, jika N habis dibagi 2 dan 7.
    
15. 
    habis dibagi 15 jika N habis dibagi 3 dan 5.
    
16. 
    habis dibagi 16 jika 4 angka terakhir dari N adalah bilangan yang habis dibagi 16.
    
17. 
    Selanjutnya dapat diselidiki apakah suatu bilangan habis dibagi bilangan prima. Cara yang dapat ditempuh adalah mencari bilangan pengali pada pembagian dengan bilangan prima.
    

2.6 Soal-soal

1. 
   Tunjukkan bahwa jika ab │ bc maka a│ b.
   
2. 
   Berapa banyak bilangan bulat antara 100 sampai dengan 1000 yang habis dibagi 7?
   
3. 
   Jika (a,4) = 2 dan (b,4) = 2, Buktikan bahwa (a+b,2) = 4
   
4. 
   Tentukan (n,n+1) dan [n,n+1], bila n Z.
   
5. 
   Selidiki apakah bilangann 4562333211119 habis dibagi 11, dan 13.
   
6. 
   Buktikan jika n bilangan ganjil maka 8 │ n² – 1.
   
7. 
   Jika a │b, a │c, maka a │(b-c). Jika a > b dan b 0.
   
8. 
   Tentukan nilai x dan y dari kombinasi linear berikut ini.
   
9. 
   341x + 527y = (341,527)
   
10. 
    817x + 589y = (817,589)
    
11. 
    999x + 49y = (999, 49)
    
12. 
    5321x + 544y = (5321,544)
    
13. 
    44329x + 140299y = (44329, 140299)
    
14. 
    Tunjukkan bahwa:
    
15. 
    Perkalian tiga bilangan bulat berurutan habis dibagi 6
    
16. 
    Perkalian empat bilangan bulat berurutan habis dibagi 24.
    
17. 
    Tentukan KPK dari
    
18. 
    109 dan 1135
    
19. 
    2201 dan 3317
    
20. 
    4, 5, dan 9
    
21. 
    3, 4, dan 6
    
22. 
    5321 dan 544
    
23. 
    Tentukan semua selesaian (jika mungkin) dari persamaan Diophantine berikut ini.
    
24. 
    56x + 72y = 40
    
25. 
    24x + 138y = 18
    
26. 
    221x + 91y = 117
    
27. 
    84x – 438y = 156
    
28. 
    30x + 17y = 300
    
29. 
    54x + 21y = 906
    
30. 
    123x + 360y = 99
    
31. 
    158x – 57y = 7
    

BAB III

KONGRUENSI
3.1 Pengertian

Jika kita berbicara konsep kongruensi sebenarnya hal ini secara tidak langsung sudah didapatkan pada pelajaran matematika Sekolah Dasar, hanya saja istilah yang digunakan sedikit berbeda yaitu bilangan jam atau bilangan bersisa. Cara yang dilakukan biasanya diperagakan dengan menggunakan jam sebagi media dalam operasi yang berlaku, baik jumlah maupun pengurangan. Dalam bilangan jam enaman, jika dioperasikan dengan menggunakan jam maka bilangan bulat yang digunakan adalah 0, 1, 2, 3, 4, dan 5. Sedangkan bilangan bulat lainnya dapat direduksi yaitu dengan cara membagi bilanmgan tersebut dengan 6 dan bilangan yang digunakan adalah sisa dari pembagian tersebut.

Contoh:

14 dalam jam enaman dapat direduksi menjadi 2, karena 14 jika dibagi 6 bersisa 2.

21 dalam jam enaman dapat direduksi menjadi 3, karena 21 jika dibagi 6 bersisa 3.

61 dalam jam enaman dapat direduksi menjadi 1, karena 61 jika dibagi 6 bersisa 1.

dan seterusnya.

Berdasarkan proses reduksi dan operasi yang ada pada bilangan jam, selanjutnya dikembangkan konsep kongruensi sebagai berikut.

14 2 karena jika 14 dibagi 6 bersisa 2

21 3 karena jika 21 dibagi 6 bersisa 3

61 1 karena jika 61 dibagi 6 bersisa 1

Pernyataan di atas dapat pula dinyatakan dengan

14 2 karena 14 – 2 = 12 dan 12 habis dibagi 6

21 3 karena 21 – 3 = 18 dan 18 habis dibagi 6

61 1 karena 61 – 1 = 60 dan 60 habis dibagi 6.

Berdasarkan contoh di atas terlihat bahwa sesungguhnya konsep kongruensi adalah pengkajian secara lebih mendalam tentang keterbagian pada bilangan bulat dan sifat-sifatnya yang telah dipelajari pada bab II, atau dapat pula dikatakan bahwa kongruensi adalah cara lain untuk mengkaji keterbagian dalam bilangan bulat. Untuk jelasnya perhatikan definisi dan teorema di bawah ini.

Definisi 3.1

Misal a, b, m Z dan m 0, maka a disebut kongruen dengan b modulo m jika a-b habis dibagi oleh m, yaitu m│a – b. Pernyataan ini dinotasikan a b (mod m).

Jika m ┼ (a-b) maka dinotasikan dengan a ∕ b (mod m).

Contoh:

7 2 ( mod 5), karena 5│(7-2)

34 4 ( mod 10), karena 10│(34-4)

17 1 ( mod 4), karena 4│(17-1)

6 ∕ 1 (mod 4), karena 4 ┼ (6-1)

11 ∕ 4 (mod 9), karena 9 ┼ (11-4)

Dengan demikian sebenarnya istilah kongruensi sering muncul dalam kehidupan di sekitar kita. Misalnya kerja kalender yang kita gunakan dalam tahun Masehi menggunakan bilangan bulat modulo 7 karena dalam satu minggu terdapat 7 hari, kerja arloji menggunakan bilangan bulat modulo 12 karena waktu yang ada dalam jam yaitu jam 01.00 – 12.00. Banyaknya bulan dalam satu tahun menggunakan bilangan bulat modulo 12, pasaran hari dalam satu minggu menggunakan bilangan bulat modulo 5 karena terdapat pasaran hari pon, wage, kliwon, legi, pahing dan masih banyak lagi contoh-contoh penggunaan kongruensi yang secara tidak langsung ada disekitar kita.

Dalil 3.1

Misal a,b,c, Z, dan m N, maka berlaku sifat-sifat simetris, refleksif, dan transitip.

1. 
   Refleksif
   

a a (mod m)

1. 
   Simetris
   

Jika a b (mod m) maka b a.(mod m)

1. 
   Transitif
   

Jika a b (mod m) maka b c (mod m)m, maka a c (mod m)

Bukti

1. 
   Misal m 0, maka m│0.
   

m│0 berarti m │(a-a)

Karena m │(a-a), hal ini menurut definisi a a (mod m), untuk setiap bilangan bulat a dan m 0.

Cara lain

a a (mod m), sebab a-a = 0 dan m│0.

1. 
   a b (mod m), menurut definisi berarti m│a-b, sedangkan menurut definisi keterbagian m│a-b, dapat dinyatakan sebagai (a-b) = tm, untuk t Z.
   

(a-b) = tm -(a-b) = -tm

(b-a) = (-t)m, -t Z.

m │(b-a) atau b a (mod m)

1. 
   a b (mod m) berarti m │(b-a)
   

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

Menurut dalil keterbagian

m │(b-a) dapat dinyatakan dengan a-b = t₁m

m │(b-c) dapat dinyatakan dengan b-c = t₂m

---------------- +

(a-c) = (t₁+t₂)m, untuk t₁,t₂ Z

Jadi m │(a-c) atau a ≡ c(mod m)

• Teorema 3.1

Misal a,b,c,d Z dan m N, maka

1. 
   Jika a b (mod m) maka ac bc (mod m)
   

Bukti

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

Menurut definisi keterbagian bilangan bulat berlaku

(a-b) = tm, t Z.

(a-b)c = (tm)c.

ac – bc = (tc)m

ac – bc = xm, x Z.

Karena ac-bc = xm, berarti m │ (ac-bc) atau ac = bc (mod m)

1. 
   Jika a b (mod m) maka a+c b+c (mod m)
   

Bukti

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

Menurut definisi keterbagian bilangan bulat berlaku

(a-b) = tm, t Z.

(a-b) + 0 = (tm)

(a-b) + (c-c) = (tm)

(a+c) – (b+c) = (tm)

Karena (a+c) – (b+c) = tm, berarti m │ (a+c) – (b-c) atau a+c = b+c (mod m)

1. 
   Jika a b (mod m) dan c d (mod m) maka a+c b+d (mod m)
   

Bukti

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

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

Menurut dalil keterbagian

m │(b-a) dapat dinyatakan dengan a-b = t₁m

m │(c-d) dapat dinyatakan dengan c-d = t₂m

---------------- +

(a+c) - (b+d) = (t₁+t₂)m, untuk t₁,t₂ Z

Jadi m │(a+c) - (b+d) atau a+c ≡ b+d (mod m)

1. 
   Jika a b (mod m) dan c d (mod m) maka a-c b-c (mod m)
   

Bukti

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

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

Menurut dalil keterbagian

m │(b-a) dapat dinyatakan dengan a-b = t₁m

m │(c-d) dapat dinyatakan dengan c-d = t₂m

---------------- -

(a-c) - (b-d) = (t_1-t₂)m, untuk t₁,t₂ Z

Jadi m │(a-c) - (b-d) atau a-c ≡ b-d (mod m)

1. 
   Jika a b (mod m) dan d │m, d > 0, maka a b (mod d)
   

Bukti

Karena a b (mod m) maka m │m-b

Jika m │a-b dan d │m, berarti d │a-b , d > 0.

Karena d │a-b berati a b (mod d)

1. 
   Jika a b (mod m) dan c d (mod m) maka
   

ax + by = bx + dy (mod m), untuk x,y Z.

Bukti

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

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

Menurut dalil keterbagian

m │(b-a) dapat dinyatakan dengan a-b = t₁m

m │(c-d) dapat dinyatakan dengan c-d = t₂m

(a-b)x = (t₁m)x, x Z

(c-d)y = (t₂m)y, y Z

---------------------------- +

(a-b)x + (c-d)y = {(t₁m)x+ (t₂m)y}, x,y Z

atau (ax +cy) – (bx+dy) = {(t₁x)+ (t₂y)}m, {(t₁x)+ (t₂y)} Z

atau m │(ax +cy) – (bx+dy) = atau (ax +cy) ≡ (bx+dy) (mod m)

1. 
   Jika a b (mod m) dan c d (mod m) maka ac = bd (mod m)
   

Bukti

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

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

Menurut dalil keterbagian

m │(b-a) dapat dinyatakan dengan a-b = t₁m

m │(c-d) dapat dinyatakan dengan c-d = t₂m

(a-b)c = (t₁m)c, c Z atau (ac – bc) = (t₁m)c, c Z

(c-d)b = (t₂m)b, b Z atau (cb – db) = (t₂m)b, b Z

----------------------------------------------------------------- +

(ac-bd) = (t₁m)c + (t₂m)b, a,b Z.

(ac-bd) = (t₁c + t₂b)m, (t₁c + t₂b) Z.

atau m │(ac – bd ) atau (ac) ≡ (bd) (mod m)

1. 
   Jika a b (mod m) maka aⁿ = bⁿ (mod m)
   

Bukti

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

Menurut dalil keterbagian

m │(b-a) dapat dinyatakan dengan a-b = tm

Selanjutnya kita mengetahui bahwa

aⁿ – bⁿ = (a-b)(a^n-1 + a^n-2b + a^n-3b² + ..... + b^n-1)

Karena a-b │ a-b , maka

a-b │ aⁿ – bⁿ , atau

a-b │(a-b)(a^n-1 + a^n-2b + a^n-3b² + ..... + b^n-1)

•