47
Teorema 2.1.4.5. (Buchmann, 2000) Elemen
a
?
Z
m
merupakan unit jika dan hanya jika
gcd
(a, m)
=
1. Jika
gcd
(a, m)
=
1, maka invers a tunggal.
Bukti:
?
Misalkan
g
=
gcd
(a, m)
dan
x
?
Z
m
menjadi
solusi
penyelesaian
dari
persamaan
kongruen
(2.7). Karena
g
=
gcd
(a, m)
,
maka
g
|
m
dan
g
|
a
.
Menurut Definisi 2.1.4.1,
maka
g
|
(ax - 1) . Oleh karena
itu,
g
|
1. Karena pembagi dari 1 adalah 1 sendiri,
maka
diperoleh
gcd
(a, m)
=
1.
?
Diberikan
gcd
(a, m)
=
1
menggunakan Akibat 2.1.2.2 maka terdapat bilangan bulat x
dan y
sedemikian
hingga ax + my = 1. Menggunakan
Akibat 2.1.2.1 diperoleh bahwa x
adalah solusi penyelesaian dari persamaan kongruen (2.7) sehingga x adalah
invers dari
a
?
Z
m
.
Untuk membuktikan sifat ketunggalan x sebagai invers dari a digunakan langkah
sebagai berikut. Diambil
v
?
Z
m
sebagai
invers yang
lain dari a,
maka
ax =
av
(mod m)
.
Akibatnya
m
|
a
(x - v). Karena
gcd
(a, m)
=
1, maka m adalah pembagi dari x – v. Hal ini
membuktikan bahwa
x
=
v
(mod m)
. Dengan kata lain terbukti bahwa invers dari a
adalah tunggal.
Selanjutnya, dapat dilihat bahwa suatu
a
?
Z
m
,
a
?
0
dapat merupakan pembagi
nol atau juga merupakan unit.
Contoh 2.1.4.3.
Diberikan m = 8,
a
?
Z
8
merupakan unit dalam
Z
8
jika
gcd
(a,8)
=
1
.
Dari sini diperoleh
bahwa elemen-elemen
Z
8
yang
mempunyai
invers adalah 1, 3, 5 dan 7,
masing-masing
inversnya adalah 1, 3, 5 dan 7.
 |