Penulis Topik: Probable Prime (Dibaca 7561 kali)

Mtk Kerajaan Mataram · « **pada:** Oktober 18, 2008, 07:12:53 AM »

Menurut Little Fermat Theorem jika p bilangan prima maka untuk setiap bilangan bulat a berlaku a^p=a(mod p). Khususnya jika p tidak membagi habis a atau katakan p dan a relatif prima maka a^(p-1)=1(mod p).
Teorema ini termasuk mudah pembuktiannya asal memahami binomial newton dan induksi matematik.
Okay kita tuliskan yang lebih terang, p prima ==> a^p=a(mod p)
Di sini konversnya (a^p=a(mod p) ==> p prima ) tidak berlaku artinya kalau p dan a memenuhi a^p=a(mod p) belum tentu p prima.
Bilangan p yang memenuhi a^p=a(mod p) biasa disebut dengan aPRP (probable prime base a), kemudian kalau ternyata bilangan p itu komposit maka disebut pseudoprime.
Contohnya :
5 termasuk 2-PRP karena 2^5=32=2(mod 5) karena 32=6x5+2
7 termasuk 2-PRP karena 2^7=128=2(mod 7) karena 128=18x7+2
9 bukan termasuk 2-PRP karena 2^9=512=56x9+8 tidak sama dengan 2(mod 9) jadi tidak termasuk 2-PRP
dst...semua bilangan prima akan memenuhinya.
tapi tidak semua yang memenuhi 2-PRP akan merupakan bilangan prima, yaitu contohnya
341 termasuk 2-PRP karena
2^341=4479489484355608421114884561136888556243290994469299069799978201927583742360321890761754986543214231552=2(mod 341)
tapi 341=11x31 (komposit)
Jadi 341 ini termasuk pseudoprime. Ada beberapa tapi tak terhingga pseudoprime ini, maksudnya dalam rentang yang lumayan adanya. Berawal dari sinilah primality test yang lebih modern dikembangkan, sampai yang lebih modern lagi adalah dengan teori group terutama teorema lagrange dimana indeks suatu group berhingga merupakan hasil perkalian indeks subgroup dengan indeks quotient groupnya, dalam hal bilangan prima ini groupnya adalah Z bilangan asli dan subgroupnya adalah pZ. Dan sampai terbentur pada hipotesa Riemann. Mulai dari yang sederhana di atas silahkan dilanjutkan pembicaraan yang lebih dalam lagi seperti Strong Probable Prime base a (a-SPRP)

Mtk Kerajaan Mataram · « **Jawab #1 pada:** Oktober 22, 2008, 09:45:18 PM »

Weh lanjut sendiri dulu juga ini jadinya....
Untuk memahami a-SPRP (Strong Probable Prime base a) kita mulai dari sebuah lemma yang juga penting dalam matematika yang mendasari sistem kriptografi. Ini sebelum membahas tentang primitive root.
Berikut lemmanya : Jika jika m suatu bilangan bulat positif dan x adalah bilangan bulat yang relatif prima terhadap m maka ada suatu bilangan bulat positif n sehingga x^n=1(mod m).
Buktinya :
Kita dengan bukti yang tidak formal dulu yang mudah ditangkap, misalnya m=7, maka kelas-kelas kongruensi modulo 7 adalah :
{0,7,14,21,28,...} = {0(mod 7)}
{1,8,15,22,29,...} = {1(mod 7)}
{2,9,16,23,30,...} = {2(mod 7)}
{3,10,17,24,31,...} = {3(mod 7)}
{4,11,18,25,32,...} = {4(mod 7)}
{5,12,19,26,33,...} = {5(mod 7)}
{6,13,20,27,34,...} = {6(mod 7)}
Kita ambil misalnya x=4 dan x relatif prima terhadap 7, lalu kita lihat 4^3=64=9x7+1=1(mod 7).
Jadi di sini n=3. Kita bisa mencoba yang lain. Hanya perlu diketahui bahwa yang membuat 4^n=1(mod 7) tidak hanya n=3, contohnya n=6 karena 4^6=4096=585x7+1=1(mod 7). Kemudian n yang terkecil yang memenuhi x^n=1(mod m) biasa disebut order kelas kongruensi modulo m terhadap x. Ini bukan bukti sebenarnya tapi saya kira lebih mudah untuk dipahami sebelum masuk yang betul-betuk niskala.

Mtk Kerajaan Mataram · « **Jawab #2 pada:** November 01, 2008, 05:53:47 AM »

Dilanjut lagi primanya...
Kayaknya belum ada yang berminat, padahal aplikasinya banyak nih..

{0,7,14,21,28,...} = {0(mod 7)}
{1,8,15,22,29,...} = {1(mod 7)}
{2,9,16,23,30,...} = {2(mod 7)}
{3,10,17,24,31,...} = {3(mod 7)}
{4,11,18,25,32,...} = {4(mod 7)}
{5,12,19,26,33,...} = {5(mod 7)}
{6,13,20,27,34,...} = {6(mod 7)}

2^1=2=2(mod 7),2^4=16=2(mod7),2^7=128=2(mod 7),...
2^2=4=4(mod 7),2^5=32=4(mod 7),2^8=256=4(mod 7),...
2^3=8=1(mod 7),2^6=64=1(mod 7),2^9=512=1(mod 7),...
Order kelas kengruensi 7 terhadap 2 adalah 3

3^1=3=3(mod 7),3^7=2187=3(mod 7),...
3^2=9=2(mod 7),3^8=6561=2(mod 7),...
3^3=27=6(mod 7),3^9=19683=6(mod 7),...
3^4=81=4(mod 7),3^10=59049=4(mod 7),...
3^5=243=5(mod 7),3^11=177147=5(mod 7),...
3^6=729=1(mod 7),3^12=531441=1(mod 7),...
Order kelas kengruensi 7 terhadap 3 adalah 6

4^1=4=4(mod 7),4^4=256=4(mod 7),...
4^2=16=2(mod 7),4^5=1024=2(mod 7),...
4^3=64=1(mod 7),4^6=4096=1(mod 7),...
Order kelas kengruensi 7 terhadap 4 adalah 3

5^1=5=5(mod 7),5^7=78125=5(mod 7),...
5^2=25=4(mod 7),5^8=390625=4(mod 7),...
5^3=125=6(mod 7),5^9=1953125=6(mod 7),...
5^4=625=2(mod 7),5^10=9765625=2(mod 7),...
5^5=3125=3(mod 7),5^11=48828125=3(mod 7),...
5^6=15625=1(mod 7),5^12=244140625=1(mod 7),...
Order kelas kengruensi 7 terhadap 5 adalah 6

6^1=6(mod 7),6^3=216=6(mod 7),...
6^2=36=1(mod 7),6^4=1296=1(mod 7),...
Order kelas kengruensi 7 terhadap 6 adalah 2

x=a(mod m) dengan 0<a<m
Ada k bilangan bulat sehingga
x=km+a ==> x^2=(km)^2+2kma+a^2=(mk^2+2ka)m+a^2 ==> x^2=a^2(mod m)
Dengan binomial newton, maka
x^n=Am+a^n=a^n(mod m), untuk suatu bilangan bulat A.

sehingga x^i=a^i(mod m) dan x^j=a^j(mod m) dengan 0<a<m.
Kapan terjadi x^i=x^j(mod m) ? Yaitu jika m|(x^j-x^i) atau
m|{x^i)}{x^(j-1)-1} dan karena x^i relatif prima terhadap m (x relatif prima terhadap m maka x^i relatif prima terhadap m), maka m|{x^(j-1)-1} ==> x^(j-i)=1(mod m) atau a^(j-i)=1(mod m)

Ini menghasilkan lemma yang kedua, yaitu :
Jika jika m suatu bilangan bulat positif dan x adalah bilangan bulat yang relatif prima terhadap m maka x^i=x^j(mod m) jika dan hanya jika j=i(mod d) dengan d adalah order kelas kongruensi m terhadap x.

Mtk Kerajaan Mataram · « **Jawab #3 pada:** November 06, 2008, 11:47:15 AM »

Lema tersebut kemudian dilanjutkan yang ketiga :
Jika p bilangan prima serta x dan y bilangan positif bulat yang keduanya relatif prima dengan p serta jika keduanya mempunyai order yang sama untuk kelas kongruensi modulo p, katakanlah ordernya d, maka ada bilangan bulat k yang relatif prima terhadap d sehingga y=x^k(mod p).

Nah.. dari sini lalu didefinisikan akar primitif. Misalkan m bilangan bulat positif, maka suatu bilangan bulat g dikatakan akar primitif modulo m jika untuk setiap bilangan bulat x yang relatif prima terhadap m, ada bilangan bulat j sehingga
x=g^j(mod m).

Mtk Kerajaan Mataram · « **Jawab #4 pada:** November 09, 2008, 08:58:20 AM »

Ulasan mengenai lemma-lemma :

Pertama :
"Jika jika m suatu bilangan bulat positif dan x adalah bilangan bulat yang relatif prima terhadap m maka ada suatu bilangan bulat positif n sehingga x^n=1(mod m)."

Contoh :
m=3, x=5 maka 5^1=5=2(mod 3), 5^2=25=1(mod 3) inilah karena 3 dan 5 relatif prima maka ada n=2 shg 5^2=1(mod 3)
m=5, x=10 maka 10^1=10=0(mod 5),10^2=100=0(mod 5), kita tahu untuk selanjutnya selalu merupakan 0(mod 5) jadi tak ada dong n yang memenuhi 5^n=1(mod 5) inilah karena 5 dan 10 tidak relatif prima.
m=6, x=8 maka 8^1=8=2(mod 6),8^2=64=4(mod 6),8^3=512=2(mod 6),8^4=4096=4(mod 6), dst ini selalu berselang-seling antara 2(mod 6) dan 4(mod6) dan bisa dibuktikan dengan induksi yaitu 8^n-2 habis dibagi 6 jika n ganjil dan 8^n-4 habis dibagi 6 jika n genap. Inilah karena 6 dan 8 tidak relatif prima.

Jika m bilangan prima maka untuk x bilangan asli dibawah m akan selalu relatif prima terhadap m,
contohnya jika m=7, maka 1,2,3,4,5,dan 6 relatif prima terhadap 7.
Jadi untuk m bilangan prima, maka untuk semua x lebih kecil dari m, akan selalu ada n sehingga x^n=1(mod m)

Kedua :
"Jika jika m suatu bilangan bulat positif dan x adalah bilangan bulat yang relatif prima terhadap m maka x^i=x^j(mod m) jika dan hanya jika j=i(mod d) dengan d adalah order kelas kongruensi m terhadap x."

Kita lihat pada contoh kelas-kelas kongruensi modulo 7 di atas, yakni m=7 dan x=5 :
5^6=15625=1(mod 7),5^12=244140625=1(mod 7),...
Order kelas kengruensi 7 terhadap 5 adalah 6
Kalau kita teruskan maka 5^6, 5^12, 5^18, 5^24,... semuanya merupakan 1(mod7). Jadi ambilah 5^6=15625 dan 5^18=3814697265625
dan 5^18-5^6 = 3814697250000 = 544956750000 x 7 sehingga 5^18=5^6(mod 7) dan kita lihat j=18 dan i=6 sehingga j=i(mod 6), di sini 6 merupakan order kelas kongruensi modulo 7 terhadap 6.
Lebih lanjut lemma ini juga menjamin bahwa jika x^i=x^j(mod m) maka x^i dan x^j berada pada kelas yang sama. Karena untuk semua x bilangan bulat positif di bawah m relatif prima terhadap m jika m prima, maka berarti kelas kongruensi modulo 7 - nya berlain-lainan (distinct)

Ketiga :
"Jika p bilangan prima serta x dan y bilangan positif bulat yang keduanya relatif prima dengan p serta jika keduanya mempunyai order yang sama untuk kelas kongruensi modulo p, katakanlah ordernya d, maka ada bilangan bulat k yang relatif prima terhadap d sehingga y=x^k(mod p)."

Kita ganti simbol m menjadi p untuk mulai memastikan bahwa kita bekerja pada bilangan prima. Kita ambil contoh p=7 serta x dan y masing-masing 5^6=15625 dan 5^18=3814697265625 dan keduanya ini kita tahu relatif prima terhadap 7 (bisa dibuktikan dengan induksi bahwa jika x relatif prima terhadap p maka x^n relatif prima terhadap p). Keduanya berorder d=6 atas kelas kongruensi modulo 7. Maka kita lihat 5^18=5^6(mod 7) ==> 5^18=(5^6)^5(mod 7), disini k=5 relatif prima terhadap d=6. Bisa dihitung bahwa 5^30-5^18 = 931322574615478515625-3814697265625 = 931322570800781250000 = 133046081542968750000 x 7.

Mtk Kerajaan Mataram · « **Jawab #5 pada:** November 12, 2008, 12:55:37 PM »

Berikut bukti formal lemma, saya kira yang bisa memahami orang-orang dari matematika atau fisika. Lemma yang pertama dulu.

Lemma 1 :
Taruhlah m bilangan bulat positif, dan x adalah bilangan bulat yang relatif prima terhadap m. Maka ada bilangan bulat positif n sedemikian hingga x^n=1(mod m).

Bukti :
Kelas-kelas kongruensi modulo m banyaknya berhingga, yaitu sebanyak m :
{0(mod m)}, {1(mod m)}, {2(mod m)},. . ., {m-1(mod m)}
Setiap bilangan bulat pasti menjadi anggota dari salah satu kelas-kelas kongruensi tersebut.
Maka kita bisa memilih i dan j sehingga x^i=x^j(mod m) dengan i<j. Mungkin ini agak membingungkan mengapa bisa demikian, kita lihat lagi bahwa kelas-kelas kongruensi tersebut bisa dituliskan dengan :
{km}, {km+1}, {km+2},..., {km+m-1}
Misalkan x^i anggota {km+q} dengan 0=<q<m, maka pada langkah-langkah berikutnya tentu terdapat x^j anggota {km+q}.
Sebagai contoh, 8^3=512=2(mod 17), lalu 8^11=8589934592=2(mod 17), sehingga 8^3=8^11(mod 17).
Untuk generalnya, sebagai berikut :
Asumsikan tidak ada j>i sehingga x^i=x^j(mod m) berarti misalkan x^i=q(mod m) dengan 0=<q<m, maka untuk semua j>i berlaku x^j<>q(mod m), taruhlah x^i=km+q untuk suatu bilangan bulat positif k, maka (x^i)^2=(km)^2+2kmq+q^2=(mk^2+2kq)m+q^2=q^2(mod m) dan dapat ditunjukkan dengan binomial newton bahwa (x^i)^m=q^m(mod m).
Kita perhatikan bahwa menurut teorema Fermat Kecil maka q^m=q(mod m) atau dengan kata lain m membagi habis (q^m-q). Jadi q^m = (q^m-q) + q = q(mod m). Sehingga asumsi kita gagal karena dengan mengambil j=im, maka x^j=x^(im)=(x^i)^m=q^m(mod m)=q(mod m).
Karena itu Kita bisa menaruh x^j=x^i(mod m) atau x^i=x^j(mod m)
Taruhlah n=j-i maka (x^i)(x^n)=(x^i)(mod m)
Karena x relatif prima terhadap m, maka ada a dan b sehingga ax + bm = 1 ==> ax=1-bm ==> (ax)^i=(1-bm)^i
==> (a^i)(x^i) = 1 + Hm untuk suatu bilangan bulat H ==> (a^i)(x^i) - Hm = 1 sampai disini kombinasi linear ini memberikan arti bahwa x^i dan m relatif prima. Akhirnya kita bisa melakukan kanselasi yang menjadikan (x^n)=1(mod m). Terbukti.

Mtk Kerajaan Mataram · « **Jawab #6 pada:** November 15, 2008, 07:34:21 AM »

Sebaiknya juga kutuliskan bukti Little Fermat Theorem berikut :

Taruhlah p sebuah bilangan prima. Maka x^p=x(mod p) untuk semua bilangan bulat x. Lebih lanjut jika x relatif prima terhadap p maka x^(p-1)=1(mod p).

Sebelumnya kita buktikan lemma berikut sebagai pendahuluannya :
Lemma :
Taruhlah p bilangan prima. Maka koefisien binomial C(p,k) habis dibagi p untuk semua bilangan bulat k yang memenuhi 0 < k < p.
Bukti :
Koefisien binomial diberikan dengan formula C(p,k)=p!/{(p-k)!k!}
Jika 0<k<p maka C(p,k) = [p(p-1)!] / [(p-k)!k!] = pm / k! dengan m=(p-1)! / (p-k)!. Sehingga (k!)C(p,k) = pm, maka k! membagi habis pm. Juga karena k! relatif prima terhadap p, ini dikarenakan p prima dan semua bilangan positif lebih dari 1 dan kurang dari p akan relatif prima ternadap q.
{ jika a dan p relatif prima juga b dan p relatif prima maka ab relatif prima terhadap p, karena jika ada g,h,i,j bilangan bulat sehingga ga+hp=1 juga ib+jp=1 maka (ga)(ib)=(1-hp)(1-jp)=1-(h+j)p+hjp^2 ==> (gi)ab + (h+j-hjp)p=1 }
Karena k! membagi habis pm dan k! relatif prima terhadap p maka haruslah k! membagi habis m. Sehingga koefisien binomial C(p,k) merupakan kelipatan p. Terbukti.

Bukti Teorema Fermat :
Taruhlah p prima maka (x+1)^p=Sigma(dari k=0 ke p) C(p,k)x^k
Menurut lemma di atas maka (x+1)^p=(x^p+1)(mod p). Sehingga jika f(x)=x^p-x maka
f(x+1)(mod p)=(x^p+1)(mod p) - (x+1)(mod p)
f(x)(mod p)=(x^p)(mod p) - x(mod p)
___________________________________________ -
f(x+1)(mod p) - f(x)(mod p) = 1(mod p) - 1(mod p) = 0(mod p)
==> f(x+1)=f(x)(mod p)

Jadi f(x+1)=f(x)(mod p) untuk semua bilangan bulat x.
Karena f(0)=0^p-0=0(mod p) maka
f(1)=f(0+1)=f(0)(mod d)=0(mod p),
f(2)=f(1+1)=f(1)(mod p)=0(mod p),
f(3)=f(2+1)=f(2)(mod p)=0(mod p),
dst dengan induksi... jadi untuk semua x positif f(x)=0(mod p).

Kita bergerak pada bilangan bulat, jadi karena f(x+1)=f(x)(mod p) maka f(x)=f(x+1)(mod p), lalu
f(0)=f(-1+1)(mod p)=f(-1) dan f(0)=0(mod p) ==> f(-1)=0(mod p),
f(-1)=f(-2+1)(mod p)=f(-2)(mod p) dan f(-1)=0(mod p) ==> f(-2)=0(mod p),
f(-2)=f(-3+1)(mod p)=f(-3)(mod p) dan f(-2)=0(mod p) ==> f(-3)=0(mod p),
dst dengan induksi... jadi untuk semua x negatif f(x)=0(mod p).

Jadi untuk semua bilangan bulat f(x)=0(mod p).
Berarti x^p-x=0(mod p) ==> x^p=x(mod p), Untuk mana x relatif prima terhadap p, maka kita bisa
melakukan kanselasi (x^p)/x=1(mod p) ==> (x^(p-1))=1(mod p). Terbukti.

Mtk Kerajaan Mataram · « **Jawab #7 pada:** November 16, 2008, 08:20:22 AM »

Bukti Formal Lemma Kedua :

Taruhlah m bilangan bulat positif, dan x bilangan bulat yang relatif prima terhadap m, serta i dan j bilangan bilangan-bilangan bulat positif. Maka (x^i)=(x^j)(mod m) jika dan hanya jika i=j(mod d) dimana d adalah order kelas kongruensi modulo m terhadap x.

Bukti :
Kita akan membuktikan biimplikasi (x^i)=(x^j)(mod m) <==> i=j(mod d)
Kita bisa memilih i<j dan ini tidak menyebabkan lepas dari generalitasnya.

Pertama kita buktikan i=j(mod d) ==> (x^i)=(x^j)(mod m) :
Jika i=j(mod d) maka d | (j-i) ata ada bilangan bulat b sehingga (j-i)=bd, sehingga karena x^d=1(mod m) [ingat bahwa d adalah order kelas kongruensi modulo m terhadap x] dan misalkan x^d=km+1 kemudian (x^(j-i))=x^(bd)=(x^d)^b=(km+1)^b=Lm+1=1(mod m) untuk suatu L bilangan bulat. Sehingga x^j=(x^i)(x^(j-i))=(x^i)(1(mod m)) ==> (x^j)=(x^i)(mod m).

Kedua kita buktikan (x^i)=(x^j)(mod m) atau (x^j)=(x^i)(mod m) ==> i=j(mod d) :
Kita telah memilih i < j, maka (x^i)(x^(j-i))=(x^i)(mod m) dan karena x relatif prima terhadap m, sehingga x^i relatif prima terhadap m, ini menjadikan x^(j-i)=1(mod m). Sehingga jika d order kelas kongruensi modulo m terhadap x maka x^d=1(mod m). Kemudian misalkan j-i=kd+r dengan 0 =< r< d maka x^(j-i) = x^(kd+r) = ((x^d)^k)(x^r) = 1(mod m)
==> (x^r)=1(mod m). Ehh tapi d adalah order dari kelas modulo m terhadap x jadi harusnya d yang terkecil sehingga (x^d)=1(mod m), kalau ternyata (x^r)=1(mod m) dengan 0 =< r< d maka harusnya r=0 dan terbukti bahwa
d|(j-i) atau j=i(mod d). Terbukti.

Mtk Kerajaan Mataram · « **Jawab #8 pada:** Desember 05, 2008, 01:58:23 PM »

Ternyata memang belum ada yang begitu berminat atau terlalu susah dipahami yaa, tapi saya rasa orang2 matematika terutama yang master atau yang pernah belajar kriptografi pernah membacanya kalo ada di forum ini.
Disini untuk memahami bukti lemma ketiga dibutuhkan prasyarat lebih terutama pemahaman tentang penyelesaian suku banyak kongruensi modulo n. Saya belum menemukan cara yang mangkus untuk membuatnya jadi jelas. Melangkah dari konkrit ke abstrak memang membutuhkan energi pikiran.

mkukuh · « **Jawab #9 pada:** Desember 29, 2008, 02:35:22 AM »

salam kenal kerajaan mataram
saya kukuh..newbie ni
saya baru nemu situs ni pas dini hari..tak bobok dulu ya..
o y saya tertarik ntar tak pelajari dulu...ok pak asisten dosen/dosen.
jangan pernah kesepian yo...salam

Mtk Kerajaan Mataram · « **Jawab #10 pada:** Januari 05, 2009, 09:04:38 PM »

Salam saudara mkukuh, topik ini adalah pada teori bilangan elementer yaitu tentang primitive root, senang bisa berdialog. Saya bukan dosen dari suatu institusi, hanya seorang praktisi komputer berlatar belakang matematika. Karena melihat teori bilangan bermain disini maka saya ublek2.

Mtk Kerajaan Mataram · « **Jawab #11 pada:** Pebruari 10, 2009, 09:30:57 PM »

Oke biar kuhangatkan lagi biar tidak usang digulung tempat terus...karena topik ini termasuk menarik sekaligus pelik.

Kita putar balik dulu pada kongruensi persamaan polinomial dan fungsi Euler..supaya tidak menjendel di jalan.

Fungsi Euler dulu lah..

Taruhlah n bilangan bulat positif. Kita definisikan $\Psi(n)$ sebagai banyaknya bilangan bulat x yang memenuhi
0 =< x < n yang relatif prima terhadap n. Fungsi Xi pada himpunan bilangan bulat positif kita sebut sebagai
fungsi Euler.

Setiap bilangan bulat (termasuk nol) relatif prima terhadap 1, karena itu $\Psi(1)=1$ .
Taruhlah p bilangan prima. Maka $\Psi(p)=p-1$ , karena setiap bilangan bulat positif kurang dari p akan relatif
prima terhadap p. Lebih lanjut $\Psi(p^k)=(p^k)-(p^{k-1})$ untuk semua bilangan bulat positif k, karena bilangan
bulat yang memenuhi $0\le x \le p^k$ yang habis dibagi p ada sebanyak $p^{k-1}$ , dan bilangan bulat yang relatif
prima terhadap p adalah yang selain habis dibagi p.
Contoh :
p=5 ==> $\Psi(5)=4$ , yaitu {1,2,3,4}
p^2=25 ==> $\Psi(25)=5^2-5^1=20$ , yaitu {1,2,3,4,6,7,8,9,11,12,13,14,16,17,18,19,21,22,23,24}
yang habis dibagi 5 adalah {5,10,15,20,25} sebanyak 5

Secara general untuk $p^k$ :
Bilangan bulat positif yang habis dibagi p dari 1 s.d. $p^2$ adalah $p,2p,3p,...,p^2$ ==> sebanyak p
Bilangan bulat positif yang habis dibagi p dari $p^2+1$ s.d. $2p^2p^2+1 s.d. 2p^2$ adalah $p^2+p,p^2+2p,...,2p^2$ adalah $p^2+p,p^2+2p,...,2p^2$ ==> sebanyak p
Bilangan bulat positif yang habis dibagi p dari $2p^2+1 s.d. 3p^2$ adalah $2p^2+p,2p^2+2p,...,3p^2$ ==> sebanyak p
...........
...........
Bilangan bulat positif yang habis dibagi p dari $(p-1)p^2+1 s.d. p^3$ adalah $(p-1)p^2+p,(p-1)p^2+2p,...,p^3$ ==> sebanyak p
[sampai disini yang habis dibagi p sebanyak p^2]
Bilangan bulat positif yang habis dibagi p dari $p^3+1$ s.d. $p^3+p^2$ adalah $p^3+p,p^3+2p,...,p^3+p^2$ ==> sebanyak p
..........
..........
dan seterusnya....
akhirnya yang habis dibagi p sebanyak $p^{k-1}$

Masih berlanjut .... nulisnya cukup ngoyo ini...tapi yang penting bisa bermanfaat.

nandaz · « **Jawab #12 pada:** Pebruari 11, 2009, 02:39:13 PM »

waw, rumit... hebat sekali!!! (sebetulnya ngga ngerti sih...)

Mtk Kerajaan Mataram · « **Jawab #13 pada:** Pebruari 13, 2009, 11:01:04 PM »

Yaa memang rumit...biasanya dalam literatur-literatur hanya disingkat penjelasannya, semoga uraian ini bisa membawa titik terang.

Jadi kemarin dari 1 sampai dengan p^k ada sebanyak p^k-1 bilangan yang habis dibagi dengan p dengan kata lain karena p-nya prima maka ada sebanyak p^k-1 bilangan yang tidak relatif prima terhadap p^k dan lalu berarti ada sebanyak p^k-p^k-1 bilangan dari 1 sampai dengan p^k yang relatif prima terhadap p^k.

Lalu berapa banyaknya bilangan dari 1 s.d. p^aq^b yang relatif prima terhadap p^aq^b dengan p dan q keduanya prima ?

Yang tidak relatif prima terhadap p^a sebanyak p^a-1 dari 1 s.d. p^a,
Yang tidak relatif prima terhadap q^b sebanyak q^b-1 dari 1 s.d. q^b.
tidak relatif prima terhadap p^a atau terhadap q^b berarti juga tidak relatif prima terhadap p^aq^b.

1,2, ..., p^aq^b
= 1,2,...,p^a,
p^a+1,p^a+2,...,p^a+p^a,
.................
[q-1]p^a+1,[q-1]p^a+2,...,qp^a,
..................
[q^b-1]p^a+1,[q^b-1]p^a+2,...,[q^b]p^a.

Tunjukkan bahwa banyaknya bilangan yang relatif prima terhadap p^aq^b adalah [p^a-p^a-1][q^b-q^b-1] ....

ryoma · « **Jawab #14 pada:** Pebruari 14, 2009, 09:02:23 AM »

Kutip dari: nandaz pada Pebruari 11, 2009, 02:39:13 PM

waw, rumit... hebat sekali!!! (sebetulnya ngga ngerti sih...)

walah-walah..

Artikel Sains

Aku Cinta ForSa

Pranala Luar

ShoutBox!

Penulis Topik: Probable Prime (Dibaca 7561 kali)