55
Berdasarkan
Teorema
2.1.4.10
berakibat
bahwa
h
|
nk ,
sehingga
diperoleh
bahwa
?
?
?
h
?
?
h
?
?
h
?
|
k
. Karena
m
=
order
g
n
,
maka ?
?
|
m
,
di
lain
pihak
diketahui
m
|
?
?
.
?
g
?
?
g
?
?
g
?
Akibatnya, diperoleh
m
=
h
. Dengan kata lain
order
g
n
=
g
h
gcd
(h, n)
.
Teorema 2.1.4.12. (Buchmann, 2000)
Jika
G
adalah
grup
siklik
dan
berhingga,
maka G mempunyai pembangun sebanyak
?
(G ) dan order setiap pembangunnya sama
dengan order G
.
Bukti:
Diberikan
g
?
G
yang
mempunyai
order
s,
maka
g
membangun
suatu
subgrup
g
dengan
g =
s
.
Selanjutnya,
suatu
elemen
G
yang
membangun
G
mempunyai
order
|G|.
Akan
diselidiki
elemen-elemen
G
yang
mempunyai
order
|G|.
Misalkan
g
adalah
pembangun
G,
maka
G
=
{g
k
:
0
=
k
=
G
}. Menggunakan
Teorema
2.1.4.11,
elemen
dari
himpunan
ini
mempunyai
order
|G|
jika
dan
hanya
jika
gcd
(k , G
)
=
1
.
Hal
ini
menunjukkan bahwa banyaknya pembangun dari G ada sebanyak
?
(G ).
F.
Teorema Fermat
Berikut
ini
diberikan
sebuah
teorema
yang
cukup
terkenal
dalam
kriptografi.
Teorema ini disebut dengan teorema Fermat, seperti diberikan pada Teorema 2.1.4.13 di
bawah ini.
Teorema 2.1.4.13. (Buchmann, 2000)
Untuk
sebarang
a
?
(
m
)
=
1
(mod m)
.
a
?
(Z
m
,*
)
berlaku
 |