9
2.1.4.
Congnum:es
Salah
satu
dasar
dari Teori
Bilangan
yang sar.gat
berguna adalah aritmatika
modular atau
kongruensl (Congruences).
Deiinisi
:
Untuk bi!angan
integer a,b,n
sebagai
bilanga1"1 integer dengan 11 ,c 0.
Maka
a ""
b
(
mod
n
)
a
adalah
kongruen dengan
b
mod
11
CGntoh
:
32
=
7
(
mod
5
)
;
-12
=
37 ( mod
7)
;
17
"'
17 ( mod
7)
Proposisi
-
proposisi dalam
Kongruensi yang
sering
dipakai
adalah
:
Proposisi
1
:
Untuk
bilangan
integer
a,b,c,n
sebagai
bi!angan
i:"'lteger dengan
n
tc 0
1.
a
=
0
(
mod
n
}jika
dan
hanya
jika 11
Ia
2.
a
=
a
(
mod
11 )
3.
a=
b
(mod n)
jika dan
hanyajika b =a
(mod n)
4.
Tl.ka a
=
b
(mod n)
dan b
=
c
(mod n ), maka a
'"' c (mod n)
Proposisi 2 :
Untuk
bilangan
integer
a,b,c,d,n
sebagai
bilangan
integer
dengan
n tc 0
dan
a
=
b
(mod
n)
dan c
=
d
(
mod n ).
Maka
a
+
c
b
+
d
(
mod
n
) , a - c
=
b
-
d
(
mod n ), ac
=
bd ( mod
n
)
 |