Modulo (2)

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) dan -(p-1)/6 (mod p) ada dua kemungkinan
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 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

contoh soal campuran

soal 15.
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