Teorema 2 ⇔ (Teori Bilangan)

TEOREMA 2

Bukti (Hanya untuk 1 (ii) dan 2 (i) saja)

1.     (ii) a º b (mod m) berarti:

⇔ a = b + km

⇔ a – b = km

⇔ (a – b)c = ckm

⇔ ac = bc + Km

⇔ ac º bc (mod m)

2.     (i) a º b (mod m) Û  a = b + k1m

     c º d (mod m) Û  c = d + k2m +

Û (a + c) = (b + d) + (k1 + k2)m

Û (a + c) = (b + d) + km (k = k1 + k2)

Û (a + c) = (b + d) (mod m)

Contoh

Misalkan 17 º (mod 3) dan 10 º 4 (mod 3) maka menurut Teorema 2

a.    17 + 5 = 2 + 5 (mod 3) Û  22 = 7 (mod 3)

b.    17 . 5 = 5 . 2 (mod 3) Û  85 = 10 (mod 3)

c.    17 + 10 = 2 + 4 (mod 3) Û  27 = 6 (mod 3)

d.    17 . 10 = 2 . 4 (mod 3) Û 170 = 8 (mod 3)

·       Perhatikanlah bahwa Teorema 2 tidak memasukkan operasi pembagian pada aritmetika modulo karena jika kedua ruas dibagi dengan bilangan bulat, maka kekongruenan tidak selalu dipenuhi. Misalnya:

(i)    10 º 4 (mod 3) dapat dibagi dengan 2 karena 10/2 = 5 dan 4/2 = 2 dan 5 º 2 (mod 3)

(ii)  14 º 8 (mod 6) tidak dapat dibagi dengan 2, karena 14/2 = 7 dan 8/2 = 4 tetapi 7 º/ 4 (mod 6).

Sumber:

https://informatika.stei.itb.ac.id/~rinaldi.munir/Kriptografi/Teori%20Bilangan.pdf