Contoh Soal/Penyelesaian Teorema Fermat ( Teori Bilangan )

Teorema Fermat & Teorema Wilson

Ambil p bilangan prima, bila p ∤ a atau ( a,p ) = 1 maka ap-1 = 1 ( mod p ).

Bukti :

1. Misal { 1, 2, 3, . . , ( p-1 )} sistem residu direduksi modulo p
2. Bentuk { a,2 a,3 a, … ( p-1 ) a } maka juga merupakan sistem residu direduksi modulo p sebab ( a, p ) = 1
3. Pasangkan sistem elemen dari { 1, 2, 3, .., ( p-1 )} dengan satu dan hanya satu elemen dari { a, 2a, 3a,… ( p-1 ) a } sedemikian sehingga i ≡ ja ( mod p ) untuk i = 1, 2, 3.. ( p–1 ) dan j = 1, 2, 3,..( p–1 )
4. Gandakan elemen-elemen { 1, 2, 3, .., ( p-1 )} demikian juga {a, 2a, 3a, … ( p-1 ) a} sehingga didapat :
{ 1, 2, 3, .., ( p-1 )} ≡ { a, 2a, 3a, … ( p-1 ) a} ( mod p )
ap -1 ( 1, 2, 3, .., ( p-1 )) ≡ ( 1, 2, 3, .., ( p-1 )) ( mod p )
= ap -1 ( p-1 )! ≡ ( p-1 )!( mod p )

Karena  {( p-1 ), p = 1 } maka ap -1 ≡ 1 ( mod p )

Contoh Soal :

1. Berapa sisa pembagian 5²⁸ oleh 11 ?
Penyelesaian :

5²⁸ ≡ 1 ( mod 11 )

≡ ( 5¹⁰ )² ( 5² )⁴ ( mod 11 ) 

≡ ( 5¹⁰ )² ( 254 ) ( mod 11 )

≡ ( 1 ) ( 34 ) ( mod 11 )

≡ 81 ( mod 11 )

≡ 4 ( mod 11 )

∴5³⁸ dibagi 11 bersisa 4

2. Tentukan sisa pembagian 6²⁰¹⁸ oleh 13
Penyelesaian :

6²⁰¹⁸ ( mod 13 )

( 6¹² )¹⁶⁸⁺²  ( mod 13 )

≡6² ( mod 13 )

= 36 ( mod 13 )

10 ( mod 13 )

∴ sisanya 10

3. Hitunglah sisanya jika 7²⁰¹³ dibagi 41
Penyelesaian :

( 7⁴⁰ )⁵⁰ 7¹³ ( mod 41 )

1.7¹³ ( mod 41 )

( 7² )² 7⁹ ( mod 41 )

82 7⁹ ( mod 41 )

64 .7⁹ ( mod 41 )

23 ( 72 )4 7 ( mod 41 )

23 ( 8 )4 7 ( mod 41 )

23 ( 64 ) ( 64 )7 ( mod 41 )

23.23.23.7 ( mod 41 )

12167 ( mod 41 )

≡14 ( mod 41 )

∴sisanya 14

4. Tunjukkan bahwa 3¹⁰⁵ + 4¹⁰⁵ habis dibagi oleh 7 
Penyelesaian :

3¹⁰⁵ + 4¹⁰⁵ ( mod 7 )

= 3¹⁰⁵ + ( 7-3 )¹⁰⁵ ( mod 7 )

= 3¹⁰⁵ + ( -3 )¹⁰⁵ ( mod 7 )

= 0 ( mod 7 )