Faktorisasi bilangan bulat dan kekongruenan

Faktorisasi Bilangan Bulat

1.1.   Bilangan Prima

1.1.1. Defenisi Bilangan Prima

Bilangan bulat p > 1 dikatakan prima jika ia hanya mempunyai pembagi p dan 1. Dengan kata lain bilangan prima tidak mempunyai pembagi selain dari 1 dan dirinya sendiri. Berdasarkan definisi ini, 1 bukanlah bilangan prima. Bilangan prima terkecil adalah 2 yang merupakan bilangan genap. Sedangkan bilangan prima lainnya, seperti 3; 5; 7; 11; …. semuanya bilangan ganjil. Ingat, sebaliknya bilangan ganjil belum tentu prima; misalnya 9 ganjil tapi bukan prima. Bilangan bukan prima seperti 4; 6; 8; 9;…. disebut bilangan komposit. Bila n komposit maka ia dapat dinyatakan sebagai n = ab dimana a; b 2 Z; 1 < a < n; 1 < b < n.

Sebelum membahas teorema tentang bilangan prima, terlebih dahulu dijelaskan istilah saling prima. Dua buah bilangan dikatakan saling prima jika faktor persekutuan terbesar (FPB) dari dua bilangan tersebut adalah 1. Istilah lain dari saling prima adalah komprima atau prima relatif. Jadi defenisi saling prima dapat dituliskan sebagai berikut.

“Dua bilangan bulat a dan b dikatakan prima relatif, jika (a,b)=1”

Apabila (a,b )=1 maka  juga dikatakan saling prima. Bilangan bulat positif  dikatakan saling prima dua-dua atau saling prima sepasang, apabila (ai,bj)=1, untuk setiap i=1, 2, 3,…., n dan j=1, 2, 3,…., n  dengan i j, maka dikatakan bahwa bilangan bulat positif a₁,a_2,a₃,…,a_n saling prima dua dua atau saling prima sepasang demi sepasang.

Contoh:

·         (7, 8, 15)=1,sehingga dikatakan bahwa 7, 8 dan 15 saling prima dan sekaligus saling prima dua-dua, sebab (7,8)=(7,15)=(8,15)=1.

·         (4, 6, 9, 10) =1 menunjukkan bahwa 4, 6, 9 dan 10 saling prima, tetapi tidak saling prima dua-dua, sebab (4,6)=2, (4,10)=2, (6,9)=3, (6,10)=2 meskipun (4,9)=(9,10)=1.

Teorema 1.1.1.2 “Setiap bilangan bulat positif yang lebih besar atau sama dengan 2 dapat dinyatakan sebagi perkalian lebih atau satu bilangan prima”

Bentuk: n =

Contoh:

90        = 2.3.3.5

            = 2¹ .3² .5¹

Teorema 1.1.1.3 “Jika n > 1, maka n dapat dibagi oleh paling sedikit satu bilangan prima”

Bukti:  Karena n > 1, maka dipunyai paling sedikit satu pembagi > 1. Berdasarkan Prinsip Terurut Baik, n pasti mempunyai paling sedikit satu pembagi positif yang lebih besar dari 1, misalnya q. Diklaim bahwa q adalah prima. Jika q bukan prima maka dapat dituliskan q = ab, 1 < a  b < q. Ini berarti bahwa a adalah suatu pembagi dari n yang lebih besar dari 1 dan lebih kecil dari q. Timbul kontradiksi dengan kenyataan

bahwa q adalah minimal.

Contoh:

n = 30, untuk pencari pembaginya bias menggunbakan pohon faktor.

Dari pohon faktor disamping, dapat dilihat pembagi dari 30 adalah 2,3,5 dimana 2,3,5 merupakan bilangan prima. Maka dari pembuktian diatas dapat dilihat a adalah 2 dan q  adalah 5.

Teorema  1.1.1.4. “Jika n suatu bilangan komposit, maka n memiliki faktor k dengan 1<k ”

Bukti:

Karena n suatu bilangan komposit, ada bilangan-bilangan bulat positif k dan m sedemikian sehingga km=n dengan 1<k<n dan 1<m<n.

Apabila k dan m kedua-duanya lebih besar dari , yaitu k>  dan m> , maka n=km> =n(n>n).

Hal ini tidak mungkin sehingga salah satu dari k atau m harus lebih kecil atau sama dengan , misalnya k, yaitu 1<k . Jadi, n memiliki faktor k dengan 1<k .

Kontraposisi teorema 4.

Apabila bilangan bulat positif n tidak mempunyai faktor k dengan 1<k , maka n adalah suatu bilangan prima.

Contoh:

Apakah 1003 merupakan bilangan prima atau bukan?

Penyelesaian:

Bilangan 1003 diperiksa keterbagiannya oleh bilangan-bilangan prima yang kurang dari  1003 yaitu 2, 3, 5, 7, 11, 13, 17, 19, 23, 29 dan 31. Karena terdapat bilangan yang dapat membagi habis 1003 yaitu 17 maka 1003 adalaah bilangan komposit.

1.2.         Faktorisasi Tunggal

Telah diketahui bahwa setiap bilangan bulat positif yang lebih besar dari 1 dapat dinyatakan sebagai perkalian dari bilangan-bilangan prima tertentu. Dapat dikatakan bahwa setiap bilangan bulat positif yang lebih dari 1 dapat dinyatakan sebagai perkalian bilangan bilangan prima tertentu. Pada sesi ini akan dipelajari bahwa pemaktoran suatu bilangan bulat positif atas faktor faktor prima adalah tunggal, sehingga kita mengenalnya sebagai faktorisasi tunggal, kita akan mempelajari beberapa teorema sebagai persiapan untuk mempelajari faktorisasi tunggal.

Teorema 1.2.1.. (Euclid) “Terdapat tak hingga banyak bilangan prima”

Bukti:  Diandaikan terdapat berhingga banyak bilangan prima, misalnya p1, p2, ..., pn.

Diambil N = p1,p2…pn + 1. Bilangan bulat N adalah lebih besar dari 1, sehingga berdasarkan teorema sebelumnya diperoleh bahwa N pasti mempunyai suatu pembagi prima p. Bilangan prima p haruslah salah satu dari bilangan-bilangan p1, p2, ..., pn. Tetapi, diamati bahwa p pasti berbeda dari sembarang p1, p2, ..., pn karena N mempunyai sisa 1 ketika dibagi oleh sembarang pi. Jadi timbul kontradiksi.

Contoh:

6 adalah bilangan prima pertama jika dikalikan dan ditambahkan satu maka:

2x3x5x7x11x13+1 = 30031

Ternyata 30031 bukan bilangan prima, tetapi 30031 habis dibagi oleh 59 dan 509 yang merupakan bilangan prima.

Teorema 1.2.2.

 "jika p suatu bilangan prima dan p | ab, maka p|a atau p|b”

Bukti :

Karena p suatu bilangan prima,maka untuk sembarang bilangan bulat a berlaku (a,p) = 1 atau (a,p) = p.

Jika (a,p) = 1 dan p |ab, kita pernah membuktikan bahwa p|b. buktikanlah kembali! Dan jika (a,p) = p maka p|a.

Contoh :

3|6.3        dimana   p =3 , a = 6 , dan c = 3.

Maka p|a 3|6

Atau p|b 3|3

  

                                                        Kekongruenan

2.1.   Defenisi 1

Jika m suatu bilangan bulat positif, maka a kongruen dengan b modulo m [ditulis a ≡ b(mod m)], bila m membagi (a-b). Jika m tidak membagi (a-b) maka dikatakan bahwa a tidak kongruen dengan b modulo m [ditulis a  b (mod m)].

Contoh:

·         25 ≡ 1 ( mod 4)

sebab (a-b) terbagi oleh m, (25-1) = 24 terbagi oleh 4.

·         47 8 (mod 8)

Sebab (a-b) tidak terbagi oleh m, (47-8) = 39 tidak terbagi oleh 8.

Teorema 2.1.1.  “a ≡ b (mod m) jika dan hanya jika ada bilangan bulat k sehingga a = mk + b”

Bukti: a ≡ b (mod m)

akan ditunjukkan bahwa: a = mk + b

Dari defenisi 1 diatas didapat bahwa:

a ≡ b (mod m), jika dan hanya jika m|(a-b).

Karena m|(a-b), maka m > 0

karena m|(a-b), maka ada bilangan bulat k, sehingga (a-b) = mk

Contoh :

Jika 25 ≡ 4 (mod 7) maka ada bilangan bulat k = 3.

yaitu    25-4 = 7k

21 = 7.3

Jadi a ≡ b (mod m), bila dan hanya bila a-b = mk, untuk setiap bilangan bulat k.

Karena a-b = mk sama artinya dengan a = mk + b,

Atau dengan kata lain:

a ≡ b (mod m) jika dan hanya jika a = mk + b.

Maka: 25 ≡ 4 (mod 7), sama artinya dengan 25 = 7.3 + 4, dimana k = 3

Teorema 2.1.2. “Setiap bilangan bulat kongruen modulo m dengan tepat satu diantara 0,1,2,3,...,(m-1)”

Bukti:

a ≡ b (mod m) jika dan hanya jika ada bilangan bulat k sehingga a=mk+b. Jika a dan m bilangan bulat dan m>0, maka ia dinyatakan sebagai a=mq+r dengan 0 ≤ r < m. Ini berarti bahwa a-r=mq, yaitu a ≡ r (mod m). Karena 0 ≤ r < m, maka ada m buah pilihan untuk r, yaitu 0,1,2,3....,(m-1). Jadi setiap bilangan bulat akan kongruen modulo m dengan tepat satu diantara 0,1,2,3,....,(m-1).

Contoh:

·         27 ≡ r (mod 6), tentukan r, jika 0 ≤ r < 6.

Karena 0 ≤ r < 6, maka pilihan untuk r tepat satu diantara 0,1,2,3,4,5,6. Yaitu 3.

·         12 ≡ 2 (mod 5) karena 2 adalah sisian terkecil dari 12 modulo 5

2.2.    Defenisi 2

Jika a ≡ r (mod m) dengan 0 ≤ r < m, maka r disebut residu terkecil dari a modulo m. Untuk kekongruenan residu terkecil ini, {0,1,2,3,...,(m-1)} disebut himpunan residu terkecil modulo m.

Contoh:

·         Residu terkecil dari 71 modulo 2 adalah 1, sebab sisa dari 71:2 adalah 1.

·         Himpunan residu terkecil dari modulo 5 adalah {0.1,2,3,4}.

Himpunan residu terkecil dari modulo 9 adalah {0.1,2,3,...,9}.

Himpunan residu terkecil dari modulo 24 adalah {0.1,2,3,...,23}.

Kita dapat melihat relasi kekongruenan itu dengan cara yang lain, seperti teorema berikut ini:

Teorema 2.2.1. “a ≡ b (mod m) jika dan hanya jika a dan b memiliki sisa yang sama jika dibagi m”

Bukti :

Akan dibuktikan dari dua sisi,

Pertama,

jika a ≡ b (mod m), maka akan ditunjukkan bahwa a dan b memiliki sisa yang sama jika dibagi m.

Karena a ≡ b (mod m), maka a ≡ r (mod m) dan b ≡ r (mod m), dengan r adalah residu terkecil modulo m atau 0 ≤ r < m. Selanjutnya,

a ≡ r (mod m), berarti a = mq + r, dan

b ≡ r (mod m), berarti b = mt + r, untuk suatu bilangan bulat q dan t, sehingga dapat disimpulkan bahwa a dan b memiliki sisa yang sama jika dibagi m. (Terbukti!)

Kedua,

jika a dan b memiliki sisa yang sama, maka akan ditunjukkan a ≡ b (mod m).

Misalkan:

a memiliki sisa r jika dibagi m, berarti a ≡ mq + r, dan

b memiliki sisa r jika dibagi m, berarti b ≡ mt + r, untuk suatu bilangan bulat q dan t,

dari kedua persamaan ini diperoleh :

(a-b) = (mq – mt) + (r-r)

(a-b) = m(q – t)

Dari kedua persamaan diperoleh bahwa a-b=m(q-t) berarti m | (a-b) atau a ≡ b (mod m).

Perhatikan bahwa berdasarkan teorema yang telah dibahas, ungkapan berikut mempunyai arti yang sama, yaitu:

 n ≡ 7(mod 8)

 n ≡ 7 + 8k

 n dibagi 8 bersisa 7.

Contoh:

10  ≡ (mod 4) maka nilai n nya adalah 10, untuk itu:

10 ≡ 4k + m maka 10 dibagi 4 bersisa 2, jadi nilai m adalah 2.

2.3.    Defenisi 3

Himpunan bilangan bulat r1,r2,r3,.....,rm disebut sistem sisaan lengkap modulo m jika dan hanya jika setiap bilangan bulat adalah kongruen modulo m dengan satu dan hanya satu diantara r1,r2,r3,.....,atau rm.

Contoh:

·         Himpunan {45,-9,12,-22,23,24} adalah sistem residu lengkap dari modulo 5, dapat diperiksa bahwa :

45≡ 0(mod 5)

-9 ≡1(mod 5)

12≡2(mod 5)

-22≡2(mod 5)

23≡ 3(mod 5)

24≡ 4(mod 5)

·         Himpunan  {11,12,13,14,15} adalah suatu sistem residu (sisaan) lengkap modulo 5, dapat diperiksa bahwa:

 11≡ 1 (mod 5)

12 ≡2 (mod 5)

13 ≡ 3 (mod 5)

14 ≡ 4 (mod 5)

15 ≡ 5 (mod 5).

2.4.    Relasi Ekuivalensi

Apakah relasi Kekongruenan Modulo suatu bilangan bulat merupakan relasi ekuivalensi atau tidak ?

Untuk menjawab pertanyaan diatas, simaklah uraian-uraian berikut!

Kekongruenan modulo suatu bilangan bulat positif adalah relasi antara bilangan-bilangan bulat. suatu relasi disebut relasi ekuivalensi jika relasi itu memiliki sifat reflektif, simetris, dan transitif.

Sekarang akan ditunjukkan bahwa relasi kekongruenan itu merupakan relasi ekuivalensi.

Perhatikan !

Jika m, a, b, dan c adalah bilangan-bilangan bulat dengan m positif, maka :

a. a ≡ a (mod m), sifat reflektif

b. Jika a ≡ b (mod m), maka b ≡ a (mod m), sifat simetris.

c. Jika a ≡ b (mod m) dan b ≡ c (mod m), maka a ≡ c (mod m), sifat transitif.

Bukti :

a. Karena a-a = 0.m, maka a ≡ a (mod m).

b. Jika a ≡ b (mod m), maka a-b = k.m, sehingga b-a = (-k).m, yang berarti bahwa b ≡  a (mod m).

c. a ≡ b (mod m), berarti a-b = p.m

b ≡ c (mod m), berarti b-c = q.m

untuk suatu bilangan bulat p dan q, jika kedua persamaan tersebut kita jumlahkan, maka diperoleh:

a-c = (p+q).m

karena p dan q adalah bilangan-bilangan bulat, maka (p + q) bilangan bulat, sehingga

a ≡ c (mod m).

Karena relasi “≡” (kekongruenan) pada himpunan bilangan bulat memenuhi ketiga sifat tersebut, yaitu reflekti, simetris, dan transitif, maka relasi “≡” (kekongruenan) pada himpunan bilangan bulat merupakan relasi ekuivalensi.

(terbukti!).

Karena relasi kekongruenan pada bilangan bulat merupakan relasi ekuivalensi, maka akibatnya himpunan bilangan bulat pada kongruen modulo m ini terpartisi menjadi himpunan-himpunan bagian yang setiap himpunan bagian disebut kelas.

Contoh :

Misalnya kita memperhatikan himpunan bilangan bulat dengan relasi kekongruenan modulo 5, maka dengan relasi ini himpunan bagian bilangan bulat terpatisi (terbagi menjadi himpunan-himpunan bagian yang saling asing, dan gabungannya sama dengan himpunan bilangan bulat) menjadi 5 kelas, yaitu :

[0] = {...,-10,-5,0,5,10,...}

[1] = {...,-9,-4,1,6,11,....}

[2] = {...,-8,-3,2,7,12,....}

[3] = {...,-7,-2,3,8,13,....}

[4] = {...,-6,-1,4,9,14,....}

Keterangan :

Pemberian nama untuk suatu kelas menggunakan nama salah satu anggota kelas tersebut, yang dibubuhi tanda “garis diatasnya”, atau dengan menggunakan tanda “kurung persegi”, seperti contoh diatas.

Relasi kekongruenan mempunyai kemiripan sifat dengan persamaan, sebab relasi kekongruenan dapat dinyatakan sebagai persamaan, yaitu a ≡ b (mod m) sama artinya dengan a = b + km, untuk suatu bilangan bulat k.

Misalnya :

1. Jika a ≡ b (mod m), maka (a + c) ≡ (b + c) (mod m), untuk setiap bilangan bulat c.

2. Jika a ≡ b (mod m), maka ac ≡ bc (mod m), untuk setiap bilangan bulat c.

Bukti :

1)      Jika a ≡ b (mod m), berarti a-b = p.m, atau

a = pm + b, untuk setiap bilangan bulat p, selanjutnya,

jika masing-masing ruas ditambahkan dengan bilangan bulat c, maka diperoleh :

a + c = pm + b + c

atau,

(a + c) - (b + c)= p.m

Yang berarti bahwa:

(a + c) ≡ (b + c) (mod m).......(Terbukti !)

Contoh :

Jika 15 ≡ 3 (mod 4), maka :

·         17 ≡ 5 (mod 4),

sebab 15 + 2 = 17, dan 3 + 2 = 5

·         21 ≡ 9 (mod 4),

Sebab  15 + 6 = 21, dan 3 + 6 = 9

·         116 ≡ 104 (mod 4),

sebab  15 + 101 = 116, dan 3 + 101 = 104.

Dan seterusnya.

2)      Jika a ≡ b (mod m), berarti a-b = p.m untuk setiap bilangan bulat p selanjutnya,

jika masing-masing ruas dikalikan dengan bilangan bulat c, maka diperoleh :

c(a - b) = c.p.m

atau,

ac – bc = cp.m

karena c dan p masing-masing adalah bilangan bulat, maka c.p juga merupakan suatu bilangan bulat, sehingga diperoleh bahwa :

ac ≡ bc (mod m)....(Terbukti !)

contoh :

Jika 10 ≡ 2 (mod 4), Maka :

50 ≡ 10 (mod 4),

Sebab 10.5 = 50, dan 2.5 = 10

 120 ≡ 24 (mod 4),

Sebab 10.12 =120, dam 2.12 = 24

 Dan seterusnya.

Teorema 2.4.1 ”Jika a ≡ b (mod m), dan c ≡ d (mod m), maka ( a + c) ≡ (b + d) (mod m)”

Bukti :

Jika a ≡ b (mod m), dan c ≡ d (mod m), akan dibuktikan bahwa ( a + c) ≡ (b + d) (mod m).

Kareana a ≡ b (mod m), berarti a = s.m + b, untuk suatu bilangan bulat s.

Karena c ≡ d (mod m), berarti c = t.m + d, untuk suatu bilangan bulat s.

Jika kedua persamaan tersebut dijumlahkan, maka diperoleh bahwa :

(a + c) = (sm + tm) + (b + d)

(a + c) = m(s + t) + (b + d)

(a + c) - (b + d) = m.(s + t)

Hal ini berarti bahwa :

a + c) ≡ (b + d) (mod m)

(Terbukti!)

Contoh :

Jika 20 ≡ 2 (mod 6), dan 25 ≡ 1 (mod 6),

maka 45 ≡ 3 (mod 6), sebab 20 + 25 = 45, dan 2 + 1 = 3.

Teorema 2.4.2. “Jika a ≡ b (mod m), dan c ≡ d (mod m), maka ax + cy ≡ bx + dy (mod m), untuk setiap bilangan bulat x dan y”

Bukti :

a ≡ b (mod m), berarti a = m.s + b,untuk suatu bilangan bulat s.

c ≡ d (mod m), berarti c = m.t + d, untuk suatu bilagan bulat t.

Jika kedua ruas persamaan pertama dikalikan dengan x, dan kedua ruas persamaan kedua dikalikan dengan y, maka diperoleh :

ax = msx + bx

cy = mty + dy

Dengan menjumlahkan kedua persamaan ini, maka diperoleh bahwa :

ax + cy = (msx + mty) + (bx + dy)

ax + cy = m(sx + ty) + (bx + dy)

(ax + cy) -  (bx + dy) = m(sx + ty)

persamaan terakhir ini berarti bahwa :

m | (ax + cy) -  (bx + dy)

sehingga :

(ax + cy) ≡ (bx + dy) (mod m).

(Terbukti !)

Contoh :

Jika 21 ≡ 1 (mod 4), dan 16 ≡ 2 (mod 7), maka

(21.3        + 16.4) ≡ (1.3 + 2.4) (mod 7)

(64 + 63) ≡ (3 + 8) (mod 7)

127  ≡ 11 (mod 7).

Teorema 2.4.3 “jika ac bc (mod m) dengan (c,m)=1, maka a b (mod m)”

Bukti:

ac bc (mod m) berarti m|(ac-bc) atau m|c(a-b) dengan (c,m)=1, maka m|(a-b) berarti a b (mod m)

Contoh:

Tentukan bilangan-bilangan bulat y yang memenuhi perkongruenan 3y 1 (mod m)

Jawab:

Karena 1 15 (mod 7), maka kita dapat mengganti 1 pada perkongruenan tersebut dengan 15, sehingga diperoleh 3y  15 (mod 7). Selanjutnya, karena (3,7) =1, maka kita dapat membagi 3 pada ruas-ruas perkongruenan itu, sehingga di peroleh y  5 (mod 7). Perkongruenan terakhir ini berarti y=5+7k untuk setiap bilangan bulat k atau dapat dikatakan bahwa himpunan penyelesaian dari perkongruenan tersebut adalah{5+7k|k bilangan bulat}.

2.5.   Sifat Kanselasi (Penghapusan)

Pada persamaan / kesamaan bilangan bulat berlaku sifat kanselasi (penghapusan), yaitu :

Misalkan a,b,dan c bilangan bulat, jika ab = ac, dengan a ≠ 0, maka b = c.

Contoh :

Jika 3.x = 3.6, maka x = 6

Apakakah pada kekongruenan berlaku sifat yang mirip dengan sifat kanselasi (penghapusan) tersebut ?

Misalkan :

jika ab ≡ ac (mod m), dengan a ≠ 0

apakah b ≡ c (mod m) ?

ambil sebuah contoh :

24 ≡ 12 (mod 4)

3.8 ≡ 3.4 (mod 4)

8 ≡ 4 (mod 4)

Akan tetepi, bagaimana dengan contoh berikut :

24 ≡ 12 (mod 4)

2.12 ≡ 2.6 (mod 4)

Apakah 12 ≡ 6 (mod 4)? Jelas tidak, karena 4 tidak membagi (12 – 6)

Dari kedua contoh diatas, dapat disimpulkan bahwa walaupun sifat kanselasi (penghapusan) tidak berlaku sepenuhnya pada relasi kekongruenan, tetapi akan berlaku jika memenuhi syarat seperti yang dinyatakan dalam teorema berikut :

Teorema 2.5.1. “Jika ac ≡ bc (mod m) dengan (c,m) = d,maka a ≡ b (mod m/d)”

Bukti :

ac ≡ bc (mod m) berarti m | (ac – bc) atau m| c(a – b), maka m/d | c/d (a-b).

Karena d FPB dari c dan m, maka m/d dan c/d adalah bilangan-bilangan bulat.

Karena (c,m) = d, maka (c/d , m/d) = 1.

Karena (c/d , m/d) = 1, dan m/d | c/d (a-b),maka :

m/d |(a-b)

berarti a ≡ b (mod m/d)

(Terbukti !)

Contoh :

Tentukan x yang memenuhi 2x ≡ 4 (mod 6)

Jawab

2x ≡ 2.2 (mod 6), karena (2,6) = 2,

maka : x ≡ 2 (mod 3)

atau,

x = 3k + 2, untuk setiap bilangan bulat k.

jadi nilai-nilai x adalah {3k + 2}, atau dapat dikatakan bahwa himpunan penyelesaian dari pengkongruenan itu adalah {3k + 2 | k bilangan bulat}.

2.6.   Aplikasi Kekongruenan

Kekongruenan bilangan bulat yang sering di aplikasikan adalah kekongruenan madulo 9. Kekongruenan modulo 9 dapat digunakan untuk memeriksa kebenaran terhadap operasi aritmetika yaitu penjumlahan, pengurangan, perkalian, dan pembagian pada bilangan bulat. Perhatikan penjelasan berikut ini:

Misalnya, diketahui bahwa :

10.000-1          = 9.999 = 9 k4 sehingga  10.000 = 1(mod 9)

1.000-1            =999 = 9 k3    sehingga  1.000 = 1(mod 9)

100-1               = 99 = 9 k2      sehingga  100 = 1(mod 9)

 10-1                = 9 = 9 k1        sehingga  10 = 1(mod 9)

Berikut menunjukkan bahwa setiap bilangan bulat kongruen modulo 9 dengan jumlah angka-angkanya.

12345 ≡ {10000 + 2000 + 300 + 40 + 5} (mod 9)

            ≡ {1(10000) + 2(1000) + 3(100) + 4(10) + 5} (mod 9)

            ≡  {1(1) + 2(1) + 3(1) + 4(1) + 5} (mod 9)

            ≡  15 (mod 9)

selanjutnya dengan cara yang sama

15 ≡ {10 + 5} (mod 9)

     ≡ {1 + 5} (mod 9)

     ≡ 6 (mod 9)

Jadi 12345 ≡ 6 (mod 9)

Berdasarkan penjelasan yang telah diuraikan di atas, maka dapat diturunkan menjadi teorema sebagai berikut.

Teorema 4.1.1 “10_­ⁿ ≡ 1 (mod 9) untuk n = 0,1,2,3 …”

Bukti :

10ⁿ – 1 = 999 … 9 (sebanyak n kali, dengan syarat semua angkanya 9)

10ⁿ  = 1 (mod 9)

Teorema 4.2. “Setiap bilangan bulat kongruen modulo 9 dengan jumlah angka-angkanya”

Bukti:

Ambil sembarang bilangan bulat n yang angka-angkanya secara berturut-turut adalah :

n = d_kd_k-₁d_k-2  .... d₂d₁d₀ atau

n = d_k10^k+ d_k-1 10^k-1 + d_k-2 10^k-2+....+ d₂ 10² + d₁10 +d₀

dengan  0 d_i   9 untuk i = 0,1,2,..., k dan d_k

Contoh :

Periksalah kebenaran penjumlahan berikut ini dengn prinsip diatas.

248 + 324 + 627 = 1244

Jawab :

248 ≡ 2 + 4 + 8 (mod 9)

≡ 14 (mod 9)

≡ 5 (mod 9)

324 ≡ 3 + 2 + 4 (mod 9)

≡ 9 (mod 9)

≡ 0 (mod 9)

627 ≡ 6 + 2 + 7 (mod 9)

≡ 15 (mod 9)

≡ 6 (mod 9)

Jadi, 248 + 324 + 627 ≡ 5 + 0 + 6 (mod 9)

≡ 11 (mod 9)

≡ 2 (mod 9) ……………….. (i)

Sedangkan 1244 ≡ 1 + 2 + 4 + 4 (mod 9)

≡ 11(mod 9)

≡ 2 (mod 9) ………………. (ii)

Dari kekongruenan (i) dan (ii) berarti : 248 + 324 + 627 = 1244 (benar)

Jika a ≡ b (mod m) dan c ≡ d (mod m) maka ac ≡ bd (mod m)

Contoh :

Untuk yang terbagi 9,

10+11=30

Kita mengetahui bahwa 10 + 11 ≡ 3 (mod 9) dan 30 ≡ 3 (mod 9)

Menurut cara pemeriksaan diatas 10 + 11 = 30 benar.

Tetapi kita mengetahui bahwa 10 +11 = 30 salah

Selain itu kekongruenan modulo 9 digunakan untuk menguji keterbagian suatu bilangan bulat oleh 9. Suatu bilangan terbagi oleh 9 apabila dan hanya bila sisa pembagian itu nol.

n ≡ a (mod 9) apabila dan hanya apabila n dan a masing-masing mempunyai sisa yang sama jika dibagi 9. Jadi, jika n ≡ a (mod 9) maka n terbagi oleh 9, apabila dan hanya apabila terbagi oleh 9. Padahal n kongruen modulo 9 dengan jumlah angka-angkanya.

Jadi, suatu bilangan terbagi oleh 9 apabila dan hanya apabila jumlah angka-angkanya terbagi oleh 9.

Contoh :

(i)     7587 ≡ 7 + 5 + 8 + 7 ≡ 27 ≡ 9 (mod 9)

Karena 9│9 maka 9 │7587

(ii)   47623 ≡ 4 + 7 + 6 + 2 + 3 ≡ 22 ≡ 4 (mod 9)

Karena 9│4 maka 9 │4762