Pembuktian Banyaknya Generator Grup Siklik Zpq

Soal Struktur Aljabar nomer 8


8.Misalkan p dan q adalah bilangan – bilangan prima. Tentukan banyaknya generator untuk grup siklik Zpq
Jawab
a). p,q prima dengan p ≠ q , maka
Zpq = {0,1,2,…,pq-1}
|Zpq | = pq , banyaknya elemen Zpq adalah pq
Elemen Zpq yang dapat menjadi generator (membangun) Zpq hanya elemen yang relatif prima terhadap p atau q.
(Jelas bahwa elemen tersebut juga juga akan relatif prima terhadap pq)
Yaitu n ∈ Zpq dengan GCD(n,pq)=1
[ GCD = Greatest Common Divisor , yaitu Faktor Persekutuan terBesar (FPB) ]
Sedemikian hingga, jika m ∈ Zpq , dengan GCD(m,pq)≠1 , maka m BUKAN generator dari Zpq
Jadi
p.1 = p
p.2 = 2p
p.3 = 3p
.
.
.
p.(q-1) = (q-1)p
_______________________
Sebanyak q-1

Jelas bahwa p,2p,3p,…,(q-1)p Bukan generator dari Zpq
Karena GCD(p,pq) = p , GCD(2p,pq) = p
Secara umum GCD(p,pq) = GCD(2p,pq) = ⋯ = GCD[(q-1)p,pq] = p
Diperoleh GCD nya adalah p, bukan 1
Sehingga p,2p,3p,…,(q-1)p ( yang sebanyak q-1 ) tidak relatif prima dengan pq

Dengan cara yang sama
q.1 = q
q.2 = 2q
q.3 = 3q
.
.
.
q.(p-1) = (p-1)q
________________________
Sebanyak p-1

Jelas bahwa q,2q,3q,…,(p-1)q Bukan Generator Zpq
Karena GCD(q,pq) = GCD(2q,pq)= GCD(3q,pq) = ⋯ = GCD[(q-1)p,pq] = q
Diperoleh GCD nya adalah q, bukan 1
Sehingga q,2q,3q,…,(p-1)q ( yang sebanyak p-1 ) tidak relatif prima dengan pq

Sementara itu 0 ∈ Zpq tidak mungkin membangun Zpq
Karena 0 dioperas biner +pq sebanyak apapun, akan selalu menghasilkan 0 itu sendiri
Sehingga kemungkinan banyaknya elemen Zpq yang dapat menjadi generator Zpq = pq-1
(Dikurangi 1 karena 0 ∈ Zpq tidak termasuk)
Untuk selanjutnya dapat ditulis Zpq\{0} dengan |Zpq\{0}| = pq-1 adalah kemungkinan banyaknya generator Zpq
Sehingga
Banyaknya generator Zpq = Banyaknya elemen Zpq selain 0 - Banyaknya elemen yang tidak relatif prima dengan pq
= |Zpq\{0}| - [(q-1)+(p-1)]
= pq - 1 - (p + q - 2)
= pq - 1 - p - q + 2
= pq - p - q + 1
= (p-1)(q-1)

b). p,q prima dengan p = q , maka
Zpq = Zpp = Z(p^2 ) = {0,1,2,…,p^2 - 1}
|Z(p^2 )| = p^2 , banyaknya elemen Z(p^2 ) adalah p^2
Elemen Z(p^2 ) yang dapat menjadi generator (membangun) Z(p^2 ) hanya elemen yang relatif prima terhadap p^2.
Sebaliknya, elemen yang tak relatif prima dengan p^2 adalah
p.1 = p
p.2 = 2p
p.3 = 3p
.
.
.
p.(p-1) = (p-1)p
__________________________
Sebanyak p-1

Jelas bahwa p,2p,3p,…,(p-1)p tak relatif prima dengan p^2 , karena GCD nya adalah p ( GCD ≠ 1 )
Sementara itu 0 ∈ Z(p^2 ) tidak mungkin membangun Z(p^2 )
Sehingga,
Banyaknya generator Z(p^2 ) = Banyaknya elemen Z(p^2) selain 0 - Banyaknya elemen yang tidak relatif prima dengan p^2
= |Z(p^2 )\{0}| - (p-1)
= p^2 - 1 - (p-1)
= p^2 - 1 - p + 1
= p^2 - p




NB : Catatan sebagai ilustrasi
1. Banyaknya Elemen Zn adalah banyaknya seluruh elemen Zn selain 0 dikurangi dengan banyaknya elemen Zn yang relatif prima dengan n

Ilustrasi : Misal n = 4
Zn = {0, 1, 2, 3} sehingga |Zn| = 4
Elemen yang tak relatif prima dengan 4 adalah 2, karena GCD(2,4) = 2 , tidak sama dengan 1

Sehingga banyaknya generator Zn adalah 4-1 (elemen Zn selain 0) dikurangi 1 ( karena 2 elemen Zn tidak relatif prima dengan 4)
Maka banyaknya generator = 4 - 1 - 1 = 2

Banyaknya Generator Z4 adalah 2 yaitu <1> dan <3>
Perhatikan bahwa
0 = 1+1+1+1,
1 = 1,
2 = 1+1,
3 = 1+1+1
Sehingga {0,1,2,3} dibangun oleh <1>

Demikian juga
0 = 3+3+3+3,
1 = 3+3+3,
2 = 3+3,
3 = 3
Sehingga {0,1,2,3} dibangun oleh <3>

Perhatikan juga bahwa GCD(1,4) = GCD(3,4) = 1
1 dan 3 relatif prima dengan 4



Kita menuju kepada fakta lainnya bahwa
.`. Banyaknya generator Zn adalah sama dengan Banyaknya elemen yang RELATIF PRIMA dengan n


2. Jika p,q prima dengan p ≠ q , Maka banyaknya generator Zpq = (p-1)(q-1)

Ilustrasi : Misal p = 2, q = 7 , maka pq = 2x7 = 14
Zpq = Z14 = {0,1,2,3,4,5,6,7,8,9,10,11,12,13}
Elemen elemen yang relatif prima dengan 14 yaitu 1, 3, 5, 9, 11, 13
Jadi pembangun Z14 adalah <1>, <13>, <3>, <11>, <5>, <9>
Banyaknya pembangun = 6
Sesuai dengan rumus (p-1)(q-1) = (2-1)(7-1) = 1 x 6 = 6 generator


3. Jika p,q prima dengan p = q , Maka banyaknya generator Zpp = p^2 - p

Ilustrasi : Misal p = 3, maka pp = p^2 = 3x3 = 9
Zpp = Z9 = {0,1,2,3,4,5,6,7,8}
Elemen elemen yang relatif prima dengan 9 yaitu 1, 2, 4, 5, 7, 8
Jadi pembangun Z9 adalah <1>, <8>, <2>, <7>, <4>, <5>
Banyaknya pembangun = 6
Sesuai dengan rumus p^2 - p = 3^2 - 3 = 9 - 3 = 6 generator