54
h
n
?
Diketahui
g
u
=
1
dengan
u
=
qk + r ,
0
=
r
<
k
. Diperoleh:
g
r
=
g
u
-
qk
=
g
u
(g
k
)
-
q
=
1
.
Karena
k
adalah
bilangan
bulat
positif
terkecil
sehingga
g
k
=
1
dan
karena
0
=
r
<
k
,
diperoleh
r
=
0
, sehingga
u
=
qk
untuk suatu
q
?
Z
.
Akibat 2.1.4.1. (Buchmann, 2000)
Diberikan
dan hanya jika
l
=
k
(mod order
g
)
.
Bukti:
g
?
G
dan
k l ? Z , maka
, l ? Z , maka
g
l
=
g
k
jika
Ditentukan
u
=
l
-
k
. Menggunakan Teorema 2.1.4.10 maka
g
u
=
g
l
-
k
=
1
jika dan
hanya jika order
g
|
(l - k
)
. Terbukti bahwa
l
=
k
(mod order
g
)
.
Teorema 2.1.4.11. (Buchmann, 2000)
Jika
g
?
G
mempunyai
order
h
dan
jika
n
?
Z
,
maka order
g
n
=
h
.
gcd
(
h, n
)
Bukti:
Misalkan
g
=
gcd
(h, n) dan
m
=
order
g
n
. Akan dibuktikan bahwa
m
=
h
. Oleh karena
g
(g
n
)
g
=
(g
h
)
g
n
=
1
g
=
1,
?
h ?
menggunakan Teorema 2.1.4.10 diperoleh bahwa
m
|
?
?
.
Misalkan untuk suatu
k
?
Z
?
g
?
berlaku:
1
=
(g
n
)
k
=
g
nk
.
 |