TEORI BILANGAN

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
Fungsi Euler Φ
Fungsi Euler Φ medefinisikan Φ(n) untuk n ≥ 1 yang
menyatakan jumlah bilangan bulat positif < n yang relatif prima dengan n. Contoh 18 Tentukan Φ(20). Penyelesaian: Bilangan bulat positif yang lebih kecil dari 20 adalah 1 sampai 19. Di antara bilangan-bilangan tersebut, terdapat Φ(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 Φ(1) = 0 Φ(6) = 2 Φ(2) = 1 Φ(7) = 6 Φ(3) = 2 Φ(8) = 4 Φ(4) = 2 Φ(9) = 6 Φ(5) = 4 Φ(10) = 4 Jika n prima, maka setiap bilangan bulat yang lebih kecil dari n relatif prima terhadap n. Dengan kata lain, Φ(n) = n – 1 hanya jika n prima. 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 82 TEOREMA 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.. ^__^ contoh penyelesaian kongruensi tentukan solusi kongruensi berikut 8k≡15 (mod 25) cara 1.subtitusi langsung 8k = 15 mod 25 8k = 40 mod 25 k = 5 mod 25 atau k=25n + 5, untuk n bilgan bulat. cara 2.diophantine 8k = 15 mod 25 8k = 25c +15 8k-25c = 15 25=3.8+1 1=25-3.8 1=8.(-3)+25(1) 15=8.(-45)+25(15) 15=8.(-45)-25(-15) k0=-45,c0=-15 k=-45+25t c=-15+8t untuk t=2 k=5,c=1 8k = 25c +15 8k= 25c+15 mod 25 8k= 25+15 mod 25 k=5 mod 25 atau k=25n + 5, untuk n bilgan bulat cara 3.invers modulo 8k = 15 mod 25 euler 25=20 2^17 .2^3 k = 2^17 . 15 (mod 25) k = (2^5)^3 .4.15 (mod 25) k=(7^2).7.10 (mod 25) k=-1.-5 (mod 25) k=5 mod 25) cara 4. cari identitas bezoutnya kita cukup mengetahui identitas Bezout-nya, yaitu 1=8.(-3)+25(1) Dapat kita katakan bahwa "-3 adalah invers dari 8 modulo 25". Kita juga dapat mengatakan bahwa "8 adalah invers dari -3 modulo 25". 8k = 15 mod 25 k = -3.15 mod 25 k = 5 mod 25 atau k=25n + 5, untuk n bilgan bulat contoh penyelesaian chinese remainder theorem atau biasa disebut crt 8.suatu bilangan jika dibagi 3 sisanya 1, jk dibagi 7 sisanya 5, dan jk dibagi 16 sisanya 11. Brapakah nilai bilangan tsb? pke cara biasa.. x=1 mod3 --> x=3a+1
x=5 mod7
x=11 mod 16 --> x= 16b + 11
...
x=5 mod7
3a+1=5 mod7
3a=4 mod 7
3a=18 mod7
a=6 mod 7
a=7c + 6 --> x=3(7c+6) +1 --> x=21c+19 -->x=19 mod21

16b +11 = 19 mod 21
16b= 8 mod21
16b= 176 mod21
b=11 mod 21 --> b=21d+11
jd:
x= 16b + 11
x= 16(21d +11) + 11
x=336d +187, untuk d sembarang bil bulat
atau
x= 187 mod336

chek
187:3 sisa 1
187:7 sisa 5
187:11 sisa 11
CARA CHINESE REMAINDER THEOREMA

langkah pertama syarat crtnya adlah modnya saling prima atau koprima
lalu
x=(1) mod 3
x=5 mod (7)
x=11 mod (16)
pandang persamaan pertama ,lalu yang dikurung dikalikan semua dan kalikan dengan a jd
k=(1.7.16.a)
k=112a

p=7.16
untuk menyelesaikan nilai a haruslah meyelesaikan persamaan kongruensi brikut p.a = 1 (mod 3) jd
7.16a = 1 mod 3
a=1 mod 3
1 adalah solusi terkecilnya jadi a=1

langkah ke 2

x=1 mod (3)
x=(5) mod 7
x=11 mod (16)

pandang persmaan kedua ,lalu yg dikurung kalikan semua dan kalikan dengan b jd
l=(3.5.16.b)
l=240b

q=3.16
untuk menyelesaikan nilai b haruslah meyelesaikan persamaan kongruensi brikut q.b = 1 (mod 7) jd
3.16b = 1 mod 7
3.2b=1 mod 7
6b=1 mod 7

untuk menyelesaikan ada 4 cra dari saya,brikut penjelasanya!!

cara 1.subtitusi langsung

6b = 1 mod 7
6b = 35+1 mod 7
6b = 36 mod 7
b = 6 mod 7

atau b=7n + 6, untuk n bilngan bulat.

cara 2.diophantine

6b = 1 mod 7
6b = 1+7s
6b-7s=1

7=1.6+1
1=7-1.6
1=6.(-1)+7.(1)
1=6.(-1)-7.(-1)

b0=-1,s0=-1
b=-1+7t
s=-1+6t
untuk t=1
b=6,s=5

6b = 1+7s
6b = (1+7.5) mod 7
6b = 36 mod 7
b = 6 mod 7
atau b=7n + 6, untuk n bilngan bulat.

cara 3.invers modulo

6b = 1 mod 7
euler 7=6
kalikan 6^5 kedua ruas

6^5.6b = 6^5 mod 7
6^6.b = (-1)^5 mod 7
b = -1 mod 7
b= 6 mod 7
atau b=7n + 6, untuk n bilngan bulat.

cara 4. cari identitas bezoutnya

kita cukup mengetahui identitas Bezout-nya, yaitu

1=6.(-1)+7.(1)
Dapat kita katakan bahwa "-1 adalah invers dari 6 modulo 7".
Kita juga dapat mengatakan bahwa "6 adalah invers dari -1 modulo 7".

6b = 1 mod 7
-1.6b = -1.1 mod 7
b = -1 mod 7
b = 6 mod 7
atau b=7n + 6, untuk n bilngan bulat.

karena nilai b terkecil adalah 6 maka b=6

langkah ke 3

x=1 mod (3)
x=5 mod (7)
x=(11) mod 16

pandang persmaan ketiga ,lalu yg dikurung kalikan semua dan kalikan dengan c jd
m=(3.7.11.c)
m=231c

r=3.7
untuk menyelesaikan nilai c haruslah meyelesaikan persamaan kongruensi brikut r.c = 1 (mod 16) jd
3.7c = 1 mod 16
21c = 1 mod 16
5c = 1 mod 16
-3.5c = -3 mod 16
c = 13 mod 16
atau c=16n + 13, untuk n bilngan bulat.

karena nilai c terkecil adalah 13 maka b=13

hasil kongruensinya akan jadi sperti ini
x=(k+l+m) (mod 3.7.16)
x=(112a+240b+231c) (mod 336)
x=(112.1+240.6+231.13) (mod 336)
x=(112+1440+3003) (mod 336)
x=4555 (mod 336)
x=(13.336+187) (mod 336)
x=187 (mod 336)

kali ini di modulo jilid 2 kita membahas tentang teori wilson dan pangkat yang dipangkatkan dalam modulo
pertama tama kita membahas tentang teori wilson

Teori Wilson

rumus:
rumus umunya yaitu

1. (p-1)! Ξ -1 (mod p) atau (p-1)! Ξ (p-1) (mod p)
untuk p adalah bil prima
pembuktiannya ada di http://asimtot.wordpress.com/2010/06/01/teorema-wilson/ dan http://hendrydext.blogspot.com/2009/08/teorema-wilson.html


lalu kita kembangkan
(p-1)! Ξ (p-1) (mod p)
(p-1).(p-2)! Ξ (p-1) (mod p)
(p-2)! Ξ 1 (mod p)
jadi rumus ke 2

2.(p-2)! Ξ 1 (mod p)
kembangkan lagi jadi rumus ke tiga yaitu

3. (p-3)! Ξ (p-1)/2 (mod p) disini untuk p prima >2
setelah dikembangkan lagi saya menemukan rumus baru yaitu

4. (p-4)! Ξ +- (p+1)/6 (mod p)ada dua kemungkinan + dan -
kita lihat dari p nya
jika p=6k+1 maka (p-4)! Ξ -(p-1)/6 (mod p)
jika p=6k-1 maka (p-4)! Ξ (p+1)/6 (mod p)
berlaku untuk p prima dan >3

untuk yang (p-5)! sudah tinggal memakai invers modulo peyelesaian dengan menggunakan persamaan diophantine seperti yang akan dijelaskan dibawah ini!

dan banyak pengembangan lain yang bisa diperoleh seperti
5. a^p +a(p-1)! Ξ a^(p-1) -1 = 0 (mod p)
untuk pembuktian bisa request!


soal 1.
Berapakah sisanya
16! dibagi 17
‎

(17-1)! Ξ -1 (mod 17)
16! Ξ -1 (mod 17)
16! Ξ ((-1)17 + 16) (mod 17)
16! Ξ 16 (mod 17)

jadi sisanya 16

soal 2.
Tentukan sisa dari
21! dibagi 23

21! mod 23 Ξ (23-2)! mod 23
21! mod 23 Ξ 1 mod 23
jd sisanya 1

soal 3.
berapakah sisa dari
131! dibagi 131

131! mod 131 Ξ 0 mod 131

jd 131! habis dibagi 131 (sisa = 0)

soal 4.
Berapakah sisa dari
2(26!) dibagi 29

pake rumus ke 3
26! Ξ (29-1)/2 mod 29
26! Ξ 14 mod 29
2.26! Ξ 2.14 mod 29
2.26! Ξ 28 mod 29

atau
(p-2)!Ξ1 (mod p)
27! Ξ 1 (mod 29)
27.26! Ξ 1 (mod 29)
27.26!Ξ29k+1 (mod 29)
k=13
26! Ξ 14 (mod 29)
2.26! Ξ 28 (mod 29)


soal 5.
gunakan rumus ke 5 yang diatas
7^2011 +7(2010)! mod2011
sisanya 0

atau
7^2011 +7(2010)! mod2011
7^2010 .7 +7(-1) (mod 2011)
7-7 (mod 2011)
0 (mod 2011)

soal 6.
9!.(7!^11) +9!(10!) mod 11

(1).(7!^10).7! +1(-1) (mod 11)
7! -1 (mod 11)

8! Ξ (11-1)/2 (mod 11)
8.7! Ξ 5 (mod 11)
2^7.8.7!Ξ2^7.5 (mod 11)
7! Ξ 2^4 .2^3 .5 (mod 11)
7! Ξ 5 .8 .5 (mod 11)
7! Ξ 2 (mod 11)

7! -1 (mod 11)
2-1 (mod 11)
1 (mod 11)

soal 7.
7.(2008!) (mod 2011)

7.(2011-1)/2 (mod 2011)
7.1005 (mod 2011)
7035 mod 2011
1002 mod 2011

atau
7(2008!) mod 2011?
2009! Ξ 1 mod 2011
2009.2008! Ξ 2011e+1 mod 2011
e=1004
2008! Ξ 1005 mod 2011
7.2008! Ξ 7.1005 mod 2011
7.2008! Ξ 7035 mod 2011
7.2008! Ξ 1002 mod 2011

soal 8.
18!^17!^16! mod 19

hint :
prhtkn ini
(18!)^1 Ξ -1 (mod 19)
(18!)^2 Ξ 1 (mod 19)
(18!)^3 Ξ -1 (mod 19)

Bdakan genap ganjil
18!^17!^16! Mod 19
17!^16!=genap krn 17!=genap,
maka
18!^17!^16! mod 19=1



konsep dari bang sihab untuk soal (p-3-n)!
konsepnya gni,

Cnth: Kan berlaku
25 Ξ 1 (mod 4)
25 Ξ 5 (mod 4)
25 Ξ 9 (mod 4)
25 Ξ 13 (mod 4)
dst

Cnth soal.
4! Ξ ... (mod 7)

Kita kan memanfaatkan teorema
5! Ξ 1 (mod 7)
5.4! Ξ 1 (mod 7)

Trus kita gunakan sifat pembagian yg sdh kita bhas sblumnya..
Fpb dr 5 dan 7 adlh 1

5.4!/5 Ξ 1/5 (mod 7/1)

Tp masak, itu hasilnya pecahan.. G mgkn kan, makanya kita manfaatin.

5.4! Ξ [1] (mod 7)
5.4! Ξ [8] (mod 7)
5.4! Ξ [15] (mod 7)

Dg angka yg d dlm krung siku itu hbs dbgi 5.

Jdi,
5.4! Ξ 15 (mod 7)

Sfat pmbgian

5.4!/5 Ξ 15/5 (mod 7/1)

Shg

4! Ξ 3 (mod 7)

yg d dlm kurung kotak kan sbnarnya
7k+1 dg k bil bulat

kita inginnya 7k+1 itu menghasikan bil bulat ktka dbagi 5.

Jd
(7k+1)/5 = n

Maka
7k + 1 = 5n
5n - 7k = 1

Cari deh yg mememuhi, n dan k adlh bulat


Salah satu yg memenuhi:
n0=3, k0=2 (0=nol)
jadi, n dan k:
n=n0+(b/d)m
=3+(-7/1)m
n=3-7m
k=2-5m
dengan m bilangan bulat

kalo angkanya besar, gunakan cara persamaan diophantine!

Misal, ngawur angkanya

127k - 51n = 1

127=51(2)+25
51=25(2)+1

Krn sdh ada 1, maka proses dibalik

1=51-(25)2
1=51-(127-51(2))2
1=51(5)-127(2)
1=127(2)-51(5)

Jd, n0=5 dan k0=2
‎

k0=2,n0=5
k=2+127k
n=-5-51k


misal variabelnya x,y
ax+by=1
127x+51y=1
cari x0 dan y0 kaya cara bang sihab (algoritma euclid)
terus, rumusnya:
x=x0+(b/d)k
y=y0-(a/d)k
atau
x=x0-(b/d)k
y=y0+(a/d)k
d=divisor=gcd(x,y)
k=bilangan bulat (parameter)


Pangkat Berulang
contoh soal!

soal 9.
5^6^7 mod 11

5^1=5 mod 11
5^2=3mod 11
5^3=4mod 11
5^4=9mod 11
5^5=1mod 11
berulang stiap 5^5n
6^7 mod 5=6^4.6^3 mod 5
=36.6 mod5
=1mod5
jadi,
5^6^7 mod 11
=5^(5k+1)mod 11
=5 mod 11

atau
5^6^7 mod 11
euler 11=10
pangkatnya mencari sisa jika dibagi 10
6^7 mod 10
6 mod 10

5^6 mod 11
(5^2)^3 mod 11
5 mod 11

atau lagy
5^6^7 Ξ ... (mod 11)

Euler(11)=10

6^7 Ξ ... (mod 10)
6 pngkt brpapun hsilnya angkanya satuannya ya 6.

Jd,
Soal bisa ditulis
5^6 Ξ ... (mod 11)

5 Ξ 5 (mod 11)
5^3 Ξ 125 (mod 11)
5^3 Ξ 4 (mod 11)
5^3.5^3 Ξ 4.4 (mod 11)
5^6 Ξ 5 (mod 11)


soal 10.
2^2012 mod 100

2^2012 mod 100
pakai pembagi mod bagi dengan 4

2^2012/4 mod 100/(gcd100,4)
2^2010 mod 25 karena 25 dan 2 relatif prima kita pakai teori fermatnya
2^10 mod 25
1024 mod 25
24 mod 25
pakai perkalian mod lgy kali dngan 4
96 mod 100

GCD=Great Common Divisor= faktor persekutuan terbesar (FPB)


soal 11.
6^6^6 mod 37

6^6^6 mod 37
6^6 yg diatas pangkat 6 dijabarin jadi
2^6.3^6
keluarin 2 nya jadi 2(2^5.3^6)
msukan ke pangkatnya lagy
6^6^6 mod 37
6^{2(2^5.3^6)}
(6^2)^(2^5.3^6)
(6^2)^(2^5.3^6) mod 37
(36)^(2^5.3^6) mod 37
(37-1) ^(2^5.3^6) mod 37
(-1)^(2^5.3^6) mod 37
liat pangkatnya genap atau ganjil jelas genap maka
1 mod 37

atau
euler 37=36
6^6 Ξ 0 mod 36 (pangkatnya)

6^6^6 mod 37
6^0 Ξ 1 mod 37
jd sisa 1

atau
6^6^6 mod 37
jadi 6^6 jbarin lgy jd
6^5.6
oh ya .(titik) itu kali ya
6^5 jbarin lagy jadi
2^5 .3^5 .2.3
duanya di taruh depan
2.2^5.3^5.3
3 nya kalikan ke 3^5
jadi 2(2^5.3^6)
(6^2)^(2^5.3^6) mod 37
(36)^(2^5.3^6) mod 37
(37-1) ^(2^5.3^6) mod 37
(-1)^(2^5.3^6) mod 37
liat pangkatnya genap atau ganjil jelas genap maka
1 mod 37



soal 12.
2010^2011^2012^2013 mod 100


2010^2011^2012^2013 mod 100
10^2011^2012^2013
euler 100 =40
brarti pangkatnya di mod 40
2011^2012^2013 mod 40
11^2012^2013 mod 40
euler 40=16
pangkatnya di mod 16
2012^2013 mod 16
12^5 mod 16
0 mod 16
atau jadi 16k

11^2012^2013 mod 40
11^(16k) mod 40
1 mod 40
40k+1

10^2011^2012^2013 mod 100
10^(40k+1) mod 100
10^40k .10 mod 100
0.10 mod 100
0 mod 100


soal 13.
10^11^12 Ξ.... (mod 13)

euler 13=12
11^12 Ξ 1 mod 12 (pangkatnya)

10^11^12=10^1
jd 10^11^12 Ξ 10 mod 13


soal 14.
43^43^43 mod 100

43^43^43 mod 100
euler 100=40
43^40k mod 100=1
43^43 mod 40?
Euler 40=16
43^(16.2+11)mod 40
=43^11 mod 40
=3^11 mod 40
={(3^4)^2}3^3 mod 40
=(81^2)27 mod 40
=1^2. 27 mod 40
=27 mod 40
=40k+27

43^(40k+27) mod 100
=43^40k . 43^27 mod 100
=1.43^27 mod 100
=(43^4)^6 .43^3 mod 100
=1. 43^3 mod 100
=49.43 mod 100
=7 mod 100

atau
euler 100 = 40
43^43 mod 40
= 43^40 . 43^3 mod 40
=1 . 43^3 mod 40
=> 43 Ξ 3 mod 40
= 43^3 Ξ 27 mod 40

43^27 mod 100
=> 43^2 Ξ 49 mod 100
=> 43^3 Ξ 7 mod 100
=> 43^4 Ξ 1 mod 100
=> 43^(4.6) Ξ 1 mod 100
43^27= 43^24 . 43^3 Ξ 1 . 7 mod 100
7 mod 100


soal 15.
JIKA X=125^1025, MAKA JUMLAH DARI 9 DIGIT TERAKHIR X ADALAH??

125^1025 = 0 mod5^9
125^1025=(125^4)^256 . 125 = 125 mod2^9
atau
x= 0 mod5^9
bearti x= a(5^9)
x= 125 mod2^9
a(5^9)= 125 mod2^9
a(5^6)=1 mod2^9
15625a= 1 mod512
265a= 1 mod512 --> 1=265a - 512b
pke algoritma euclid
512=265 + 247
265=247 + 18
247 = 18.13 + 13
18= 13.1 + 5
13=5.2 +3
5=3.1+2
3=2.1 +1
kita balik arah dapet:
1=-199.265 + 512.103 --> 1=265a - 512b
maka a=-199 =313 mod2^9 --> a=(2^9)c + 313
sehingga
x=a(5^9)
x=[(2^9)c + 313]5^9
x=1953125 . 313 + (10^9)c
x=611328125 + (10^9)c
jd 9 digit terakhirny adalah 611328125



contoh soal campuran

soal 16.
2011(18!) +[2011(17!)]^2012^2013^2014 +7.(15!) mod 19

# 2011(18!) mod 19
= 2011 . 18 mod 19
=-2011 mod 19
=3 mod 19

# {2011(17!)}^2012^2013^2014 mod 19
{2011.(1)}^2012^2013^2014 mod 19
16^2012^2013^2014 mod 19
euler 19=18
2012^2013^2014 mod 18
14^2013^2014 mod 18
euler 18=6
2013^2014 mod 6
3^2.1007 mod 6
3 mod 6

14^3 mod 18
8 mod 18

16^8 mod 19
6 mod 19

# 7.15! Ξ ... mod 19
cara 1.
16! Ξ (19-1)/2 mod 19
16.15! Ξ 9 mod 19
2^14.16.15! Ξ 2^14 .9 mod 19
15! Ξ (2^7)^2 .9 mod 19
15! Ξ 14^2 .9 mod 19
15! Ξ 6.9 mod 19
7.15! Ξ 72 mod 19
7.15! Ξ 16 mod 19

cara 2.
pake rumus ke 4
karena 19 adalah 6k+1 maka pakai rumus yang (p-4)! Ξ -(p+1)/6 (mod p) jadi
15! Ξ -(19-1)/6 (mod 19)
15! Ξ -3 (mod 19)7.15! Ξ -21 (mod 19)7.15! Ξ -3 (mod 19)
7.15! Ξ 16 (mod 19)


3 mod 19+6 mod 19+ 16 mod 19
=6 mod 19

jika x dan y prima dan n bilangan asli terbukti bahwa [x^(Φ(y)) +y^(Φ(x))] ≡ 1 (mod xy)
Φ(y)=euler dari y
Φ(x)=euler dari x


soal terakhir
17.Find a polynomial P(x) such that:
P(x) is divisible by (x^2 + 1), and
P(x) + 1 is divisible by (x^3 + x^2 + 1)

p(x)=0 mod (x"+1)
bisa ditulis
p(x)=(x"+1)k
kita kalikan dengan (x"'+x"+1)
(x"'+x"+1)p(x)=(x"'+x"+1)(
x"+1)k...............(1)
...
p(x)+1=0 mod (x"'+x"+1)
p(x)=-1 mod (x"'+x"+1)
bisa ditulis
p(x)=-1+(x"'+x"+1)m
kalikan dengan (x"+1)
(x"+1)p(x)=-(x"+1)+(x"+1)(x"'+x"+1)m........(2)

persamaan (1) kurangi persamaan (2)
(x"'+x"+1)p(x)=k(x"+1)(x"'
+x"+1)
(x"+1)p(x)=-(x"+1)+T (x"'+x"+1)(x"+1)
__________________________
_________-
x"'p(x)=(x"+1)(x"'+x"+1)(k-m)+(x"+1)

misalkan (k-m)=R jadi

x"'p(x)=(x"+1)(x"'+x"+1)R+
(x"+1) atau bisa ditulis
x"'p(x)=(x"+1) mod (x"+1)(x"'+x"+1)

so x"'p(x)=(x"+1)(x"'+x"+1)R+
(x"+1)
x"'p(x)=(x"+1)[1+(x"'+x"+1
)R]
p(x)=(x"+1)[1+(x"'+x"+1)R]/x"'

nah kita udah ketemu kan bentuk umum p(x) nya nah sekarang kita mencari R nya gmna caranya?
nah kalo (x"+1)/x"' gak bisa karena irreducible

skarang gmna carax agar
[1+(x"'+x"+1)R]/x"' bisa jadi polinomial

sekarang untuk (1 + R (x'''+ x''+1)) harus dapat dibagi oleh x"'
bisa ditulis
(1 + R (x'''+ x''+1)) = 0 mod x"'
1+Rx"'+Rx"+R =0 mod x"'
Rx "+ R +1 = 0 mod x"'
nah ide yang pertama misalkan R=S-1
jadi
(S-1)x" +(S-1) +1 = 0 mod x"'
Sx "-x" + S = 0 mod x"'
lagi kita punya ide *ide ini agar memudahkan kita supaya dapat saling menghilangkan dan kita akan menemukan itu bersisa 0*
misalkan lagi S = T + x "
(T+x")x" -x" +(T+x")=0 mod x"'
Tx" +x"" -x" + T + x" = 0 mod x"'
Kemudian Tx "+ x""+ T = 0modx"'
dan kita subtusi untuk T = x "' yang benar memenuhi
x"'.x" +x"" +x"' =0 mod x"'
yap terbukti

lanjut kita masukan x nya
T=x"'
S=T+x"
S=x"' +x"
R=S-1
R=x"' +x" -1

jadi R nya ketemu kan

nah sekarang masih banyak R yang memenuhi sekarang dengan ide ide kalian temukan R lain yang memenuhi untuk p(x) yang memenuhi, 3

nah salah satu bentuk untuk R adalah (x"'+x"-1)
jadi untuk p(x) nya bernilai
(x''+1) (1 + (x'''+ x''-1) (x''' + x''+1)) / x'''
aku sederhanakan jadi
x^5+2 x^4+2 x^3+2 x^2+x

buktinya
x^5+2 x^4+2 x^3+2 x^2+x = (x+2 x^2+x^3)(1+x^2)+0
x^5+2 x^4+2 x^3+2 x^2+x+1 = (1+x+x^2)(1+x^2+x^3)+0
rumus umum pada permasalahan hensel lemma