BALIKAN MODULO (INVERS)

Balikan Modulo (Invers)
Jika a dan m relatif prima dan m > 1, maka kita dapat menemukan balikan
(invers) dari a modulo m. Balikan dari a modulo m adalah bilangan bulat a
sedemikian sehingga

Bukti:
Dari definisi relatif prima diketahui bahwa GCD (a,m) = 1, dan menurut
persamaan (2) terdapat bilangan bulat p dan q sedemikian sehingga
pa + qm = 1
yang mengimplikasikan bahwa
pa + qm = 1
Karena qm ≡ 0 (mod m) , maka
pa ≡ 1 (mod m)
Kekongruenan yang terakhir ini berarti bahwa p adalah balikan dari a modulo m.
Pembuktian di atas juga menceritakan bahwa untuk mencari balikan dari a
modulo m, kita harus membuat kombinasi lanjar dari a dan m sama dengan 1.
Koefisien a dari kombinasi lanjar tersebut merupakan balikan dari a modulo m.
Contoh :
Tentukan balikan modulo dari 4 (mod 9), dan 17 (mod 7)
1) 4 (mod 9)
o GCD (4, 9) => 9 = 1 . 4 + 5
4 = 1 . 4 + 1
4 = 4 . 1 + 0
GCD = 1
o p . 4 + q . 9 = 1
(-2) . 4 + 1 . 9 = 1
-2 . 4 ≡ 1 (mod 9)
-8 ≡ 1 (mod 9)
o -2 adalah balikan 4 modulo 9
2) 17 (mod 7)
o GCD (17, 7) => 17 = 2 . 7 + 3
7 = 2 . 3 + 1
3 = 3 . 1 + 0
GCD = 1
o p . 17 + q . 7 = 1
(-2) . 17 + 5 . 7 = 1
-2 . 7 1 (mod 7)
-14 1 (mod 7)
o -2 adalah balikan 17 modulo 7

SUMBER : BU WINDIA HADI 

DOSEN : UNIVERSITAS MUHAMMADIYAH PROF DR.HAMKA 

MATAKULIAH : TEORI BILANGAN 

SOAL DAN PEMBAHASAN KONGRUENSI

SOAL DAN PEMBAHASAN KONGRUENSI

SUMBER : BU WINDIA HADI M. Pd
DOSEN : UNIVERSITAS MUHAMMADIYAH PROF DR.HAMKA
MATAKULIAH : TEORI BILANGAN


Itu lah soal soal kongruensi, gampang kan? Jika ada yang belum paham bisa langsung komentar dibawah atau hubungi saya via email.

KONGRUENSI

Kongruensi
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). 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). Contoh :
1) 17 ≡ 2 (mod 3) ( 3 habis membagi 17 – 2 = 15)
2) –7 ≡ 15 (mod 11) (11 habis membagi –7 – 15 = –22)
3) 12 2 (mod 7) (7 tidak habis membagi 12 – 2 = 10 )
4) –7 15 (mod 3) (3 tidak habis membagi –7 – 15 = –22)
 Teorema 4
Misalkan a, b, c, d, x dan y melambangkan bilangan bulat, maka
1) a ≡ b (mod m), b ≡ a (mod m), dan a-b ≡ 0 (mod m) adalah pernyataan
yang setara
2) Jika a ≡ b (mod m) dan b ≡ c (mod m) maka a ≡ c (mod m)
3) Jika a ≡ b (mod m) dan d membagi habis m maka a ≡ b (mod d)
4) Jika a ≡ b (mod m) dan c ≡ d (mod m) maka ax + cy = bx + dy (mod
m)
 Teorema 2
Misalkan m adalah bilangan bulat positif.
1) Jika a ≡ b (mod m) dan c adalah sembarang bilangan bulat maka
(i) (a + c) ≡ (b + c) (mod m)
(ii) ac ≡ bc (mod m)
(iii) ap ≡ bp (mod m) untuk suatu bilangan bulat tak negatif p.
2) Jika a ≡ b (mod m) dan c ≡ d (mod m), maka
(i) (a + c) ≡ (b + d) (mod m)
(ii) ac ≡ bd (mod m)
Contoh :
1) 27 mod 3 = 3 . 9 + 0 = 0
2) 6 mod 8 = 8 . 0 + 6 = 6
3) 0 mod 12 = 12 .1 + 0 = 0
4) -41 mod 9 = 9 . (-5) + 4 = 4
5) 17 mod 3 = 3 . 5 + 2 = 2
6) 10 mod 3 = 3 . 3 + 1 = 1
7) 14 mod 6 = 6 . 2 + 2 = 2
8) 32 mod 3 = 3 . 10 + 3 = 3
17 mod 3 kongruensi dengan 14 mod 6 maka 17 ≡ 32 (mod 3). Misalkan c =
2, maka
i. (a + c) ≡ (b + c)
o 29 mod 3 = 3 . 9 + 2 = 2
o 2 mod 12 = 12 . 0 + 2 = 2
ii. a x c = b x c
o 27 . 2 mod 3 = 54 mod 3 = 3 . 18 + 0 = 0
o 0 . 2 mod 12 = 0 mod 12 = 12 . 1 + 0 = 0
iii. ac ≡ bc
o 27² mod 3 = 729 mod 3 = 3 . 243 + 0 = 0
o 0² mod 12 = 0 mod 12 = 12 . 1 + 0 = 0

*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.
Proposisi 5.2 :
a ≡ b (mod m) jika dan hanya jika a = b + km untuk bilangan bulat k .
Bukti :
a ≡ b (mod m) jika hanya jika a -  b adalah kelipatan dari m. ini berarti a -  b = km untuk bilangan bulat k, atau setara dengan a = b + km.
Proposisi 5. 2
Jika a adalah bilangan bulat dan m adalah bilangan bulat positif. Ketika ada
bilangan bulat unik r dengan 0 < r < m - 1 maka jadi a ≡ r (mod m). Bilangan bulat ini disebut residu paling tidak negatif dari mod m.
Proposisi 5.4 :
Jika a, b, c dan m adalah bilangan bulat dengan m > 0 maka :
a. a ≡ a (mod m)
b. Jika a = b (mod m) maka b = a (mod m)
c. Jika a = b (mod m) dan b = c (mod m), maka a = c (mod m).
Bukti :
a. Karena a = a + 0 x m, proposisi 5.2 mengatakan bahwa a ≡ a (mod m)
b. Jika a ≡ b (mod m), maka a = b + km, untuk berapa k. Untuk itu b = a + (-k)m, jadi b ≡ a (mod m)

SUMBER : BU WINDIA HADI M. Pd

DOSEN : UNIVERSITAS MUHAMMADIYAH PROF DR.HAMKA 

MATAKULIAH : TEORI BILANGAN 

KEKONGRUENAN LANJAR

SOAL DAN PEMBAHASAN PERSAMAAN DIOPHANTINE

1. Tentukan penyelesaian umum persamaan Diophantine 12x + 8y = 40!
*12 = 1×8 + 4
8 = 2×4 + 0
GCD = 4
*4 l 40 = 10
Artinya dapat dicari x dan y
*4 = 1×12 – (1×8) (dikali 10)
40 10×12 – 10×8
Xo = 10 Yo = -10
*Persamaan Diophantine
X = 10 + 2k
Y = - 10 - 3k
2. Tentukan penyelesaian umum persamaan Diophantine 75x + 20y = 300!
*75 = 3×20 + 15
20 = 1×15 + 5
15 = 3×5 + 0
GCD = 5
*5 l 300 = 60
Artinya dapat dicari x dan y
*5 = 20 – (1×15)
5 = 20 – 1 (75 - 3×20)
5 = 20 – 1×75 + 3×20
5 = -1×75 + 4×20 (dikali 30)
Xo = -1 Yo = 4
*Persamaan Diophantine
X = - 1 + 4k
Y = 4 -  15k
3. Tentukan penyelesaian umum persamaan Diophantine 140x + 50y = 200!
*140 = 2×50 + 40
50 = 1×40 + 10
40 = 4×10 + 0
GCD = 10
*10 l 220 = 22
Artinya dapat dicari x dan y
*10 = 50 – (1×40)
10 = 50 – 1 (140 – 2×50)
10 = 50 – 1×140 + 2×50
10 = -1×140 + 3×50 (dikali 22)
220 = -22×140 + 66×50
Xo = -22 Yo = 66
*Persamaan Diophantine
X = - 22 + 5k
Y = 66 - 14k
4. Tentukan penyelesaian umum persamaan Diophantine 12x + 8y = 40!
*12 = 1×8 + 4
8 = 2×4 + 0
GCD = 4
*4 l 40 = 10
Artinya bisa didapat x dan y
*4 = 1×12 – (1×8) (dikali 10)
40 = 10×12 – 10×8
Xo = 10 Yo= -10
*Persamaan Diophantine
X = 10 + 2k
Y = - 10 - 3k
5. Tentukan penyelesaian umum persamaan Diophantine 12x + 5y = 19!
*12 = 2×5 + 2
5 = 2×2 + 1
2 = 2×1 + 0
GCD = 1
*1 l 19 = 19
Artinya dapat dicari x dan y
*1 = 5 – (2×2)
1 = 5 – 2 (12 – 2×5)
1 = 5 – 2×12 + 4×5
1 = -2×12 + 5×5 (dikali 19)
19 = -38×12 + 95×5
Xo = -38 Yo = 95
*Persamaan Diophantine
X = - 38 + 5k
Y = 95 - 12k

SUMBER : BU WINDIA HADI M.Pd
DOSEN : UNIVERSITAS MUHAMMADIYAH PROF DR.HAMKA
MATAKULIAH : TEORI BILANGAN 

PERSAMAAN DIOPHANTINE

Persamaan Diophantine
Diophantus tinggal di Alexandria, Mesir, sekitar 1800 tahun yang lalu.
Bukunya yang berjudul Arithmetica memberikan metode untuk menyelesaikan
berbagai persamaan aljabar dan memiliki pengaruh besar pada pengembangan
teori aljabar dan bilangan selama bertahun-tahun. Bagian dari teori bilangan yang
disebut persamaan Diophantine, dinamakan persamaan Diophantine karena untuk
menghormati dirinya.
Teorema :
Persamaan linear Diophantine ax + by = c mempunyai penyelesaian jika dan hanya jika (a, b) l c. Bukti :
Misalkan (a, b) = d dan d l c
d l c⇔ ada sehingga c = kd
d l (a, b) ⇔ ada m dan n sehingga am + bm = d
 ⇔ a (km) = b (kn) = kd
 ⇔ a (km) + b (kn) = c
Diperoleh x = m k dan y = n k
Teorema 2.1 :
Persamaan Diophantine merupakan suatu persamaan berbentuk ax + by =
c dengan a, b, c merupakan bilangan bulat dan a, b bukan 0 (nol). Dimana k
adalah bilangan bulat dan GCD (a,b) = d. Jika penyelesaian dicari untuk bilangan
bulat. Maka penyelesaiannya adalah

Contoh :
Tentukan penyelesaian umum persamaan Diophantine 738x + 621y = 45 !
o 738 = 1 × 621 + 117
621 = 5 × 117 + 36
117 = 3 × 36 + 9
36 = 4 × 9 + 0
GCD = 9
o 9 l 45 = 5
Artinya dapat dicari x dan y
o Mencari Xo dan Yo
9 = 117 – (3×36)
9 = 117 – 3 (621 – 5×117)
9 = 117 – 3×621 + 15×117
9 = -3×621 + 16×117
9 = -3×621 + 16 (738 – 1×621)
9 = -3×621 + 16×738 – 16×621
9 = 16×738 – 19×621 (dikali 5)
45 = 80×738 – 95×621
Xo = 80 Yo = -95
o Persamaan Diophantine
X = - 80 + 69k
Y = - 95 - 82k

SUMBER : BU WINDIA HADI M.Pd

DOSEN : UNIVERSITAS MUHAMMADIYAH PROF DR.HAMKA

MATAKULIAH : TEORI BILANGAN

SOAL DAN PEMBAHASAN TEORI KETERBAGIAN

SOAL DAN PEMBAHASAN
1. 4 l 16 dan 16 l 32 maka?
*4 l 32 = 8
2. 5 l 30 dan 5 l 40 maka?
*5 l 30+40 = 5 l 70 = 13 (bilangan bulat)
*5 l 30−40 = 5 l −10 = −2 (bilangan bulat)
*5 l 30×40 = 5 l 1200 = 240 (bilangan bulat)
3. 837950419236 apakah habis dibagi oleh 2, 4, 8, 16?
*Dibagi 2 : 2 l 6 = 3 (bilangan bulat)
*Dibagi 4 : 4 l 36 = 9 (bilangan bulat)
*Dibagi 8 : 8 l 236 = 29,.. (desimal)
*Dibagi 16 : 16 l 9236 = 577,... (desimal)
4. Apakah bilangan 926810 habis dibagi oleh 5, 7, 13, 17?
*Dibagi 5 : 926810 = 0 (bilangan bulat)
*Dibagi 7 : 92681 – 0(2) = 92681
9268 – 1(2) = 9266
926 – 6(2) = 914
91 – 4(2) = 83
7 l 83 = 11,... (desimal)
*Dibagi 13 : 92681 – 0(9) = 92681
9268 − 1(9) = 9259
925 – 9(9) = 844
84 – 4(9) = 48
13 l 48 = 3,... (desimal)
*Dibagi 17 : 92681 – 0(5) = 92681
9268 – 1(5) = 9263
926 – 3(5) = 911
91 – 1(5) = 86
17 l 86 = 5,.. (desimal)
*Dibagi 19 : 92681 + 0(2) = 92681
9268(2) = 9270
927 + 0(2) = 927
92 + 7(2) = 106
10 + 6(2) = 22
19 l 22 = 1,... (desimal)
5. Apakah hasil dari 16 4 adalah bilangan bulat?
*16 l 40= 0,25 (desimal ≠ bilangan bulat)
6. 3 l 9 dan 9 l 81 maka?
*3 l 81 = 27 (bilangan bulat)
7. Apakah bilangan 96574362 akan habis jika dibagi dengan 2, 4, 8,
16?
*Dibagi 2 : 2 l 2 = 1 (bilangan bulat)
*Dibagi 4 : 4 l 62 = 15,... (desimal)
*Dibagi 8 : 8 l 362 = 45,...(desimal)
*Dibagi 16 : 16 l 4362 = 272,... (desimal)
8. Apakah bilangan 695 akan habis dibagi 17?
*69 – 5(5) = 44
17 l 44 = 6,.. (desimal)
9. Apakah 8891882748 habis dibagi 19 dan 17?
*Dibagi 19 : 889188274 + 8(2) = 889188290
88918829 + 0(2) = 88918829
8891882 + 9(2) = 8891900
889190 + 0(2) = 889190
88919 + 0(2) = 88919
8891 + 9(2) = 8909
890 + 9(2) = 908
90 + 8(2) = 106
10 + 6(2) = 22
19 l 22 = 1,... (desimal)
*Dibagi 17 : 889188274 – 8(5) = 889188234
88918823 – 4(5) = 88918803
8891880 – 3(5) = 889161
88916 – 1(5) = 8886
888 – 6(5) = 858
85 – 8(5) = 45
17 l 45 = 2,... (desimal)
10. 90000001927 akan habis dibagi 16 atau 19?
*Dibagi 16 : 16 l 1927 = 120,... (desimal)
*Dibagi 19 : 9000000192 + 7(2) = 9000000206
900000020 + 6(2) = 900000032
90000003 + 2(2) = 90000007
9000000 + 7(2) = 9000014
900001 + 4(2) = 900009
90000 + 9(2) = 90018
9001 + 8(2) = 9017
901 + 7(2) = 915
91 + 5(2) = 101
19 l 101 = 5,.. (desimal)

SUMBER : BU WINDIA HADI M.Pd

DOSEN : UNIVERSITAS MUHAMMADIYAH PROF DR.HAMKA

MATAKULIAH : TEORI BILANGAN