zhu zubaedah: Maret 2013

Ø KONGRUENSI

Teori Kongruensi

Pada bab ini dipelajari aritmatika modular yaitu aritmatika tentang kelas-kelas ekuivalensi, dimana permasalahan dalam teori bilangan disederhanakan dengan cara mengganti setiap bilangan bulat dengan sisanya bila dibagi oleh suatu bilangan bulat tertentu n. Sebelum masuk ke aritmatika modular diperhatikan dulu masalah sederhana berikut Misalkan hari ini adalah Sabtu, hari apa setelah 100 hari dari sekarang?

Penyelesaian. Cara 'konyol' menjawab pertanyaan ini adalah menghitung langsung satu per satu hari-hari pada kalender sampai dengan hari ke 100. Tetapi dengan mengingat terjadi pengulangan secara periodik setiap 7 hari maka permasalahan ini mudah diselesaikan dengan menghitung sisanya jika 100 dibagi 7, yaitu ; 100 = 14 x 7 + 2:

Jadi 100 hari mendatang adalah hari ke 2 dari sekarang, yaitu Senin.

Aritmetika Modulo

· Misalkan a adalah bilangan bulat dan m adalah bilangan bulat > 0. Operasi a mod m (dibaca “a modulo m”) memberikan sisa jika a dibagi dengan m.

· Notasi: a mod m = r sedemikian sehingga a = mq + r, dengan 0 £ r < m.

· Bilangan m disebut modulus atau modulo, dan hasil aritmetika modulo m terletak di dalam himpunan {0, 1, 2, …, m – 1} (mengapa?).

Contoh : Beberapa hasil operasi dengan operator modulo:

(i) 23 mod 5 = 3 (23 = 5 × 4 + 3)

(ii) 27 mod 3 = 0 (27 = 3 × 9 + 0)

1.1 Kongruen

ab≡ (mod m)

Definisi : jika m adalah suatu bilangan positif dan α, b, ϵ B, demikian sehingga m | (a-b), maka dikatakan “a kongruen b modula m” ditulis :

a≡b (mod m) ↔a-b = k.m

Dengan perkataan lain :

Contoh : 3|(8-2), ditulis dalam bentuk kongruensi

8≡2 (mod 3), yang artinya 8-2 adalah kelipatan 3.

a ≢ b (mod m)

Bila m tidak habis membagi (a-b), maka dikatakan “a inkongruensi b modula m” ditulis :

Contoh : 3+ (8-3), ditulis dalam bentuk kongruensi

8 ≡ 3(mod 3) artinya 8-3 =3 bukan kelipatan 3

Bila b=0, maka m membagi a, (m|a) atau a kelipatan m, maka a = k.m atau a ≡ 0 (mod m)

· Misalnya 38 mod 5 = 3 dan 13 mod 5 = 3, maka kita katakan 38 º 13 (mod 5) (baca: 38 kongruen dengan 13 dalam modulo 5).

· Misalkan a dan b adalah bilangan bulat dan m adalah bilangan > 0, maka a º b (mod m) jika m habis membagi a – b.

· Jika a tidak kongruen dengan b dalam modulus m, maka ditulis a ≢b (mod m) .

1.2 Sifat-Sifat Relasi Kongruensi

Relasi dengan tanda ≡ pada a ≡ b (mod m) disebut relasi kongruensi. Relasi kongruensi mempunyai sifat-sifat yang sama seperti relasi kesamaan. Untuk a,b.c dan d ϵ B, dan m ϵ N (Bilangan Asli). Relasi kongruensi memenuhi sifat-sifat :

a. Reflektif , yaitu a ≡ a (mod m).

Sebab a-a=0, dimana 0 kelipatan m, yaitu 0= 0 x m

b. Simetri, jika a ≡ b (mod m), maka b ≡ a (mood m).

Bukti : a ≡ b (mod m) → a-b = k. m

-(b-a)=k.m

b-a =k.(-m) = k.m

jadi b ≡ a (mod m).

c. Transitif. Jika a ≡ b (mod m), b ≡ c (mod m), maka berlaku a ≡ c (mod m)..

Bukti : a ≡ b (mod m) → a-b = k₁.m

b ≡ c (mod m) → b-c = k₂.m +

a-c = k.m

jadi a ≡ c (mod m)

1.3.Sifat-sifat Pengerjaan Hitung Pada Kongruensi

1.3.1 Dalil-dalil pada penjumlahan

a. jika a ≡ b (mod m), maka (a+c) ≡ (b+c) (mod m)

Bukti : a ≡ b (mod m) maka a-b = k.m

(a+c)- (b+c) = k.m

Jadi (a+c) ≡ (b+c) (mod m)

b. jika a ≡ b (mod m) dan c ≡ d (mod m), maka (a+c) ≡ (b+d) (mod m)

bukti : a ≡ b (mod m) maka a-b = k₁.m

c ≡ d (mod m) maka c-d = k₂.m +

(a-b) + (c-d) = (k₁+k₂) m

(a+c) – (b+d) = k .m

Jadi (a+c) ≡ (b+d) (mod m)

c.jika (a+c) ≡ (b+c) (mod m), maka a ≡ b (mod m)

bukti : (a+c) ≡ (b+c) (mod m) , maka (a+c) – (b+c) = k.m

a –b = k.m

jadi a ≡ b (mod m)

1.3.2. Dalil-dalil pada Perkalian

a. Jika a ≡ b (mod m), maka ac ≡ bc (mod m)

Bukti : jika a ≡ b (mod m) maka a-b = k.m

(a -b) c = k.m

ac-bc = k.m

jadi ac ≡ bc (mod m)

b. Jika a ≡ b (mod m) dan c ≡ d (mod m), maka ac ≡ bd (mod m)

c ≡ d (mod m) maka bc ≡ bd (mod m) → bc-bd = k2 .m +

ac-bd = k.m

jadi ac ≡ bd (mod m)

c. Jika ac ≡ bc (mod m), maka tidak selalu a ≡ b (mod m)

contoh : 39 ≡ 15 (mod 12)

≡ 5.3 (mod 12)

13 ≡ 5 (mod 12)

d. Jika ac ≡ bc (mod m) = 1, maka a ≡ b (mod m)

Contoh : 28 ≡ 8 (mod 5)

7. 4 ≡ 2.4 (mod 5) karena (4,5) = 1 maka

7 ≡ 2 (mod 5)

e. Jika ac ≡ bc (mod m) dan (c,m) = d, maka a ≡ b (mod m/d)

Bukti : diketahui ac ≡ bc (mod m), maka ac –bc = (a-b) c│m

m/d pembagi m, sedangkan m membagi (a-b)c maka

m/d membagi (a-b)c

(c,m) = d maka (m/d,c) = 1, oleh karena itu m/d pembagi (a-b)

Atau dengan kata lain a ≡ b (mod m/d)

f. Jika a ≡ b (mod m) maka aⁿ≡ bⁿ (mod m)

Contoh :

1. Sederhanakanlah 120 ≡ 168 ( mod 24 )

Jawab :

5.24 ≡ 7.25 ( mod 24 ), karena (24, 24) =24 maka 5 ≡ 7 ( mod 1 )

2. . Tunjukkan bahwa 2²⁰ dibagi 7 sisanya 4

Jawab :

8 – 1 = kel. 7

8 ≡ 1 ( mod 7)

2³ ≡ 1 ( mod 7)

(2³)⁶ ≡ (1)⁶ ( mod 7)

2¹⁸ ≡ 1 ( mod 7)

2¹⁸.2² ≡ 1.2² ( mod 7)

2.²⁰ ≡ 4 ( mod 7) atau 2.²⁰ - 4 = kel. 7 + 4

Jadi 2.²⁰ dibagi 7 sisanya 4

1.4 kongruensi Linear

1.4.1. Kelas residu

Bilangan bulat yang dibagi oleh 3 maka sisanya adalah 0,1 atau 2. Dengan kata lain bilangan bulat tersebut telah dijadikan 3 kelas yang berbedaS, yaitu kelas yang kongruen dengan 0 modulo 3 ( x ≡ 0 (mod 3)), kelas yang kongruen dengan 2 modulo 3 (x ≡ 2 (mod 3)). Dikatakan bahwa kumpulan bilangan bulat yang telah dipisahkan menjadi 3 himpunan bilangan yang disebut ; “kelas-kelas residu modulo 3”, yang dinotasikan dengan [ 3 ].

Jadi kelas-kelas residu modulo 3 adalah sebagai berikut.

1. Himpunan bilangan yang kongruensi 0 (mod 3) yaitu [ 0 ] = {…, -9,-6,-3,0,3,6,9,…}

2. Himpunan bilangan yang kongruensi 1 (mod 3) yaitu [ 1 ] = {…, -8,-5,-2,1,4,7,10,…}

3. Himpunan bilangan yang kongruensi 2 (mod 3) yaitu [ 2 ] = {…, -7,-4,-1,0,2,5,8,11…}

Jelaslah bahwa setiap bilangan pada satu kelas residu tersebut tentu kongruensi modulo 3 satu sama lain, sebaliknya bilangan-bilangan pada kelas residu yang berbeda ( pada lain kelas ) ingkongruensi-kongruensi berikut adalah ekivalen:

a. x ≡ 0 (mod 3), x ≡ 3 (mod 3), x ≡ 6 (mod 3), x ≡ -3 (mod 3).

b. y ≡ -5 (mod 3), y ≡ -2 (mod 3), y ≡ 1 (mod 3), y ≡ 4 (mod 3).

c. z ≡ -4 (mod 3), z ≡ -1 (mod 3), z ≡ 2 (mod 3), z ≡ 5 (mod 3).

Contoh lain untuk [ 5 ] adalah :

i. {…, -10,-5,0,5 ,10,…}

ii. {…, -9,-4,1,6 ,11,…}

iii. {…, -8,-3,2,7 ,12,…}

iv. {…, -7,-2,3,8 ,13,…}

v. {…, -6,-1,4,9 ,14,…}

1.4.2. Persamaan kongruensi berderajat 1 (kongruensi linier)

ax ≡ b (mod m)

Bentuk umum persamaan kongruensi linier adalah :

Bila kita menyelesaikan persamaan kongruensi linier tersebut artinya kita mencari nilai x sehingga memenuhi kongruensi tersebut.

Dalil -1 : kongruensi linier ax ≡ b (mod m) mempunyai himpunan penyelesaian dalam bentuk kongruensi dengan modulo yang sama.

Dalil -2 : kongruensi linier ax ≡ b (mod m) mempunyai himpunan penyelesaian jika (a,m) membagi b atau (a,m) | b.

Dalil -3 : Banyaknya himpunan penyelesaian kongruensi linier ax ≡ b (mod m) sama dengan nilai (a,m), jawaban lain pada kelas residu yang sama dianggap 1 himpunan penyelesaian.

Contoh :

1. Tentukan himpunan penyelesaian dari kongruensi linier 4x ≡ 5 (mod 6)

Jawab :

(4,6) = 2, dimana 2 bukan pembagi 5, maka persamaan kongruensi 4x ≡ 5 (mod 6) tak mempunyai penyelesaian.

1.5. Persamaan kongruensi berderajat dua

ax² +bx +c = 0 ( mod m )

Bentuk umumnya adalah :

Contoh soal :

1. Carilah dua sebuah bilangan positif berurutan, yang bukan 3 dan 4, yang hasil baginya 12 lebih dari kelipatan 111.

Jawab : misalkan bilangan I = x , bilangan II = x + 1

x ( x + 1 ) ≡ 12 (mod 111)

x² + x - 12 ≡ 0 (mod 111)

4x² + 4x - 48 ≡ (mod 111)

4x² + 4x + 1 ≡ 49 (mod 111)

( 2x + 1 )² ≡ 49 (mod 111)

Misalkan y ≡ 2x +1 (mod 111)

y² ≡ 49 (mod 111)

y ≡ ± 7 (mod 111)

Ø y ≡ 77 (mod 111) y ≡ -7 (mod 111)

2x + 1 ≡ 77 (mod 111) 2x + 1 ≡ -7 (mod 111)

x ≡ 3 (mod 111) 1 ≡ -4 (mod 111)

Jadi, bilangan I = k.111+3 Jadi, bilangan I = k.111 + 107

bilangan II = k.1111+4 bilangan II = k.111 + 108

Jadi, bilangan-bilangan yang memenuhi adalah 107 dan 108

Ø PERSAMAAN DIOPHANTINE

1.2 Pengertian Diophantine

Persamaan Diophantine adalah persamaan bersuku banyak ax + by = c, di mana a, b dan c adalah bilangan-bilangan integer (bulat), mempunyai penyelesaian jika dan hanya jika gcd(a,b) membagi c. Contoh persamaan Diophantine ax + by = c : 2x + 4y = 26.

Persamaan Diophantine adalah persamaan yang jawabannya harus dicari hanya pada himpunan bilangan bulat. Koefisien dari persamaan juga hanya melibatkan bilangan bulat. Tidak ada bilangan pecahan di persamaan ini.

Contoh :

a) 2x = 7

Persamaan ini tidak mempunyai jawab di himpunan bilangan bulat, persamaan ini akan mempunyai jawab di himpunan bilangan real.

b) Apakah persamaan 6x + 51y = 22 mempunyai jawab di himpunan bilangan bulat?

Jawab :

jika persamaan mempunyai jawaban di himpunan bilangan bulat, kita lihat bahwa:

· 3 membagi 6 dan 3 juga membagi 51.

· 3 membagi di ruas kiri, tetapi 3 tidak membagi 22.

· Dengan kata lain, 3 tidak membagi ruas kanan. Jadi, tidak mungkin ada bilangan bulat yang memenuhi persamaan tersebut.

c) Apakah persamaan 56x + 72y = 40 mempunyai jawaban untuk himpunan bilangan bulat?

Sekarang kita akan mencari nilai-nilai yang mungkin dalam himpunan bilangan bulat.

o Kita sederhanakan persamaan yang kita punya dengan cara membaginya dengan 8.

Diperoleh : 7x + 9y = 5

o Persamaan yang diberikan adalah 7x + 9y = 5 . Karena Faktor Persekutuan Terbesar (FPB) dari 7 dan 9 adalah 1. Maka kita akan menuliskan persamaan dalam bentuk lain agar dapat diselesaikan dengan menggunakan algoritma pembagian.

Persamaan menjadi : 7a + 9b = 1

o Langkah selanjutnya yaitu mencari nilai a dan b yang memenuhi dengan menggunakan algoritma pembagian.

Û 9 = 1 (7) + 2

7 = 3 (2) + 1

Û Jadi : 1 = 7 – 3(2)

1 = 7 - 3(9 – 7)

1 = 7(4) – 9(3)

Diperoleh: a = 4 dan b = -3

o Sekarang persamaan terakhir kita kalikan 5.

7a + 9b = 1 (kedua ruas dikalikan 5)

Û 7(5a) + 9(5b) = 1

Sehingga diperoleh x = 5a dan y = 5b

dan diperoleh x = 20x dan y = -15 .

o Untuk mencari jawaban yang lain,langkah yang harus kita lakukan adalah :

Misalkan jawaban lain yaitu p dan q.

Persamaan tersebut kita tulis sebagai :

Û 7x + 9y = 7p + 9p

7 (x – p) = 9 (q – y)

o Persamaan ini mengatakan bahwa 7 membagi ruas kiri. Maka ruas kanan juga harus habis dibagi 7. Karena Faktor Persekutuan Terbesar dari 7 dan 9 adalah 1, maka 7 membagi (q – y) , akibatnya (q – y) = 7k , untuk sebarang k bilangan bulat.

o Selanjutnya 7 ( x – p ) = 9 . 7k maka(x – p) = 9k, dengan k bilangan bulat.

o Sehingga jawaban persamaan yang lain yaitu dalam bentuk :

Û p = x – 9k

q = y + 7k dengan k adalah sebarang bilangan bulat.

Jawaban yang diperoleh yaitu :

Û p = 20 – 9k

q = -15 + 7k

pasangan jawabnya yaitu (k, p, q) : (3, -7, 6) , (2, 2, -1) , (1, 11, -8) dan seterusnya.

Ø FUNGSI EULER

Bilangan Prima

· Bilangan bulat positif p (p > 1) disebut bilangan prima jika pembaginya hanya 1 dan p.

· Contoh: 23 adalah bilangan prima karena ia hanya habis dibagi oleh 1 dan 23.

· Karena bilangan prima harus lebih besar dari 1, maka barisan bilangan prima dimulai dari 2, yaitu 2, 3, 5, 7, 11, 13, …. Seluruh bilangan prima adalah bilangan ganjil, kecuali 2 yang merupakan bilangan genap.

· Bilangan selain prima disebut bilangan komposit (composite). Misalnya 20 adalah bilangan komposit karena 20 dapat dibagi oleh 2, 4, 5, dan 10, selain 1 dan 20 sendiri.

Teorema 3. (The Fundamental Theorem of Arithmetic). Setiap bilangan bulat positif yang lebih besar atau sama dengan 2 dapat dinyatakan sebagai perkalian satu atau lebih bilangan prima.

Contoh

9 = 3 ´ 3 (2 buah faktor prima)

100 = 2 ´ 2 ´ 5 ´ 5 (4 buah faktor prima)

13 = 13 (atau 1 ´ 13) (1 buah faktor prima)

· Untuk menguji apakah n merupakan bilangan prima atau komposit, kita cukup membagi n dengan sejumlah bilangan prima, mulai dari 2, 3, … , bilangan prima £ Ön. Jika n habis dibagi dengan salah satu dari bilangan prima tersebut, maka n adalah bilangan komposit, tetapi jika n tidak habis dibagi oleh semua bilangan prima tersebut, maka n adalah bilangan prima.

Contoh

Tunjukkan apakah (i) 171 dan (ii) 199 merupakan bilangan prima atau komposit.

Penyelesaian:

(i) Ö171 = 13.077. Bilangan prima yang £ Ö171 adalah 2, 3, 5, 7, 11, 13. Karena 171 habis dibagi 3, maka 171 adalah bilangan komposit.

(ii) Ö199 = 14.107. Bilangan prima yang £ Ö199 adalah 2, 3, 5, 7, 11, 13. Karena 199 tidak habis dibagi 2, 3, 5, 7, 11, dan 13, maka 199 adalah bilangan prima.

· Terdapat metode lain yang dapat digunakan untuk menguji keprimaan suatu bilangan bulat, yang terkenal dengan Teorema Fermat. Fermat (dibaca “Fair-ma”) adalah seorang matematikawan Perancis pada tahun 1640.

Teorema 4 (Teorema Fermat). Jika p adalah bilangan prima dan a adalah bilangan bulat yang tidak habis dibagi dengan p, yaitu PBB(a, p) = 1, maka

a^p^–1 º 1 (mod p)

Contoh

Kita akan menguji apakah 17 dan 21 bilangan prima atau bukan. Di sini kita mengambil nilai a = 2 karena PBB(17, 2) = 1 dan PBB(21, 2) = 1. Untuk 17,

2^17–1 = 65536 º 1 (mod 17)

karena 17 tidak membagi 65536 – 1 = 65535 (65535

17 = 3855).

Untuk 21,

2^21–1 =1048576 º\ 1 (mod 21)

karena 21 tidak habis membagi 1048576 – 1 = 1048575.

· Kelemahan Teorema Fermat: terdapat bilangan komposit n sedemikian sehingga 2ⁿ^–1 º 1 (mod n). Bilangan bulat seperti itu disebut bilangan prima semu (pseudoprimes).

· Misalnya komposit 341 (yaitu 341 = 11 × 31) adalah bilangan prima semu karena menurut teorema Fermat,

2³⁴⁰ º 1 (mod 341)

Untunglah bilangan prima semu relatif jarang terdapat.

Contoh

Periksalah bahwa (i) 3¹⁶ º 1 (mod 17) dan (ii) 18⁶ º 1 (mod 49).

Penyelesaian:

(i) Dengan mengetahui bahwa kongruen 3³ º 10 (mod 17), kuadratkan kongruen tersebut menghasilkan

3⁶ º 100 º –2 (mod 17)

Kuadratkan lagi untuk menghasilkan

3¹² º 4 (mod 17)

Dengan demikian, 3¹⁶ º 3¹² × 3³ × 3 º 4 × 10 × 3 º 120 º 1 (mod 17)

(ii) Caranya sama seperti penyelesaian (i) di atas:

18² º 324 º 30 (mod 49)

18⁴ º 900 º 18 (mod 49)

18⁶ º 18⁴ × 18² º 18 × 30 º 540 º 1 (mod 49)

Fungsi Euler f

Fungsi Euler f medefinisikan f(n) untuk n ³ 1 yang menyatakan jumlah bilangan bulat positif < n yang relatif prima dengan n.

Contoh

Tentukan f(20).

Penyelesaian:

Bilangan bulat positif yang lebih kecil dari 20 adalah 1 sampai 19. Di antara bilangan-bilangan tersebut, terdapat f(20) = 8 buah yang relatif prima dengan 20, yaitu 1, 3, 7, 9, 11, 13, 17, 19.

Untuk n = 1, 2, …, 10, fungsi Euler adalah

f(1) = 0 f(6) = 2

f(2) = 1 f(7) = 6

f(3) = 2 f(8) = 4

f(4) = 2 f(9) = 6

f(5) = 4 f(10) = 4

· Jika n prima, maka setiap bilangan bulat yang lebih kecil dari n relatif prima terhadap n. Dengan kata lain, f(n) = n – 1 hanya jika n prima.

Contoh

f(3) = 2, f(5) = 4, f(7) = 6, f(11) = 10, f(13) = 12, …

Teorema 5. Jika n = pq adalah bilangan komposit dengan p dan q prima, maka f(n) = f(p) f(q) = (p – 1)(q – 1).

Contoh

Tentukan f(21).

Penyelesaian:

Karena 21 = 7 × 3, f(21) = f(7) f(3) = 6 × 2 = 12 buah bilangan bulat yang relatif prima terhadap 21, yaitu 1, 2, 4, 5, 8, 10, 11, 13, 14, 17, 19, 20.

Teorema 6. Jika p bilangan prima dan k > 0, maka f(p^k) = p^k – p^k^-1 = p^k^-1(p – 1) .

Contoh

Tentukan f(16).

Penyelesaian:

Karena f(16) = f(2⁴) = 2⁴ – 2³ = 16 – 8 = 8, maka ada delapan buah bilangan bulat yang relatif prima terhadap 16, yaitu 1, 3, 5, 7, 9, 11, 13.

Teorema 7 (Euler’s generalization of Fermat theorem). Jika PBB(a, n) = 1, maka

a^f⁽ⁿ⁾ mod n = 1 (atau a^f⁽ⁿ⁾ º 1 (mod n) )

Kita tahu teorema kecil fermat menyatakan

Untuk sebarang bilangan bulat

dan bilangan prima

yang coprime ke

berlaku
$a^{p-1}\equiv 1\pmod p$

Sekarang bagaimana jika modulusnya tidak prima, composite, apakah teorema kecil fermat masih berlaku? Tidak, sebagai contohnya jika kita ambil

dan

,
apakah $2^{14}\equiv 1\pmod {15}$ Tidak karena 15 tidak membagi $16383=2^{14}-1$ .
Akan tetapi ada cara memodifikasi teorema kecil fermat sehingga tetap berlaku meskipun modulusnya tidak prima. Teorema fermat yang udah dimodifikasi inilah yang disebut teorema euler.

Sebelum membahas teorema euler akan saya bahas mengenai fungsi euler-phi

Definisi: Fungsi phi-euler, adalah fungsi pada bilangan asli

yang didefinisikan sebgai berikut

$\phi\left(n\right)$ adalah banyaknya bilangan pada $\left\{ 1,2,3\ldots,n-1\right\}$ yang coprime ke

Contoh: $\phi\left(8\right)=4$ karena ada 4 bilangann asli yang kurang dari 8 yang coprime ke 8 ke-4 bilangan tersebut adalah 1,3,5,7. $\phi\left(11\right)=10$ kerna semua bilangan pada $\left\{ 1,2,3\ldots,10\right\}$ coprime ke 11.

Teorema

Jika prima maka $\phi\left(p\right)=p-1$
Jika prima dan $n\geq1$ maka $\phi\left(p^n\right)=p^n-p^{n-1}$

Bukti

1. Jika

prima maka semu bilangan pada $\left\{ 1,2,3\ldots,p-1\right\}$ coprime ke

, itu artinya $\phi\left(p\right)=p-1$
2. Ada

elemen pada himpunan $\left\{ 1,2,3\ldots,p^n\right\}$ . Elemen pada himpunan tersebut tidak coprime ke

jika hanya jika dapat dibagi oleh

. Elemen pada himpunan yang dapat dibagi oleh

adalah

$1p,\:,2p\:3\cdot p,\ldots,p^{n-1}\cdot p$

Ada sebanyak $p^{n-1}$ elemen yang tidak coprime ke

maka banyaknya elemen yang coprime ke

sebanyak $p^n-p^{n-1}$

Definisi: Sistem residu tereduksi mod

(reduced residue system mod

) adalah himpunan bilangan-bilangan

$a_{1},a_{2},a_{3},\ldots,a_{\phi\left(n\right)}$

Yang memenuhi

Jika $i\neq j$ maka $a_{1}\not\equiv a_{j}\pmod n$
Untuk setiap coprime ke

Dengan demikian Sistem residu tereduksi mod

merepresentasikan bilangan-bilangan yang coprime ke

Contoh: $\left\{ 1,5,7,11\right\}$ dan $\left\{ 11,17,-1,31\right\}$ keduanya merupakan sistem residu tereduksi mod

Lemma: Diberikan $\phi\left(n\right)=k$ dan $\left\{ a_{1},a_{2},\ldots,a_{k}\right\}$ adalah Sistem residu tereduksi mod

, berlaku:

Untuk semua bilangan bulat maka $\left\{ a_{1}+mn,a_{2}+mn,\ldots,a_{k}+mn\right\}$ merupakan sistem residu tereduksi mod .
Jika coprime ke maka $\left\{ ma_{1},ma_{2},\ldots,ma_{k}\right\}$ merupakan sistem residu tereduksi mod .

Akibat: Diberikan $\phi\left(n\right)=k$ dan $\left\{ a_{1},a_{2},\ldots,a_{k}\right\}$ adalah Sistem residu tereduksi mod

, jika

coprime ke

dan

sebarang bilangan bulat maka $\left\{ sa_{1}+t,sa_{2}+t,\ldots,sa_{k}+t\right\}$ merupakan sistem residu tereduksi mod

Contoh: $\left\{ 1,5\right\}$ merupakan sistem residu tereduksi mod

. tmabahkan $12=2\times 6$ pada setiap bilangan diperoleh $\left\{ 13,17\right\}$ , sistem residu tereduksi mod

lainnya, Kita tahu 6 coprime ke 25, jika kita kalikan sistem yang awal dengan 25 diperoleh $\left\{ 25,125\right\}$ istem residu tereduksi mod

lainnya, terakhir $\left\{ 25+12,125+12\right\}=\left\{ 37,137\right\}$ juga merupakan sistem residu tereduksi mod

Teorema Euler

Setiap bilangan bulat

dan

bilangan bulat positif yang coprime ke

maka :

$a^{\phi\left(n\right)}\equiv 1\pmod n$

Perhatikan jika

prima maka $a^{n-1}\equiv 1\pmod n$ , teorema euler berubah menjadi teorema kecil fermat. Dengan demikian kita bisa menganggap teorema euler sebagai generalisasi teorema kecil fermat.

Bukti: Ambil $\phi\left(n\right)=k$ dan $\left\{ a_{1},a_{2},\ldots,a_{k}\right\}$ adalah Sistem residu tereduksi mod

, diasumsikan

termuat di $\left\{ 1,2,3\ldots,n-1\right\}$ .

Karena

dan

coprime maka $\left\{a a_{1},aa_{2},\ldots,aa_{k}\right\}$ juga merupakans sistem residu tereduksi mod

, Kedua sistem tersebut haruslah mempunyai hasil perkalian modulus

yang sama

$\left(aa_{1}\right)\ldots\left(aa_{k}\right)\equiv a_{1}\ldots a_{k}\pmod n$

$a_{k}\left(a_{1}\ldots a_{k}\right)\equiv a_{1}\ldots a_{k}\pmod n$

Karean setiap

coprime ke

, jika dikalikan kedua sisi dengan $a_{1}^{-1}\ldots a_{k}^{-1}$ diperoleh

$a^{k}\equiv 1\pmod n$ atau dengan kata lain $a^{\phi\left(n\right)}\equiv 1\pmod n$

CONTOH SOAL

1. Apakah 22051946 bilangan kuadrat sempurna?

Jawab :

Cara umum untuk menjawab pertanyaan ini adalah dengan menghitung 22051946, jika hasilnya bulat maka ia kuadrat sempurna.

Cara lain adalah dengan cara mengkuadratkan bilangan-bilangan bulat, apakah hasilnya ada yang samadengan bilangan yang dimaksud.

Cara yang paling sederhana adalah dengan menggunakan sifat bilangan kuadrat sempurna, yaitu jika bilangan kuadrat sempurna dibagi 4 maka sisanya 0 atau 1. Artinya, jika sisanya selain dari 0 dan 1 maka dipastikan ia bukan kuadrat sempurna.

Diperoleh:

22051946 = 220519 x 100 + 46

Û 220519 x (25 x 4) + (11 x 4) + 2

Û (220519 + 25 + 11) x 4 + 2

ternyata memberikan sisa 2 sehingga disimpulkan bukan kuadrat sempurna.

2. Perlihatkan bahwa persamaan x² + y² + z² = 2xyz

hanya mempunyai jawab nol pada himpunan bilangan bulat.

Jawab :

Jika persamaan mempunyai jawab di himpunan bilangan bulat, maka ruas kanan dari persaam harus merupakan bilangan genap. Maka ruas kiri juga harus bilangan genap. Jadi, satu atau ketiga dari x, y dan z harus merupakan bilangan genap.

Jika hanya ada satu yang habis dibagi 2, maka ruas kanan habis dibagi 4. Tetapi ruas kiri hanya habis dibagi 2. Itu tidak mungkin. Jadi ketiganya harus merupakan bilangan genap. Kita tulis :

x = 2a , y = 2b, z = 2c

kita gantikan pada persamaan. Diperoleh :

a² + b² + c² = 4abc

Dengan alasan yang sama. Kita menyimpulkan bahwa setiap jawaban dari persamaan ini selalu habis dibagi 2. Dengan kata lain bilangan itu hanya nol.

3. Tentukan balikan (modulo invers) dari 4 (mod 9).

Jawab :

Karena PBB(4, 9) = 1, maka balikan dari 4 (mod 9) ada. Dari algoritma Euclidean diperoleh bahwa : 9 = 2 × 4 + 1

o Susun persamaan di atas menjadi : –2 × 4 + 1 × 9 = 1

Dari persamaan terakhir ini kita peroleh –2 adalah balikan dari 4 modulo 9. Periksalah bahwa

Û –2 × 4 º 1 (mod 9) (9 habis membagi –2 × 4 – 1 = –9)

4. Tentukan balikan (modulo invers) dari 17 (mod 7)

Jawab :

Karena PBB(17, 7) = 1, maka balikan dari 17 (mod 7) ada. Dari algoritma Euclidean diperoleh

rangkaian pembagian berikut:

17 = 2 × 7 + 3 (i)

7 = 2 × 3 + 1 (ii)

3 = 3 × 1 + 0 (iii) (yang berarti: PBB (17, 7) = 1) )

o Susun (ii) menjadi : 1 = 7 – 2 × 3 (iv)

o Susun (i) menjadi : 3 = 17 – 2 × 7 (v)

o Sulihkan (v) ke dalam (iv): 1 = 7 – 2 × (17 – 2 × 7) = 1 × 7 – 2 × 17 + 4 × 7 = 5 × 7 – 2 × 17

atau –2 × 17 + 5 × 7 = 1

Dari persamaan terakhir ini kita peroleh –2 adalah balikan dari 17 modulo 7.

Û –2 × 17 º 1 (mod 7) (7 habis membagi –2 × 17 – 1 = –35)

5. Tentukan balikan (modulo invers) dari 18 (mod 10).

Jawab :

Karena PBB(18, 10) = 2 ¹ 1, maka balikan dari 18 (mod 10) tidak ada.

6. Tentukan solusi dari 2x º 3 (mod 4).

Jawab :

2x º 3 (mod 4)

Karena 4k genap dan 3 ganjil maka penjumlahannya menghasilkan ganjil, sehingga hasil penjumlahan tersebut jika dibagi dengan 2 tidak menghasilkan bilangan bulat. Dengan kata lain, tidak ada nilai-nilai x yang memenuhi 2x º 3 (mod 5).

7. Tentukan solusi dari 4x º 3 (mod 9).

Jawab :

4x º 3 (mod 9)

Û k = 1 à x = (3 + 1 × 9)/4 = 3

Û k = 5 à x = (3 + 5 × 9)/4 = 12

Û k = –3 à x = (3 – 3 × 9)/4 = –6

Û k = –6 à x = (3 – 6 × 9)/4 = –15

Nilai-nilai x yang memenuhi: 3, 12, … dan –6, –15, …

8. Buktikan bahwa untuk sebarang bilangan asli n, A = 2903ⁿ - 803ⁿ – 464ⁿ + 261ⁿ habis dibagi 1897.

Jawab :

Misalkan n suatu bilangan asli. Perhatikan bahwa 1897 = 7 x 271. Selanjutnya 2903 ≡ 803 (mod7) dan 464 ≡ 261 (mod 7) . Begitu pula 2903 464 ≡ (mod 271) dan 803 ≡ 261 (mod 271), dengan demikian A habis dibagi 7 dan 271. karena GCD(7,271) = 1, maka dapat disimpulkan bahwa A habis dibagi 1897.

9. Carilah semua solusi bilangan bulat yang memenuhi 3456 x+246 y =234.

Jawab :

Menurut persamaan diophantine, persamaan diatas mempunyai penyelesaian bulat jika GCD(3456,246) membagi habis 234.

·         Jadi, langkah pertama yang perlu dilakukan adalah mencari GCD(3456,246). Untuk bilangan-bilangan yang kecil, faktorisasi prima bisa jadi pilihan yang tepat. Akan tetapi, untuk bilangan-bilangan besar, sepertinya perlu dihindari mencari GCD menggunakan faktorisasi prima. Metode yang digunakan disini yaitu dengan menggunakan Algoritma Euclid.
3456=14.246+12
246=20.12+6
12=2.6+0
Darisini diperoleh GCD(3456,246)=6.

· Selanjutnya, cek apakah GCD(3456,246) membagi habis 234. Jelas, karena 234 : 6=39. Jadi, persamaan diatas mempunyai penyelesaian bilangan bulat.

· Langkah berikutnya yaitu, merubah persamaan-persamaan pada Algoritma Euclid. Diperoleh,
12=3456-14.246
6 = 246-20.12.

· Dari kedua persamaan ini diperoleh
6=246-20.(3456-14.246)
= -20.3456 + 28.246.

· Pada persamaan terakhir ini, terlihat penyelesaiannya yaitu dengan mengalikan dengan hasil bagi 234 terhadap 6, yaitu 39.

· Kalikan persamaan terakhir dengan 39 diperoleh 234= -780.3456 +1092.246. Jelas, bahwa ruas kanan sama dengan ruas kiri. Jadi salah satu penyelesaian untuk persamaan diatas adalah latex (x,y)=(-780,1092).

10. Tentukan GCD(4840,1512) ?

Jawab :

Akibat dari teorema algoritma euclide yaitu untuk setiap GCD(a .b) maka terdapat bilangan bulat x dan y sedemikian hingga GCD(a,b ) = ax + by . Misalnya pada contoh diatas, akan dicari x dan y sedemikian hingga 8 = 4840x + 1512y .

GCD(4840,1512) = 8 = 304 – 296

= 304 – (1512 – ( 304 x 4 ))

= ( 304 x 5 ) – 1512

= ( 4840 – ( 1512 x 3 )) x 5 – 1512

= ( 5 x 4840 ) – (15 x 1512 ) – 1512

= ( 5 x 4840 ) – (16 x 1512 )

Jadi x= 5 dan y = -16.

zhu zubaedah

Sabtu, 09 Maret 2013

kongruensi

IAIN Syekh Nurjati Cirebon