Modulo (1)

Assalamu'alaikum wr wb
berhubung di semester 3 ini ada MK Teori Bilangan, dan salah satu materinya ada masalah modulo
maka saya mau berbagi sedikit tentang Modulo

nama lain dari modulo itu sisa pembagian

Misalnya,

11 dibagi 4
hasilnya 2 sisanya 3

dlm penulisan modulo

11 mod 4 = 3

Atau

Kongruensi

11 Ξ 3 (mod 4)

Ξ Itu simbol kongruen. Sama dg tp ada 3

Klo sama dg kn artinya sama.. Ruas kanan sama dg ruas kiri..

Klo kngruensi pada modulo itu simbol..
Jadi

10 Ξ 2 (mod 4)

Itu artinya
4 hbs membagi 10-2

definisi modulo
a=b mod c <--> c l (a-b) "c membagi a-b" <--> a-b = kc atau
a= kc + b.
bahasa lebih sederhanany
a di bagi c sisany b
a=b mod c dibaca "a kongruen b modulo c"

Note:
lambang sbnrny bukan "=" sama dengan, tp yg strip tiga yg dr mas sihab dibacany kongruen

kita akan sering menggunakan
a Ξ b (mod c)

sifat pada modulo
1. Utk penjumlahan...

a+k Ξ b+k (mod c)

Jd pd modulo, kita boleh menambahkan k sprti tsb
2. Utk pengurangan

a-k Ξ b-k (mod c)
‎3. Utk perkalian

ak Ξ bk (mod c)
4. untuk pembagiana/kΞb/k mod(c/gcd(k,c))
atau
Utk pembagian perlu hati2..

Misalkan m adlh fpb dari k dan c

a Ξ b (mod c)

maka

a/k Ξ b/k (mod c/m)

Berapakah sisa dari
5.5.5.5.5 dibagi 11

itu 5^5

Gunakan sifat

a^(p-1) ≡ 1(mod p)disini diingat untuk p prima berlaku rumus tersebut

5^10 = 1 mod 11
(5^5)^2 = 1 mod 11

maka..
(5^5) mod 11= (1 mod 11)^2

(5^5) mod 11
=(25 x 25 x 5) mod 11
=[(25 mod 11)(25 mod 11)(5 mod 11)] mod 11
=(3x3x5) mod 11
=45 mod 11
=(4x11 + 1) mod 11
=1 mod 11
=1

5 Ξ 5(mod 11)

gunakan sifat perkalian

5.5 Ξ 5.5(mod 11)
5.5 Ξ 25(mod 11)
5.5 Ξ 3(mod 11)
5.5.5 Ξ 3.5(mod 11)
5.5.5 Ξ 15(mod 11)
5.5.5 Ξ 4(mod 11)
5.5.5.5 Ξ 4.5(mod 11)
5.5.5.5 Ξ 20(mod 11)
5.5.5.5 Ξ 9(mod 11)
5.5.5.5.5 Ξ 9.5(mod 11)
5.5.5.5.5 Ξ 45(mod 11)
5.5.5.5.5 Ξ 1(mod 11)

Jd, sisanya 1


berapakah sisa dari
5! dibagi oleh 7

5 Ξ 5 (mod 7)
5.4 Ξ 5.4 (mod 7)
5.4 Ξ 20 (mod 7)
5.4 Ξ 6 (mod 7)
5.4.3 Ξ 6.3 (mod 7)
5.4.3 Ξ 18 (mod 7)
5.4.3 Ξ 4 (mod 7)
5.4.3.2 Ξ 4.2 (mod 7)
5.4.3.2 Ξ 8 (mod 7)
5.4.3.2 Ξ 1 (mod 7)
5.4.3.2.1 Ξ 1 (mod 7)

Jd, sisanya 1

berapakah sisa
(2^8) - 1 dibagi 5

2 Ξ 2(mod 5)

2.2 Ξ 2.2(mod 5)
2.2 Ξ 4(mod 5)
Atau
2^2 Ξ 4(mod 5)

2^2.2^2 Ξ 4.4(mod 5)
2^2.2^2 Ξ 16(mod 5)
2^2.2^2 Ξ 1(mod 5)
2^4 Ξ 1(mod 5)

2^4.2^4 Ξ 1.1(mod 5)

2^8 Ξ 1(mod 5)

Gunakan sifat pengurangan

2^8 - 1 Ξ 1 - 1(mod 5)
2^8 - 1 Ξ 0(mod 5)

Jd, sisanya 0
Berapa sisa 4 x 6 di bagi 5
‎4.6 mod 5 Ξ (5-1)(5+1) mod 5 Ξ 5^2 - 1 mod 5
Ξ -1 mod 5
Ξ 5 - 1 mod 5
Ξ 4 mod 5
jadi sisanya 4

berapakah sisa
(2^17)+(17^2) dibagi 9

‎{(2^17)+(17^2)} mod 9

2^4 mod 9 = 16 mod 9 = 7 mod 9
(2^4 x 2^4) mod 9 = (7x7) mod 9 = 49 mod 9 = 4 mod 9
(2^8 x 2^8) mod 9 = (4x4) mod 9 = 16 mod 9 = 7 mod 9
2^17 mod 9 = (2^16 x 2) mod 9 = (7x2) mod 9 = 14 mod 9 = 5 mod 9

17^2 mod 9 = (17 mod 9 x 17 mod 9) mod 9 = (8x8) mod 9 = 64 mod 9 = 1 mod 9

{(2^17)+(17^2)} mod 9 = 5 mod 9 + 1 mod 9 = 6 mod 9 = 6
cara 2
2.2^16 + 289 mod 9
2.256^2 + 289 mod 9
2.(252+4)^2 + 289 mod 9
32+289 mod 9
321 mod 9
6 mod 9
6

kita ke bilangan yg besar
Berapa sisa
7^77 dibagi 12

‎7.7^76 mod 12
7.49^38 mod 12
7.(48+1)^38 mod 12
7.1^38 mod 12
7 mod 12
=7

Misal kita ambil bilangan:

(32+13)^2 dibagi 8
ini artinya=
32x32 + 32x13 +32x13 + 13x13.

nah 32 merupakan faktor dari 8
jadi Jika ada perkalian yang merupakan faktor 8, Jika dikali berapapaun lalu di bagi 8 pasti tidak ada sisanya..

jadi dari faktor (32+12)^2 yang buukan faktor 8 hanya 13x13

jadi (32+13)^2 mod 8=
13^2 mod 8
169 mod 8
1 mod 8
=1
brpakah sisa 3^2002 dbagi 100 !
‎3^5 = 243

3^5 Ξ 243(mod 100)
3^5 Ξ 43(mod 100)

3^5.3^5 Ξ 43.43(mod 100)
3^5.3^5 Ξ 1849(mod 100)
3^10 Ξ 49(mod 100)

3^10.3^10 Ξ 49.49(mod 100)
3^10.3^10 Ξ 2401(mod 100)
3^20 Ξ 1(mod 100)
(3^20)^100.3^2 Ξ 1^100.3^2(mod 100)
3^2002 Ξ 9(mod 100)

Jd jwbnnya 9
Berapakah sisa dari (3^2011) - 1 dibagi 61
3^2 kong 9 mod 61
3^4 kong 20 mod 61
3^8 = (3^4)^2 =400 kong 34 mod 61
3^10= (3^8)(3^2)=34x9=306 kong 1 mod 61
(3^10)^100=3^1000 kong 1 mod 61
(3^1000)(3^1000)(3^10)(3)=
3^2011 kong (1x1x1x3=3) mod 61
3-1=2
cara 2
3^2 Ξ 9(mod 61)

3^4 Ξ 81(mod 61)
3^4 Ξ 20(mod 61)

3^4.3^4 Ξ 20.20(mod 61)
3^4.3^4 Ξ 400(mod 61)
3^8 Ξ 34(mod 61)

3^2.3^8 Ξ 9.34(mod 61)
3^10 Ξ 306(mod 61)
3^10 Ξ 1(mod 61)

[(3^10)^100].3^11 Ξ 1^100.3^10.3^1 (mod 61)
3^2011 Ξ 1.3(mod 61)
3^2011 Ξ 3(mod 61)

(3^2011) - 1 Ξ 3 - 1(mod 61)
(3^2011) - 1 Ξ 2(mod 61)

jd sisanya 2..

kita kan tahu bhwa
10 Ξ 2 (mod 4)

Jika dibagi 2
Fpb dr 2 dn 4 adlh {2}

10/2 Ξ 2/2(mod 4/{2})

5 Ξ 1(mod 2)

{2} hy utk mmbdakan dg 2.
2 yg ada krungnya itu dr fpb dr pmbagi dan mod


kita td udh ngitung,
3^2002 Ξ 9(mod 100)

berapakah sisa dari

3^2001 dibagi 100

3^2002 Ξ 9(mod 100)
Fpb dr 100 dan 3 adlh 1.

3^2002/3 Ξ 9/3 (mod 100/1)

3^2001 Ξ 3(mod 100)

jd sisanya 3
berapakah sisa 2^70 + 3^70 dibagi 13kan sesuai teorema a^n+b^n habis dibagi a+b jadi (2^2)^35 +(3^2)^35 habis dibagi 2^2+3^2=13oha ya a^n+b^n habis dibagi a+b berlaku untuk n bilbul ganjilberapakah sisa pembagian dari 47^99 oleh 100
47^2 Ξ 9 mod 100
47^4 Ξ (9x9=81) mod 100
47^5 Ξ (81x47=3807) --> 7 mod 100
(47^5)^19 = 47^95
stiap klipatan 4 maka bnyk sisa akan kmbli k awal. jd 47^95 = 43 sisa'a, yaitu (7^3 mod 100)
47^99=47^95 x 47^4 = (43x81=3483) mod 100
maka 83

47^99 mod 100

47^2 Ξ 9 mod 100
47^3 Ξ 23 mod 100
(47^3)^3 Ξ 67 mod 100
47^9 Ξ 67 mod 100
47^10 Ξ 49 mod 100

47^11 Ξ 3 mod 100
(47^11)^3 Ξ 27 mod 100
47^33 Ξ 27 mod 100
(47^33)^3 Ξ 83 mod 100
47^99 Ξ 83 mod 100

sisa 83



47^99 mod 100
euler 100= 100(4/5)(1/2)=40
(47^(40.2)).47^19 mod 100
=1.47^19 mod 100
=(47^2)^9 . 47 mod 100
=(2209)^9 . 47 mod100
=9^9 . 47 mod 100
=729^3 . 47 mod 100
=29.29.29.47 mod 100
=41.63 mod 100
=83 mod 100
EULER
Jika a^m mod b, dengan a dan b relatif prima, maka a^(euler b) mod b=1
euler b= b(1-(1/p))(1-(1/p))..
Dengan p=faktor prima dari b
euler 100=100(1-1/5)(1-1/2)=100(
4/5)(1/2)=40
contoh lain, euler 12=12(1/2)(1/3)=2
nah soal yg td, 47 dan 100 kan prima, maka 47^euler100 mod 100=1


coba kerjain soal
37^134 mod 50
euler 50 = (1-1/2)(1-1/5) = 50 (1/2)(4/5) = 20
37^(20.5) . 37^23 mod 50
1.37^23 mod 50
37^20 . 37^3 mod 50
1.37^3 mod 50
37^2 . 37 mod 50
19 . 37 mod 50
703 mod 50
3 mod 50

cari euler dari:
50, 82, 105, 374
euler 50 = (1-1/2)(1-1/5) = 50 (1/2)(4/5) = 20euler 82 = 82(1-1/2)(1-1/41) = 82(1/2)(40/41) = 40
euler 105 = 105 (1-1/3)(1-1/5) = 105(2/3)(4/5) = 56
euler 374 = 374(1-1/2)(1-1/187) = 374 (1/2)(186/187) = 186


13^147 mod 82

euler 82 = 40
13^(40.3+27) mod 82
=13^27 mod 82
=(13^2)^13 . 13 mod 27
=5^13. 13 mod27
=(5^3)^4. 5. 13 mod 82
=(43^2)^2. 5. 13 mod 82
=45.5.45.13 mod 82
=61.11 mod 82
=15 mod 82TEOREMA FERMAT KECIL
Jika p adlh bil prima dan p tdk mmbagi a, maka
a^(p-1) ≡ 1(mod p)
yang berhubungan dengan modulo yaitu a^(euler dari p) ≡1 (mod p)eluler udah dijelaskan diatas tadi

berapakah sisa dr 5^38 jika dibagi 11

Manfaatkan
5^10 Ξ 1(mod 11)

5^38 = 5^(10.3 + 8) = (5^10)^3.(25 mod 11)⁴ mod 11 = (11.2 + 3)⁴ mod 11 = 3⁴ mod 1181 mod 11 = 4 mod 11

Jadi sisanya 4

Sumber:
David M Burton - Elementary Number Theory

bandingkan cra biasa
5^38 jika dibagi 11
5^2(19) mod11
25^19 mod11
(2.11+3)^19 mod 11
3^19 mod11
[3^3(6) x 3 ]mod11
[27^6 mod 11 x 3 mod11]mod11
[(11.2 +5)^mod11 x 3 mod11] mod11
[5^6mod11 x 3mod11] mod11
[25^3mod11 x 3 mod11]mod 11
[(2.11+3)^3 mod11 x 3 mod11] mod11
3^3 mod11 x 3 mod11]mod11
27mod11 x 3 mod11]mod11
5mod11 x 3 mod 11]mod11
5 x 3] mod 11
15 mod11
4mod 11
disingkat jadi
5^38
= 5^(10.3 + 8)
= (5^10)^3 . (5^8)
= (5^10)^3 . (5^2)^4
= (5^10)^3 . (25)^4
= 1^3 . 3^4
= 81

81 = 4 mod 11

berapa sisa dari 5^11 dibagi 11
cara fermat5^11 mod 11
=[5^(10+1)] mod 11
=(5^10 x 5) mod 11
=(1 x 5) mod 11
=5 mod 11
=5
cara biasa

5=5 mod 11
5^2 = 25 mod 11 = 3 mod 11
5^4 = 3^2 mod 11 = 9 mod 11
5^8 = 9^2 mod 11 = 81 mod 11 = 4 mod 11
5^16 = 4^2 mod 11 = 16 mod 11 = 5 mod 11
5^32 = 5^2 mod 11 = 25 mod 11 = 3 mod 11
5^38 = 5^32 .5^4 .5^2 mod 11=3.9.3 mod 11=81 mod 11=4 mod 11

penjelasan rinci dari bang DK
‎5^38 mod 11
karena 11 bilangan prima, sesuai teorema fermat, berlaku:
5^(11-1)=1 mod 11
5^10 = 1 mod 11
38=10.3 + 8
sehingga
5^38 = (5^10)^3 . 5^8 = 1^3. 5^8 mod 11
5^38 = 5^8 mod 11
bearti masalah sudah jd lbh sdrhn, tinggal nyari 5^8 mod 11
dan selanjutny tinggal pake cara manual
5=5 mod 11
5^2 = 25 mod 11 = 3 mod 11
5^4 = 3^2 mod 11 = 9 mod 11
5^8 = 9^2 mod 11 = 81 mod 11 = 4 mod 11
kesimpulan: 5^38 = 5^8 = 4 mod 11
sehinga sisa pembagian 5^38 di bagi 11 adalah 4