41
Berikut
ini
diberikan
beberapa
teorema
yang
menjelaskan
sifat-sifat
persamaan
kongruen.
Teorema 2.1.4.1. (Buchmann, 2000) Diberikan
persamaan
kongruen
a
=
b
(mod m)
dan
c
=
d
(mod m),
maka
berlaku
ac = (bd )
(mod m).
Bukti:
-
a
=
-b
(mod m)
,
a
+
c
=
(b + d )
(mod m)
dan
Karena m membagi (a – b),
maka m juga
membagi (–a + b), akibatnya terbukti
-
a b + c - d
=
-b
(mod m)
.
Karena
m
membagi
(a
–
b)
dan
(c
–
d),
maka
m
juga
membagi
(a - b + c - d
) = (a + c)
-
(b +
d
)
,
dengan
kata
lain
terbukti
a
+
c
=
(b + d )
(mod m)
.
Untuk membuktikan
ac = (bd )
(mod m), misalkan
a
=
b
+
lm
dan
c
=
d
+
km , maka
ac =
(b + lm)(d + km)
=
bd +
m
(ld + kb + lkm)
(
ac - bd
)
, terbukti bahwa
ac = (bd )
(
mod m
)
.
atau
dengan
kata
lain
m
membagi
Teorema 2.1.4.2 (Stinson, 1995)
Diberikan
sebarang
a, b ? Z ,
m
?
Z
positif,
r1 = a mod
m
dan
r2
=
b
mod m , maka
a
=
b
(mod m) jika dan hanya jika
r1 =
r2 .
Bukti:
?
Diketahui
a
=
b
(mod m)
dengan
m
?
Z
positif,
akan
ditunjukkan
bahwa
r1 =
r2 .
Karena
a
=
b
(mod m)
maka
menggunakan
algoritma
pembagian
pada
bilangan
bulat
(Teorema 2.1.2.2) terdapat
q1 , q2
?
Z
dan
r1 , r2
?
Z
yang tunggal sedemikian hingga:
a
=
q1m + r1
,
0
=
r1 <
m
 |