Modulo tingkat dasar

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
saran bang DK
saran ane, sblm maen teorema, kuasai dulu cara manual yg menggunakan sifat2 pada modulo.
klo sifat dah dikuasai dengan baik, semua teori penting dlm modulo yaitu teorema fermat, formula euler dan teorema wilson, akan lbh mudah di pahami..
teorema hanya untuk mempermudah aja, dengan catatan kita sudah paham dgn definisi dan sifat2 pada modulo. jadi, klo kita bljr teorema tanpa faham definisi dan sifat2, ya hasilny ga akan maksimal.
ane perhatiin, kbnykn masih bingung dengan apa itu modulo, dan bagaimana sifat2ny.. ^__^

MENENTUKAN JUMLAH KOEFISIEN DARI SUATU POLINOM

Langsung ja masuk contoh..
Ada soal kyk gini:

Tentukan jumlah semua koefisien dr penjabaran polinom
P(x)=(5x^2 -7x + 3)^2011

Buat orang yg pertama ngerjain soal ini mungkin akan menjawab:
GILA JA GUE DISURUH NGITUNG JUMLAH SEMUA KOEFISIEN!!!
BEARTI GUE MESTI NGITUNG SATU-SATU KOEFISIEN DR x^0 , x^1, x^2, ... dst SAMPE x^4022, TERUS DI JUMLAHIN SEMUANY?? NYIKSA GUE NIMAH!!!  ^__^

sepintas memang terlihat susah. Tp mari kita coba selidiki..
Ada temen bilang gini, "klo mau nyari yg ribet2, mulailah dari yg sederhana terlebih dahulu"

ya udah, daripada kita langsung nyelidikin soal yg di atas, ga kebayang seberapa panjangny hasil penjabaran polinom itu. ^__^

anggap ja soalny kita ganti dengan polinom yg sudah terurai misal
P(x)= Ax^5 - Bx^4 + Cx^3 + Dx - E
berapa ya jumlah koefisienny??
Gampang ya bearti jumlahny adalah:
A - B + C + D - E
apa hubunganny ya?

coba bandingkan bentuk:
Ax^5 - Bx^4 + Cx^3 + Dx - E dengan bentuk A - B + C +D - E
bedany yg satu masih ada variabel x , satu lagi ga ada.

Bearti klo kita pengen ngitung jumlah seluruh koefisien, yang mesti kita pikirkan adalah bagaimana cara "MEMBUANG" variabel x dari rumusan polinom.
GIMANA YA CARANYA??!! ^_^ 
INGET, bentuk
Dx maknany adalah D "dikali" x
Nah kita pengen menghilangkan variabel x, dengan kata lain, sama ja kita pengen nyari:
D di kali x = D
nah bearti x=1 alias GANTI AJA NILAIi x dengan angka 1 ^__^

ya dah kita coba ja di soal beneran 
P(x) = 5x^7 - 2x^6 + 4x^5 + 3x^4 - 10x^3 + 7x^2 - 9x + 11 
dr penulusuran kita, cara untuk mencari jumlah semua koefisien adalah dengan mengganti x=1 atau kita cari nilai dr P(1), bearti:
P(1) = 5(1)^7 - 2(1)^6 + 4(1)^5 + 3(1)^4 - 10(1)^3 + 7(1)^2 - 9(1) + 11
P(1) = 5 - 2 + 4 + 3 - 10 + 7 - 9 + 11
"TERNYATA P(1)TAK LAIN ADALAH JUMLAH DR SEMUA KOEFISIEN"
KITA DAH DAPET KESIMPULAN, TINGGAL COBA KE MASALAH YG DI ATAS.

Tentukan jumlah semua koefisien dr penjabaran polinom
P(x)=(5x^2 -7x + 3)^2011

klo dijabarin akani membentuk:
P(x)=ax^4022 + bx^4021 + cx^4020 + . . . 
dengan jumlah koefisien adalah:
a + b + c + . . .  
sama aja dengan contoh yg sederhana td khan?? 
bearti kita tidak perlu menjabarkan, dan untuk menjawabny CUKUP dengan mencari nilai P(1)

Jd jumlah koefisien dr penjabaran P(x)=(5x^2 -7x + 3)^2011adalah:
P(1) = (5 - 7 + 3)^2011 = (1)^2011 = 1
GAMPANG KHAN?? ^__^

Bila dalam penulisan ini terdapat kekurangan atau kesalahan, saya pribadi minta maaf, karena ini hanya buah pemikiran dr seseorang yg sedang belajar matematika. 
Semoga sedikit ilmu dan pengetahuan ini bisa bermanfaat untuk anggota soulmate

BERSAMBUNG

SYUKRON..