10
2.1.5. Division
PembagiaG
(division)
dengan
mod
n
jauh
lebili s:ulit
dibandingkan
dengan
Mangan
rasionaL
Aturan
umum
yang
berla1:u
adalah
pembagian
a
(
mod
11 )
bisa
di!akukan jika gcd ( a,n ) = 1.
Proposisi-proposisi
yang berlaku di dalam
pembagian:
Proposisi
1
:
Untuk
bilangan
integer a,b,c,n sebagai
bi!angan integer
dengan
n
,c
0
dan
gcd(
a,n
)
=1.
Jika ab
=
ac ( mod n ), maka b
""
c
( mod n ).
Proposisi
2
:
gcd(
a,n ) '!. Untuk bilangan
integer s
dan
t
sebagai
bilangan
integer d.i
ma."la
as
+
sf
=
1. Maka as
s:z
1
(
mod n ),
juga
untuk
invers multiplikatif dari
a
(
mod
n
).
2.L6.
Fermat's
Little Theorem
dan
Euler's
Them-em
Kedua teorema
merupakan
dua
dari
banyak
hasil
yang
paling
mendasar
yang
dihasilkan
oleh
Teori
Bilangan.
Kedua
teorema
ini
dikatakan
telah
terbuk1i dalam
memegang
peranan penting dalam ap!ikasi kriptografi,
FermaJ's Little
Theorem
:
Jika p adalah
bi!angan prima dan
p
tidak
membagi a,
maka
d'"¹
os
I( modp)
 |