Teori Bilangan 2

Materi ini membahas lima teknik penting dalam soal olimpiade: mengurai bilangan menjadi faktor prima, membandingkan faktor melalui FPB dan KPK, menghitung FPB secara efisien dengan Algoritma Euclid, menentukan solusi bilangan bulat pada persamaan Diophantine, serta menganalisis sisa pembagian menggunakan kekongruenan.

Peta Materi

1. Faktorisasi prima
2. FPB dan KPK
3. Algoritma Euclid
4. Persamaan Diophantine
5. Sisa pembagian dan kekongruenan

1. Faktorisasi Prima

Faktorisasi prima adalah menyatakan suatu bilangan bulat lebih dari 1 sebagai hasil kali bilangan-bilangan prima. Bentuk ini tunggal, kecuali urutan faktornya, dan disebut Teorema Dasar Aritmetika.

Jika $n = p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k}$, maka setiap $p_i$ adalah bilangan prima. Faktorisasi prima membantu menemukan banyak faktor, faktor terbesar, dan pola pembagian suatu bilangan.

Jika $n=p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k}$, banyak faktor positif $n$ adalah

$$ (a_1+1)(a_2+1)\cdots(a_k+1). $$

Contoh 1

Tentukan bilangan positif terkecil yang memiliki tepat 24 faktor positif dan habis dibagi 90.

Penyelesaian:

Karena $90=2\cdot3^2\cdot5$, bilangan tersebut berbentuk $n=2^a3^b5^c\cdots$ dengan $a\ge1$, $b\ge2$, dan $c\ge1$. Banyak faktornya 24.

Coba pola eksponen yang hasilnya 24: $24=4\cdot3\cdot2$. Agar bilangan minimum, eksponen terbesar dipasangkan dengan prima terkecil. Dengan syarat pembagian 90, pilihan minimum adalah $2^3\cdot3^2\cdot5^1$.

$$ 2^3\cdot3^2\cdot5=8\cdot9\cdot5=360. $$

Banyak faktor $360$ adalah $(3+1)(2+1)(1+1)=24$. Jadi jawabannya adalah 360.

Contoh 2

Diketahui $N=2^a3^b5^c$ memiliki 36 faktor positif dan merupakan kuadrat sempurna. Jika $N$ adalah bilangan terkecil yang memenuhi syarat, tentukan $N$.

Penyelesaian:

Kuadrat sempurna mengharuskan $a,b,c$ genap. Selain itu,

$$ (a+1)(b+1)(c+1)=36. $$

Karena $a,b,c$ genap, maka $a+1,b+1,c+1$ semuanya ganjil. Satu-satunya pemfaktoran 36 menjadi tiga bilangan ganjil adalah $1\cdot3\cdot12$ tidak mungkin karena 12 genap, atau $1\cdot1\cdot36$ juga tidak mungkin. Jadi tidak ada $N$ berbentuk $2^a3^b5^c$ dengan ketiga pangkat positif yang memenuhi.

Namun pangkat boleh nol. Pilihan terkecil adalah pola $(a+1,b+1,c+1)=(9,1,4)$, sehingga $(a,b,c)=(8,0,3)$, tetapi $c=3$ ganjil. Pola $(6,6,1)$ juga memiliki faktor genap. Tidak ada solusi karena hasil kali tiga bilangan ganjil tidak mungkin sama dengan 36. Jadi tidak ada bilangan $N$ yang memenuhi syarat tersebut.

2. FPB dan KPK

FPB dari beberapa bilangan adalah bilangan positif terbesar yang membagi semuanya. KPK adalah bilangan positif terkecil yang merupakan kelipatan semua bilangan tersebut.

Jika

$ a=\prod p^{\alpha_p},\qquad b=\prod p^{\beta_p}, $

maka

$ \operatorname{FPB}(a,b)=\prod p^{\min(\alpha_p,\beta_p)},\qquad \operatorname{KPK}(a,b)=\prod p^{\max(\alpha_p,\beta_p)}. $

Cara membaca lambang $\prod$

Lambang $\prod$ disebut pi besar atau notasi hasil kali. Lambang ini berarti semua faktor yang ditunjukkan dikalikan bersama-sama. Jadi,

$ \prod p^{\alpha_p} $

dibaca: “hasil kali $p$ berpangkat $\alpha_p$ untuk semua bilangan prima $p$ yang muncul dalam faktorisasi.”

Sebagai contoh, jika $a=2^3\cdot3^2\cdot5$, maka dapat ditulis

$ a=\prod_{p\in{2,3,5}}p^{\alpha_p} =2^3\cdot3^2\cdot5^1. $

Indeks di bawah $\prod$, yaitu $p\in{2,3,5}$, menjelaskan faktor mana saja yang harus dikalikan. Pangkat $\alpha_p$ menyatakan banyaknya faktor prima $p$ dalam faktorisasi $a$. Jika tidak ada indeks yang ditulis, seperti pada rumus FPB dan KPK di atas, konteksnya dipahami sebagai semua bilangan prima yang relevan.

Dengan demikian, rumus

$ \operatorname{FPB}(a,b)=\prod p^{\min(\alpha_p,\beta_p)} $

dibaca: “FPB dari $a$ dan $b$ sama dengan hasil kali semua bilangan prima $p$, masing-masing dipangkatkan dengan nilai terkecil antara $\alpha_p$ dan $\beta_p$.”

Sedangkan rumus

$ \operatorname{KPK}(a,b)=\prod p^{\max(\alpha_p,\beta_p)} $

dibaca: “KPK dari $a$ dan $b$ sama dengan hasil kali semua bilangan prima $p$, masing-masing dipangkatkan dengan nilai terbesar antara $\alpha_p$ dan $\beta_p$.”

Untuk dua bilangan positif berlaku $ab=\operatorname{FPB}(a,b)\cdot\operatorname{KPK}(a,b)$.

Contoh 1

Dua bilangan positif memiliki FPB 12 dan KPK 420. Jika jumlah kedua bilangan itu disunting ? Tentukan semua kemungkinan pasangan bilangan tersebut jika jumlahnya 144.

Penyelesaian:

Misalkan kedua bilangan $12x$ dan $12y$ dengan $\operatorname{FPB}(x,y)=1$. Karena KPK-nya 420,

$$ 12xy=420\Rightarrow xy=35. $$

Pasangan faktor koprima dari 35 adalah $(1,35)$ dan $(5,7)$. Jumlah pasangan bilangan:

• $(12,420)$ jumlah 432;
• $(60,84)$ jumlah 144.

Jadi satu-satunya pasangan dengan jumlah 144 adalah 60 dan 84.

Contoh 2

Tentukan bilangan positif terkecil $n$ sehingga $\operatorname{FPB}(n,180)=12$ dan $\operatorname{KPK}(n,180)=1260$.

Penyelesaian:

Gunakan $n\cdot180=12\cdot1260$, sehingga

$$ n=\frac{12\cdot1260}{180}=84. $$

Pengecekan: $\operatorname{FPB}(84,180)=12$ dan $\operatorname{KPK}(84,180)=1260$. Jadi $n=84$.

3. Algoritma Euclid

Algoritma Euclid menghitung FPB dengan memanfaatkan sifat

$$ \operatorname{FPB}(a,b)=\operatorname{FPB}(b,a\bmod b),\qquad a>b. $$

Lakukan pembagian bersisa berulang sampai sisanya 0. Sisa tak nol terakhir adalah FPB.

Contoh 1

Tentukan FPB dari 2026 dan 867 menggunakan Algoritma Euclid.

Penyelesaian:

$$ 2026=2(867)+292, $$ $$ 867=2(292)+283, $$ $$ 292=1(283)+9, $$ $$ 283=31(9)+4, $$ $$ 9=2(4)+1, $$ $$ 4=4(1)+0. $$

Sisa tak nol terakhir adalah 1, jadi $\operatorname{FPB}(2026,867)=1$.

Contoh 2

Tentukan semua bilangan bulat positif $n<100$ yang memenuhi $\operatorname{FPB}(n,84)=12$.

Penyelesaian:

Syarat FPB 12 mengharuskan $n=12k$ dan $\operatorname{FPB}(k,7)=1$. Karena $n<100$, maka $1\le k\le8$. Nilai $k$ yang tidak habis dibagi 7 adalah $1,2,3,4,5,6,8$.

Maka bilangan-bilangannya adalah

$$ \boxed{12,24,36,48,60,72,96}. $$

4. Persamaan Diophantine

Persamaan Diophantine adalah persamaan yang dicari solusinya dalam bilangan bulat. Untuk

$$ ax+by=c, $$

solusi bilangan bulat ada jika dan hanya jika $\operatorname{FPB}(a,b)$ membagi $c$.

Jika $(x_0,y_0)$ adalah satu solusi dan $d=\operatorname{FPB}(a,b)$, semua solusi diberikan oleh

$$ x=x_0+\frac{b}{d}t,\qquad y=y_0-\frac{a}{d}t, $$

dengan $t$ bilangan bulat. Syarat tambahan seperti $x,y>0$ digunakan untuk memilih solusi yang sah.

Contoh 1

Sebuah toko menjual paket A seharga Rp7.000 dan paket B seharga Rp11.000. Seseorang membayar tepat Rp100.000. Tentukan semua kemungkinan banyak paket A dan B yang dibeli, dengan keduanya minimal satu paket.

Penyelesaian:

Persamaannya $7x+11y=100$, dengan $x,y\ge1$. Modulo 7:

$$ 11y\equiv100\pmod7\Rightarrow4y\equiv2\pmod7. $$

Invers 4 modulo 7 adalah 2, sehingga $y\equiv4\pmod7$. Karena $11y<100$, maka $y=4$ atau $y=11$; hanya $y=4$ yang mungkin. Diperoleh

$$ x=\frac{100-44}{7}=8. $$

Jadi satu-satunya kemungkinan adalah 8 paket A dan 4 paket B.

Contoh 2

Tentukan semua pasangan bilangan bulat positif $(x,y)$ yang memenuhi $15x+21y=150$.

Penyelesaian:

Bagi 3:

$$ 5x+7y=50. $$

Modulo 5 menghasilkan $2y\equiv0\pmod5$, jadi $y\equiv0\pmod5$. Karena $y>0$ dan $7y<50$, maka $y=5$. Akibatnya,

$$ x=\frac{50-35}{5}=3. $$

Jadi pasangan positifnya adalah $(x,y)=(3,5)$.

5. Sisa Pembagian dan Kekongruenan

Notasi $a\equiv b\pmod m$ berarti $m$ membagi $a-b$. Dengan kekongruenan, bilangan besar dapat diganti dengan sisa baginya.

Aturan penting:

$$ a\equiv b\pmod m\Rightarrow a+c\equiv b+c\pmod m, $$ $$ a\equiv b\pmod m\Rightarrow ac\equiv bc\pmod m. $$

Untuk pangkat besar, cari pola sisa atau gunakan siklus. Hati-hati: pembagian atau pencoretan dalam modulo hanya sah jika faktor yang dicoret relatif prima terhadap modulus.

Contoh 1

Tentukan tiga angka terakhir dari $7^{2026}$.

Penyelesaian:

Kita bekerja modulo 1000. Karena $7^4=2401\equiv401$ dan pola dapat dihitung melalui pemangkatan cepat:

$$ 7^{10}=282475249\equiv249\pmod{1000}, $$ $$ 7^{20}\equiv249^2=62001\equiv1\pmod{1000}. $$

Karena $2026=20(101)+6$, maka

$$ 7^{2026}\equiv7^6=117649\equiv649\pmod{1000}. $$

Tiga angka terakhir adalah 649.

Contoh 2

Tentukan sisa pembagian $2^{100}+3^{100}$ oleh 7.

Penyelesaian:

Pola pangkat 2 modulo 7 adalah $2,4,1$ dan berulang setiap 3. Karena $100\equiv1\pmod3$,

$$ 2^{100}\equiv2\pmod7. $$

Pola pangkat 3 modulo 7 adalah $3,2,6,4,5,1$ dan berulang setiap 6. Karena $100\equiv4\pmod6$,

$$ 3^{100}\equiv3^4=81\equiv4\pmod7. $$

Jadi

$$ 2^{100}+3^{100}\equiv2+4=6\pmod7. $$

Sisanya adalah 6.

Strategi Umum Menyelesaikan Soal

1. Uraikan bilangan menjadi faktor prima jika soal membahas faktor, FPB, atau KPK.
2. Gunakan Algoritma Euclid untuk FPB bilangan besar.
3. Periksa syarat keterbagian sebelum mencari solusi persamaan Diophantine.
4. Gunakan modulo yang paling menguntungkan, terutama modulo salah satu koefisien.
5. Untuk pangkat besar, cari siklus sisa sebelum menghitung.
6. Selalu substitusikan kembali jawaban untuk memeriksa kebenarannya.