Rabu, 31 Oktober 2012

Fungsi phi-euler

Kita tahu teorema kecil fermat menyatakan
Untuk sebarang bilangan bulat a dan bilangan prima p yang coprime ke a berlaku
a^{p-1}\equiv 1\pmod p
Nah..sekarang bagaimana jika modulusnya tidak prima, composite, apakah teorema kecil fermat masih berlaku?
Tidak, sebgai contohnya jika kita ambil a=2 dan n=15,
apakah 2^{14}\equiv 1\pmod {15}
Tidak karena 15 tidak membagi 16383=2^{14}-1.
Akan tetapi ada cara memodifikasi teorema kecil fermat sehingga tetap berlaku meskupun modulusnya tidak prima. Teorema fermat yang udah dimodifikasi inilah yang disebut teorema euler.
Nah..sebelum membahas teorema euler akan saya bahas mengenai fungsi euler-phi
Definisi: Fungsi phi-euler, adalah fungsi pada bilangan asli n yang didefinisikan sebgai berikut
\phi\left(n\right) adalah banyaknya bilangan pada \left\{ 1,2,3\ldots,n-1\right\} yang coprime ke n
Contoh: \phi\left(8\right)=4 karena ada 4 bilangann asli yang kurang dari 8 yang coprime ke 8 ke-4 bilangan tersebut adalah 1,3,5,7. \phi\left(11\right)=10 kerna semua bilangan pada \left\{ 1,2,3\ldots,10\right\} coprime ke 11.
Teorema
  1. Jika p prima maka \phi\left(p\right)=p-1
  2. Jika p prima dan  n\geq1 maka \phi\left(p^n\right)=p^n-p^{n-1}
Bukti
1. Jika p prima maka semu bilangan pada \left\{ 1,2,3\ldots,p-1\right\} coprime ke p, itu artinya \phi\left(p\right)=p-1
2. Ada p^n elemen pada himpunan \left\{ 1,2,3\ldots,p^n\right\} . Elemen pada himpunan tersebut tidak coprime ke p jika hanya jika dapat dibagi oleh p. Elemen pada himpunan yang dapat dibagi oleh p adalah
1p,\:,2p\:3\cdot p,\ldots,p^{n-1}\cdot p
Ada sebanyak p^{n-1} elemen yang tidak coprime ke p maka banyaknya elemen yang coprime ke p sebanyak p^n-p^{n-1}
Definisi: Sistem residu tereduksi mod n (reduced residue system mod n) adalah himpunan bilangan-bilangan
a_{1},a_{2},a_{3},\ldots,a_{\phi\left(n\right)}
Yang memenuhi
  1. Jika i\neq j maka a_{1}\not\equiv a_{j}\pmod n
  2. Untuk setiap a_i coprime ke n
Dengan demikian Sistem residu tereduksi mod n merepresentasikan bilangan-bilangan yang coprime ke n
Contoh: \left\{ 1,5,7,11\right\} dan \left\{ 11,17,-1,31\right\} keduanya merupakan sistem residu tereduksi mod 12
Lemma: Diberikan \phi\left(n\right)=k dan \left\{ a_{1},a_{2},\ldots,a_{k}\right\} adalah Sistem residu tereduksi mod n, berlaku:
  1. Untuk semua bilangan bulat m maka  \left\{ a_{1}+mn,a_{2}+mn,\ldots,a_{k}+mn\right\} merupakan sistem residu tereduksi mod n.
  2. Jika m coprime ke n maka \left\{ ma_{1},ma_{2},\ldots,ma_{k}\right\} merupakan sistem residu tereduksi mod n.
Akibat: Diberikan \phi\left(n\right)=k dan \left\{  a_{1},a_{2},\ldots,a_{k}\right\} adalah Sistem residu tereduksi mod n, jika s coprime ke n dan t sebarang bilangan bulat maka \left\{ sa_{1}+t,sa_{2}+t,\ldots,sa_{k}+t\right\} merupakan sistem residu tereduksi mod n.
Contoh: \left\{ 1,5\right\} merupakan sistem residu tereduksi mod 6. tmabahkan 12=2\times 6 pada setiap bilangan diperoleh \left\{ 13,17\right\}, sistem residu tereduksi mod 6 lainnya, Kita tahu 6 coprime ke 25, jika kita kalikan sistem yang awal dengan 25 diperoleh \left\{ 25,125\right\} istem residu tereduksi mod 6 lainnya, terakhir \left\{ 25+12,125+12\right\}=\left\{ 37,137\right\} juga merupakan sistem residu tereduksi mod 6
Selanjutnya kita bahas teorema euler
Teorema Euler: Setiap bilangan bulat a dan n bilangan bulat positif  yang coprime ke a maka
a^{\phi\left(n\right)}\equiv 1\pmod n
Perhatikan jika n prima maka a^{n-1}\equiv 1\pmod n, teorema euler berubah menjadi teorema kecil fermat. Dengan demikian kita bisa menganggap teorema euler sebagai generalisasi teorema kecil fermat.
Bukti: Ambil \phi\left(n\right)=k dan \left\{   a_{1},a_{2},\ldots,a_{k}\right\} adalah Sistem residu tereduksi mod n, diasumsikan a_i termuat di \left\{ 1,2,3\ldots,n-1\right\} .
Karena a dan n coprime maka  \left\{a   a_{1},aa_{2},\ldots,aa_{k}\right\} juga merupakans sistem residu tereduksi mod n, Kedua sistem tersebut haruslah mempunyai hasil perkalian modulus n yang sama
\left(aa_{1}\right)\ldots\left(aa_{k}\right)\equiv a_{1}\ldots a_{k}\pmod n
a_{k}\left(a_{1}\ldots a_{k}\right)\equiv a_{1}\ldots a_{k}\pmod n
Karean setiap a_i coprime ke n, jika dikalikan kedua sisi dengan a_{1}^{-1}\ldots a_{k}^{-1} diperoleh
a^{k}\equiv 1\pmod n atau dengan kata lain  a^{\phi\left(n\right)}\equiv 1\pmod n

Selasa, 30 Oktober 2012

Teorema Penjodohan

Assalamu alaikum sahabatku yang Smart!
Berikut ini postingan yang berkaitan dengan materi Graphdalam postingan ini diberikan beberapa masalah yang berkaitan dengan teorema Penjodohan. Semoga bermanfaat ya....belajar
===========================tosstosstoss===========================


Teorema Penjodohan

Sabtu, 27 Oktober 2012

Mutiara Kata # 2

Sahabat, Ketika orang mengkritik kita cobalah untuk intropeksi diri. daripada sibuk mencari alasan untuk membela diri, lebih baik sibuk jujur akan kekurangan diri dan fokus untuk memperbaikinya. Insya Allah semuanya akan bernilai di sisi Allah. SWT
 berpikir
Aku yakin Skenario Allah. SWT lebih baik dari Skenario yang kubuat maupun yang mereka buat.
jadi, mengapa aku harus Khawatir? Jika Allah. SWT telah mempersiapkan yang terbaik untukku?

 berpikir
Menghormati orang lain merupakan pilihan yang lebih baik ketimbang membicarakan keburukan orang yang yang belum begitu kita kenal.
 berpikir
Terhempas ku terjaga dari lingkar mimpi, suaramu terniang menghembus khayalku. Dan ku akui tanpa kemunafikan "Ku Cinta Kau".
Bayangmu menghantui setiap gerakku. dahagaku akanmu balikkan emosi dan juga ambisiku. Dan ku akui tanpa kemunafikan "Ku Cinta Kau".

 berpikir
“Dijadikan indah pada pandangan manusia terhadap wanita-wanita, anak-anak, harta yang banyak yang meliputi emas, perak, kuda pilihan, binatang ternak, sawah ladang. Itulah kesenangan hidup di dunia, dan di sisi Allah tempat kembali yang baik (surga).”
Ali Imron : 14

 berpikir
Allahu Akbar!
Allah Maha Besar. Dia-lah satu-satunya Penguasa segala Karunia, amat mudah bagi-Nya mengangkat dan memberi kedudukan di hati mahluk.

 berpikir
Kedewasaan bukanlah dilihat dari usia ataupun tutur kata seseorang, melainkan dari cara orang tersebut menyikapi setiap permasalahan yang dihadapinya.
 berpikir
Persahabatan sejati layaknya kesehatan, nilainya baru kita sadari setelah kita kehilangannya
Seorang sahabat adalah yang dapat mendengarkan lagu di dalam hatimu dan akan menyanyikan kembali tatkala kau lupa akan bait-baitnya
Seorang teman sejati akan membuat Anda hangat dengan kehadirannya, mempercayai akan rahasianya dan mengingat Anda dalam doa-doanya.
Namun kita tidak akan pernah memiliki seorang teman, jika kita mengharapkan seseorang tanpa kesalahan. Karena semua manusia itu baik kalau kita bisa melihat kebaikannya dan menyenangkan kalau kita bisa melihat keunikannya tapi semua manusia itu akan buruk dan membosankan kalau kita tidak bisa melihat keduanya

 berpikir
Senja menyapa jiwa - jiwa yang lelah hari ini, menghantarku untuk kembali mempersiapkan diri untuk menjemput impian. Aku ingin Berhasil bukan karena adanya keberuntungan, tapi aku ingin Berhasil karena memang aku layak untuk Berhasil. Untuk itu aku kan terus berusaha...
 berpikir
Tak terasa peri malam telah mengalunkan merdu suaranya, memaksa jiwaku untuk berlabuh ke Peraduanku. Pejamkan mata, menjemput impian dan lantunkan harap kiranya semua impian indah kan terwujud dalam dunia nyataku...
 berpikir
Terkadang kita merasa sesuatu itu berarti ketika telah kehilangannya.
Sesal tak pernah meghiasi perjalanan hidup ini diawal kisah. Tapi jangan biarkan penyesalan menghalangi kita untuk bergerak menjemput impian.

 berpikir
Jujur aku IRI dengan mereka.
Mereka dapat melaksanakan perintah Allah dengan ISTIQAMAH, sedangkan Aku tidak.
Jujur aku merasa IRI dengan mereka.
Mereka memiliki jiwa-jiwa yang jauh dari Nafsu Duniawi, sedangka Aku tidak.
Jujur aku merasa IRI dengan mereka.
Mereka memiliki komitmen yang kuat dalam Keimanan, sedangkan Aku tidak.
Ya Allah bantulah aku untuk menjadi seperti mereka. Karena andaikan Aku seperti mereka, sungguh sangat bahagia diri ini.

       

Jumat, 26 Oktober 2012

Graph Pohon

Assalamu alaikum Sahabat yang Smart!
Postingan berikut berkaitan dengan materi Graph. Sebagaimana kita ketahui bahwa Graph dibentuk oleh himpunan titik dan sisi.
Dan secara garis besar Graph terbagi atas dua, yaitu Graph yang membentuk Pohon dan Graph yang tidak membentuk pohon.
Nah berikut ini adalah beberapa pembuktian yang berkaitan dengan keduanya. Semoga bermanfaat ya...belajar

================================main gamemain gamemain game===========================
Graph Pohon

Mutiara Kata # 1

Assalamu alaikum Sahabatku yang Smart!
Dalam renungan malam, terkadang sebait kalimat terniang ditelingaku, menyapa kesunyian Qalbuku dan mengingatkan Jiwaku pada keihlafan yang sering mengganggunya.
Untuk itu ku coba tuangkan dalam rangkaina kalimat untuk sekedar dijadikan lentera dalam menjalani gelapnya kehidupan di dunia yang fana ini.

================================belajar================================
Kuingat sebuah pesan yang menusuk dalam batin.
“Orang mulia menyalahkan dirinya, orang bodoh menyalahkan orang lain
“Mengenal diri yang paling penting, adalah utama demi kesadaran jagat raya.
Berarti pula memahami kesalahan, serta kekeliruannya masing-masing.
 berpikir
Berbicara tentang hidup dan kehidupan adalah berbicara tentang "PILIHAN".
Sebab hidup dan kehidupan erat kaitannya dengan pilihan. Jalan mana yang semestinya kita pilih, harus dipertimbangkan secara matang agar penyesalan tidak timbul di kemudian hari.
Demikian pula halnya dalam berbuat kebaikan atau maksiat, sepenuhnya diserahkan kepada kita untuk memilihnya.
Dan sebuah keniscayaan dari pilihan yang telah kita tentukan adalah semuanya akan berakhir pada kematian. Pada kematian itu kita akan menuai semua hasil dari pilihan kita.
berpikir
Terkadang keinginan tak sesuai harapan. Tapi yakinilah bahwa apa yang kita jalani sekarang ini memang sudah selayaknya sesuai dengan kebutuhan kita.
Karena sesungguhnya Allah lebih mengetahui apa yang kita butuhkan...
berpikir 
Hati-hati dengan "PIKIRAN" anda, karena "PIKIRAN" anda akan menjadi "PERKATAAN" anda. 
Hati-hati dengan "PERKATAAN" anda, karena "PERKATAAN" anda akan menjadi "PERBUATAN" anda.
Hati-hati dengan "PERBUATAN" anda, karena "PERBUATAN" anda akan menjadi "KEBIASAAN" anda.

Hati-hati dengan "KEBIASAAN" anda, karena "KEBIASAAN" anda akan menjadi "KEPRIBADIAN" anda.
berpikir 
sebagai manusia biasa kita tentu pernah merasakan kebencian terhadap seseorang. Tapi jangan kebencian itu melahirkan kedengkian.
karena sebesar apapun kedengkian kita kepada seseorang, tidak akan menghalangi karunia Allah kepadanya.
Tapi sebaliknya kedengkian itu akan membakar amalan kita layaknya api membakar kayu.
 berpikir 
Ketika pintu kebahagiaan tertutup,
banyak pintu lain terbuka,
tetapi kadang kita menatap pintu yang telah tertutup terlalu lama,
sehingga kita tidak melihat pintu lain yang telah terbuka untuk kita.
  berpikir 
Sahabat, tanpa kita sadari ternyata:
Kejadian sepahit dan segetir apapun yang bisa membuka mata hati kita sehingga bisa tahu dan sadar akan kesalahan diri adalah sebuah karunia yang besar.
Jadi marilah kita selalu berprasangka baik terhadap Cobaan yang diberikan-Nya kepada kita ya.
berpikir 
Sudah Sunnatullah jika manusia itu tidak lepas dari keluh kesah.
Tapi jika tiap hari hanya di isi dengan keluh kesah, maka kita tidak pernah merasakan nikmatnya kehidupan ini.
Dari pada kita berkeluh kesah, lebih baik jika kita berusaha menjadi pribadi yang baik dari hari ke hari...
 berpikir 
Ketidakhati-hatian dalam berkata-kata, bisa berakibat Riya/Pamer. Ujub membangga-bangakan diri, Sombong, Ghibah atau bahkan bisa berakibat Fitnah.
Jadi, marilah kita menjaga lidah kita agar senantiasa berhati-hati dalam berucap.
 berpikir 

Tak ada Gading yang tak retak. karena itu jika kita telah benar-benar dalam kebenaran yang Allah Ridhoi, niscaya hati kita akan tenang dan mantap apapun yang terjadi

 berpikir 

Sahabat, Ketika Setan mengingatkanmu tentang masa lalumu, maka Kamu akan mengingatkannya tentang masa depannya

 berpikir 

Saat-saat seperti ini kugunakan untuk memaknai hari.
Kadang aku dapat mengerti, tapi kadang aku tak mengerti.
Ketika Jiwa diselimuti kegundahan, hanya kepada-Nya-lah aku dapat berserah diri.
Semoga Ridho-Nya selalu menaungi setiap jejak langkahku dalam menelusuri jalan kehidupan ini


 berpikir 

Seorang Manusia adalah cermin bagi manusia lainnya. Jika Orang lain memperlakukan kita dengan buruk, maka sesungguhnya begitu pula perlakuan kita terhadap orang lain. karena itu untuk menjadi pribadi yang baik, marilah kita senantiasa untuk intropeksi diri dan tidak langsung menyalahkan perbuatan orang lain terhadap diri kita

Cari Blog Ini