Air pada
fasa padat jauh lebih ringan daripada air pada fasa cair. Karena itu es
mengambang. Ini penting untuk kehidupan di danau air tawar, karena es
berperan sebagai penyekat terhadap pelepasan energi panas sehingga
pembekuan air dari permukaan hingga ke dasar tidak terjadi.
Titik
beku berkurang di bawah tekanan, sehingga pen-cairan terjadi di dasar
glacier yang memudahkan terjadinya aliran glacier.
Rantai H
putus di bawah tekanan, sehingga es di bawah tekanan akan menjadi plastis,
sehingga daratan es di Antartika dan Artik mengalir melepaskan gunung es
di atasnya. Tanpa proses ini, maka semua air akan menjadi es di daerah
kutub.
10 Tips meningkatkan kreatifitas Anak (10 cara melatih, mengasah
anak berpikir kreatif, 10 metode menstimulasi kreatifitas anak usia
dini) By Kak Zepe
doctordisruption.com
Sering kita menemukan seorang anak yang terlihat malas di kelas atau
memiliki nilai sekolah yang tidak terlalu baik. Namun ada kalanya
mereka bisa mendapatkan nilai yang melebihi teman-teman mereka satu
kelas, atau memiliki sesuatu kemampuan yang tidak kita duga dan
tidak bisa dilakukan oleh anak-anak yang lain. Jadi bila anda
menemukan seorang anak atau bahkan mungkin buah hati kita sendiri
terlihat “kurang pandai” jangan berkecil hati. Mungkin saja dia
adalah anak yang kreatif dan cerdas, namun belum terlatih /
terasah dengan baik. Saya percaya, semua anak memiliki bakat untuk
menjadi anak yang cerdas dan kreatif. Lalu bagaimana untuk bisa
melatih anak agar bisa menjadi anak yang cerdas dan kreatif? Mari
kita ikuti tips-tips di bawah ini:
Ada 10 cara mengasah kreativitas anak, yaitu:
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 = rsedemikian 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.1Kongruen
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 = k1.m
b ≡ c (mod m) → b-c = k2.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 = k1.m
c ≡ d (mod m) maka c-d = k2.m+
(a-b) +
(c-d) = (k1+k2) m
(a+c) –
(b+d) = k .m
Jadi (a+c) ≡ (b+d) (mod
m)
c.jika
(a+c) ≡ (b+c) (mod m), makaa ≡ 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 an ≡ bn (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 220 dibagi 7 sisanya 4
Jawab
:
8
– 1 = kel. 7
8
≡ 1( mod 7)
23
≡ 1( mod 7)
(23)6
≡ (1)6( mod 7)
218
≡ 1( mod 7)
218.22
≡ 1.22( mod 7)
2.20
≡ 4( mod 7) atau 2.20 -
4= kel. 7 + 4
Jadi
2.20 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).
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
ax2
+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)
x2 + x - 12≡ 0 (mod 111)
4x2 + 4x - 48≡(mod
111)
4x2 + 4x + 1≡49
(mod 111)
(
2x + 1 )2 ≡ 49 (mod 111)
Misalkan
y ≡ 2x +1 (mod 111)
y2 ≡ 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+3Jadi,bilangan
I = k.111 + 107
bilangan
II = k.1111+4bilangan
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 persamaan56x + 72y = 40 mempunyai jawaban untuk himpunan bilangan bulat?
Sekarang
kita akan mencari nilai-nilai yang mungkin dalam himpunan bilangan bulat.
oKita sederhanakan persamaan yang
kita punya dengan cara membaginya dengan 8.
Diperoleh : 7x + 9y = 5
oPersamaan yang diberikan adalah7x + 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
oLangkah 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
oSekarang 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 .
oUntuk 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)
oPersamaan 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.
oSelanjutnya 7 ( x –
p ) = 9 . 7k maka(x – p) = 9k, dengan k bilangan bulat.
oSehingga 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
seorangmatematikawan Perancis pada
tahun 1640.
Teorema 4 (Teorema Fermat). Jika p
adalah bilangan prima dan a adalah bilangan bulatyang tidak habis dibagi dengan p,yaitu PBB(a, p) = 1, maka
ap–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,
217–1
= 65536 º 1 (mod 17)
karena 17 tidak membagi 65536 – 1 =
65535(6553517 = 3855).
Untuk 21,
221–1
=1048576 º\ 1 (mod 21)
karena 21 tidak habis membagi 1048576
– 1 = 1048575.
·Kelemahan
Teorema Fermat: terdapat bilangan komposit n sedemikian sehingga 2n–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,
2340º 1 (mod 341)
Untunglah
bilangan prima semu relatif jarang terdapat.
Contoh
Periksalah bahwa (i) 316º 1 (mod
17) dan (ii) 186º 1 (mod 49).
Penyelesaian:
(i)Dengan mengetahui bahwa kongruen 33º 10 (mod 17), kuadratkan kongruen tersebut
menghasilkan
36º 100 º –2(mod 17)
Kuadratkan lagi untuk menghasilkan
312º 4 (mod
17)
Dengan demikian, 316º 312× 33× 3 º 4 × 10 × 3 º 120 º 1 (mod
17)
(ii)Caranya sama seperti penyelesaian (i) di
atas:
182º 324 º 30 (mod
49)
184º 900 º 18 (mod
49)
186º 184× 182º 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) = 0f(6) = 2
f(2) = 1f(7) = 6
f(3) = 2f(8) = 4
f(4) = 2f(9) = 6
f(5) = 4f(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.
Untuk
sebarang bilangan bulat dan bilangan prima yang coprime
ke berlaku
Sekarang
bagaimana jika modulusnya tidak prima, composite, apakah teorema kecil fermat
masih berlaku? Tidak, sebagai contohnya jika kita ambil dan ,
apakah Tidak karena 15 tidak membagi .
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
adalah banyaknya bilangan pada yang coprime ke
Contoh: karena ada 4 bilangann asli yang kurang dari 8 yang coprime
ke 8 ke-4 bilangan tersebut adalah 1,3,5,7. kerna
semua bilangan pada coprime
ke 11.
Teorema
Jika prima maka
Jika prima dan maka
Bukti
1.
Jika prima maka semu bilangan
pada coprime
ke , itu artinya
2. Ada elemen pada himpunan .
Elemen pada himpunan tersebut tidak coprime ke jika hanya jika dapat dibagi
oleh . Elemen pada himpunan yang
dapat dibagi oleh adalah
Ada
sebanyak elemen yang tidak
coprime ke maka banyaknya elemen yang
coprime ke sebanyak
Definisi:Sistem residu tereduksi mod (reduced residue system
mod ) adalah himpunan
bilangan-bilangan
Yang
memenuhi
Jika maka
Untuk
setiap coprime ke
Dengan
demikian Sistem residu tereduksi mod merepresentasikan
bilangan-bilangan yang coprime ke
Contoh: dan keduanya
merupakan sistem residu tereduksi mod
Lemma:
Diberikan dan adalah
Sistem residu tereduksi mod , berlaku:
Untuk
semua bilangan bulat maka merupakan
sistem residu tereduksi mod .
Jika coprime ke maka merupakan
sistem residu tereduksi mod .
Akibat: Diberikan
dan adalah
Sistem residu tereduksi mod , jika coprime ke dan sebarang bilangan bulat maka
merupakan
sistem residu tereduksi mod .
Contoh: merupakan sistem residu tereduksi
mod . tmabahkan pada setiap
bilangan diperoleh ,
sistem residu tereduksi mod lainnya, Kita tahu 6 coprime
ke 25, jika kita kalikan sistem yang awal dengan 25 diperoleh istem
residu tereduksi mod lainnya, terakhir juga
merupakan sistem residu tereduksi mod .
Teorema Euler
Setiap
bilangan bulat dan bilangan bulat positif yang coprime ke maka :
Perhatikan
jika prima maka ,
teorema euler berubah menjadi teorema kecil fermat. Dengan demikian kita bisa
menganggap teorema euler sebagai generalisasi teorema kecil fermat.
Bukti: Ambil
dan adalah
Sistem residu tereduksi mod , diasumsikan termuat di .
Karena
dan coprime maka juga
merupakans sistem residu tereduksi mod , Kedua sistem tersebut
haruslah mempunyai hasil perkalian modulus yang sama
Karean
setiap coprime ke , jika dikalikan kedua sisi
dengan diperoleh
atau dengan kata lain
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 x2 + y2 + z2
= 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 :
a2 + b2 + c2 = 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
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 xyang memenuhi 2xº 3 (mod 5).
7.Tentukan solusi dari4xº 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 = 2903n-803n– 464n + 261n habis dibagi 1897.
Jawab :
Misalkan n suatu bilangan asli.
Perhatikan bahwa 1897 = 7 x 271. Selanjutnya2903 ≡ 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.
·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 .