1 Keterurutan Baik dan Pembagian

1.1 Prinsip Keterurutan Baik dan Induksi Matematika

Dalam bab ini, kita menyajikan tiga alat dasar yang akan sering digunakan untuk membuktikan sifat-sifat bilangan bulat. Kita mulai dengan sebuah sifat bilangan bulat yang sangat penting, yaitu prinsip keterurutan baik. Selanjutnya, kita menyatakan apa yang dikenal sebagai prinsip sarang merpati, lalu memperkenalkan metode penting yang disebut induksi matematika.

1.1.1 Prinsip Keterurutan Baik

Definisi 1.1. Diberikan suatu himpunan bilangan $S$ (dari jenis apa pun), kita mengatakan bahwa $\ell\in S$ adalah elemen terkecil dari $S$ jika $\forall x\in S$ , berlaku $x=\ell$ atau $\ell<x$ .

Prinsip Keterurutan Baik 1.1. Setiap himpunan bilangan asli yang tidak kosong memiliki elemen terkecil.

Prinsip ini sering diambil sebagai sebuah aksioma.

1.1.2 Prinsip Sarang Merpati

Teorema 1.2. Prinsip Sarang Merpati: Misalkan $s,k\in{\mathbb N}$ memenuhi $s>k$ . Jika $s$ objek ditempatkan ke dalam $k$ kotak, maka sekurang-kurangnya satu kotak memuat lebih dari satu objek.

Bukti. Andaikan setiap kotak memuat paling banyak satu objek. Maka terdapat paling banyak $k$ objek, padahal terdapat $s$ objek dengan $s>k$ . ◻

1.1.3 Prinsip Induksi Matematika

Sekarang kita menyajikan sebuah alat berharga untuk membuktikan hasil-hasil mengenai bilangan bulat. Alat ini adalah prinsip induksi matematika.

Teorema 1.3. Prinsip Pertama Induksi Matematika: Misalkan $S\subset{\mathbb N}$ adalah himpunan yang memenuhi kedua sifat berikut:

$1\in S$ ; dan
$\forall k\in{\mathbb N},\ k\in S\Rightarrow k+1\in S$ .

Maka $S={\mathbb N}$ .
Secara lebih umum, misalkan ${\mathcal P}(n)$ adalah suatu sifat bilangan asli yang mungkin benar atau mungkin tidak benar untuk suatu $n\in{\mathbb N}$ tertentu, dan memenuhi

${\mathcal P}(1)$ benar; dan
$\forall k\in{\mathbb N},\ {\mathcal P}(k)\Rightarrow{\mathcal P}(k+1)$

maka $\forall n\in{\mathbb N}, {\mathcal P}(n)$ benar.

Bukti. Kita menggunakan prinsip keterurutan baik untuk membuktikan prinsip pertama induksi matematika ini.

Misalkan $S$ adalah himpunan pada bagian pertama teorema dan $T$ adalah himpunan bilangan asli yang tidak termasuk dalam $S$ . Kita akan menggunakan bukti dengan kontradiksi, jadi andaikan $T$ tidak kosong.

Menurut prinsip keterurutan baik, $T$ memiliki elemen terkecil $\ell$ .

Perhatikan bahwa $1\in S$ , sehingga $1\notin T$ dan akibatnya $\ell>1$ . Jadi, $\ell-1$ adalah bilangan asli. Karena $\ell$ merupakan elemen terkecil dari $T$ , maka $\ell-1$ tidak berada di $T$ ; oleh karena itu, bilangan tersebut berada di $S$ .

Namun, berdasarkan sifat yang mendefinisikan $S$ , karena $\ell-1\in S$ , kita memperoleh $\ell=\ell-1+1\in S$ . Hal ini bertentangan dengan fakta bahwa $\ell$ adalah elemen terkecil dari $T$ , sehingga berada di $T$ dan tidak berada di $S$ .

Kontradiksi ini menunjukkan bahwa anggapan bahwa $T$ tidak kosong adalah salah; dengan demikian, $S={\mathbb N}$ .

Untuk bagian kedua teorema, ambil $S=\{n\in{\mathbb N}\mid{\mathcal P}(n)\text{ benar}\}$ , lalu terapkan bagian pertama. ◻

Contoh 1.4. Kita menggunakan induksi matematika untuk menunjukkan bahwa $\forall n\in \mathbb{N}$ , $\begin{equation} \sum_{j=1}^nj=\frac{n(n+1)}{2}. \end{equation}$ Pertama, perhatikan bahwa $\begin{equation*} \sum_{j=1}^1j=1=\frac{1\cdot 2}{2} \end{equation*}$ sehingga pernyataan tersebut benar untuk $n=1$ . Untuk langkah induksi selanjutnya, andaikan rumus itu berlaku bagi suatu $n\in{\mathbb N}$ tertentu, yaitu $\sum_{j=1}^nj=\frac{n(n+1)}{2}$ . Kita tunjukkan bahwa $\begin{equation*} \sum_{j=1}^{n+1}j=\frac{(n+1)(n+2)}{2}. \end{equation*}$ Dengan demikian, bukti induksi akan lengkap. Memang, $\begin{equation*} \sum_{j=1}^{n+1}j=\sum_{j=1}^nj+(n+1)=\frac{n(n+1)}{2}+(n+1)=\frac{(n+1)(n+2)}{2}, \end{equation*}$ dan hasil yang diinginkan pun diperoleh.

Contoh 1.5. Sekarang kita menggunakan induksi matematika untuk membuktikan bahwa $n!\leq n^n$ untuk setiap $n\in{\mathbb N}$ .

Perhatikan bahwa $1!=1\leq 1^1=1$ . Selanjutnya, kita menyajikan langkah induksi. Andaikan $\begin{equation*} n!\leq n^n \end{equation*}$ untuk suatu $n\in{\mathbb N}$ . Kita buktikan bahwa $(n+1)!\leq (n+1)^{n+1}$ . Perhatikan bahwa $\begin{equation*} (n+1)!=(n+1)n!\leq (n+1)\cdot n^n<(n+1)(n+1)^{n}=(n+1)^{n+1}. \end{equation*}$ Ini melengkapi bukti.

Teorema 1.6. Prinsip Kedua Induksi Matematika:

Misalkan $S\subset{\mathbb N}$ adalah himpunan yang memenuhi kedua sifat berikut:

$1\in S$ ; dan
$\forall k\in{\mathbb N},\ 1,\dots,k\in S\Rightarrow k+1\in S$ .

Maka $S={\mathbb N}$ .
Secara lebih umum, misalkan ${\mathcal P}(n)$ adalah suatu sifat bilangan asli yang mungkin benar atau mungkin tidak benar untuk suatu $n\in{\mathbb N}$ tertentu, dan memenuhi

${\mathcal P}(1)$ benar; dan
$\forall k\in{\mathbb N},$ jika ${\mathcal P}(1),\dots,{\mathcal P}(k)$ semuanya benar, maka ${\mathcal P}(k+1)$ juga benar,

maka $\forall n\in{\mathbb N}, {\mathcal P}(n)$ benar.

Bukti. Untuk membuktikan prinsip kedua induksi, kita menggunakan prinsip pertama induksi.

Misalkan $S$ adalah himpunan bilangan bulat seperti pada bagian pertama teorema. Untuk $n\in{\mathbb N}$ , misalkan ${\mathcal P}(n)$ adalah sifat matematika “ $1,\dots,n\in S$ ”. Kita dapat menerapkan Prinsip Pertama Induksi Matematika untuk membuktikan bahwa $\forall n\in{\mathbb N}\ {\mathcal P}(n)$ benar, yang berarti $S={\mathbb N}$ . [Rinciannya diserahkan kepada pembaca.]

Bagian kedua teorema mengikuti bagian pertama dengan cara yang persis sama seperti bagian kedua Prinsip Pertama Induksi Matematika mengikuti bagian pertamanya. ◻

Latihan untuk §1.1

Latihan 1.1. Buktikan dengan induksi matematika bahwa $n<3^n$ untuk setiap bilangan bulat positif $n$ .

Latihan 1.2. Tunjukkan bahwa $\sum_{j=1}^nj^2=\frac{n(n+1)(2n+1)}{6}$ .

Latihan 1.3. Gunakan induksi matematika untuk membuktikan bahwa
$\sum_{j=1}^n(-1)^{j-1}j^2=(-1)^{n-1}n(n+1)/2$ .

Latihan 1.4. Gunakan induksi matematika untuk membuktikan bahwa $\sum_{j=1}^nj^3=[n(n+1)/2]^2$ untuk setiap bilangan bulat positif $n$ .

Latihan 1.5. Gunakan induksi matematika untuk membuktikan bahwa $\sum_{j=1}^n(2j-1)=n^2$ .

Latihan 1.6. Gunakan induksi matematika untuk membuktikan bahwa $2^n<n!$ untuk $n\geq 4$ .

Latihan 1.7. Gunakan induksi matematika untuk membuktikan bahwa $n^2<n!$ untuk $n\geq 4$ .

1.2 Operasi Aljabar pada Bilangan Bulat

Pada ${\mathbb Z}$ , himpunan bilangan bulat, terdapat dua operasi biner dasar, yaitu penjumlahan (dinotasikan dengan $+$ ) dan perkalian (dinotasikan dengan $\cdot$ ). Kedua operasi ini memenuhi sifat-sifat yang sudah dikenal berikut:

Komutativitas penjumlahan dan perkalian $\begin{align*} \forall a,b\in{\mathbb Z}:\quad a+b&=b+a\\ a\cdot b&=b\cdot a \end{align*}$
Asosiativitas penjumlahan dan perkalian $\begin{align*} \forall a,b,c\in{\mathbb Z}:\quad (a+b)+c&=a+(b+c)\\ (a\cdot b)\cdot c&= a\cdot (b\cdot c) \end{align*}$
Distributivitas perkalian terhadap penjumlahan $\forall a,b,c\in{\mathbb Z}:\quad a\cdot (b+c)=a\cdot b+a\cdot c.\$

Di dalam himpunan ${\mathbb Z}$ terdapat elemen identitas untuk kedua operasi $+$ dan $\cdot$ , masing-masing yaitu elemen $0$ dan $1$ . Elemen-elemen ini memenuhi sifat dasar $\begin{align*} \forall a\in{\mathbb Z}:\quad a + 0 &= 0+a = a\\ a\cdot 1 &= 1\cdot a = a\ . \end{align*}$

Setiap elemen dalam himpunan ${\mathbb Z}$ mempunyai invers aditif. Artinya, untuk setiap $a\in{\mathbb Z}$ terdapat bilangan bulat lain dalam ${\mathbb Z}$ , yang dinotasikan dengan $-a$ , sedemikian sehingga $\begin{equation} a+(-a)=0. \end{equation}$ Untuk perkalian, bilangan bulat yang mempunyai invers multiplikatif hanyalah $1$ dan $-1$ . Untuk kedua bilangan tersebut, invers multiplikatif yang dinotasikan dengan $a^{-1}$ atau $1/a$ sama dengan $a$ itu sendiri, sehingga $\begin{equation} a\cdot a^{-1}=1. \end{equation}$

Dari operasi penjumlahan dan perkalian, kita dapat mendefinisikan dua operasi lain pada ${\mathbb Z}$ , yaitu pengurangan (dinotasikan dengan $-$ ) dan pembagian (dinotasikan dengan $/$ ). Pengurangan merupakan operasi biner pada ${\mathbb Z}$ , yakni didefinisikan untuk setiap pasangan bilangan bulat dalam ${\mathbb Z}$ . Sebaliknya, pembagian bukan operasi biner pada ${\mathbb Z}$ sehingga hanya didefinisikan untuk pasangan bilangan bulat tertentu. Pengurangan dan pembagian didefinisikan sebagai berikut:

$\forall a,b\in{\mathbb Z}$ , $a-b$ didefinisikan sebagai $a+(-b)$ .
Diberikan $a,b\in{\mathbb Z}$ dengan $b\neq 0$ . Jika $\exists c\in{\mathbb Z}$ sedemikian sehingga $a=b\cdot c$ , maka $a/b$ didefinisikan sebagai $c$ .

1.3 Keterbagian dan Algoritma Pembagian

Sekarang kita membahas konsep keterbagian beserta sifat-sifatnya.

1.3.1 Keterbagian Bilangan Bulat

Definisi 1.7. Jika $a$ dan $b$ adalah bilangan bulat dengan $a\neq 0$ , kita mengatakan bahwa $a$ membagi $b$ dan menulis $a\mid b$ apabila terdapat bilangan bulat $k$ sedemikian sehingga $b=ka$ . Dengan kata lain, untuk $a,b\in{\mathbb Z}$ dengan $a\neq 0$ , kita menulis $a\mid b$ apabila $\exists k\in{\mathbb Z}$ sedemikian sehingga $b=ka$ .

Jika $a$ membagi $b$ , kita juga mengatakan bahwa $a$ adalah faktor [atau pembagi] dari $b$ , dan bahwa $b$ adalah kelipatan dari $a$ . Jika $a$ tidak membagi $b$ , kita menulis $a\nmid b$ .

Contoh 1.8. Sebagai contoh, $2\mid 4$ dan $7\mid 63$ , sedangkan $5\nmid 26$ .

Definisi 1.9. Untuk $a\in{\mathbb Z}$ , kita mengatakan bahwa $a$ adalah bilangan genap jika $2\mid a$ , yaitu jika $\exists k\in{\mathbb Z}$ sedemikian sehingga $a=2k$ . Sebaliknya, untuk $a\in{\mathbb Z}$ , kita mengatakan bahwa $a$ adalah bilangan ganjil jika $2\nmid a$ .

Sebagai konsekuensi dari Algoritma Pembagian di bawah ini, jika $a$ ganjil maka $\exists k\in{\mathbb Z}$ sedemikian sehingga $a=2k+1$ .

Proposisi 1.10. Untuk setiap $a\in{\mathbb Z}\setminus\{0\}$ berlaku $a\mid 0$ .

Proposisi 1.11. Jika $a,b\in{\mathbb Z}$ memenuhi $|b|<a$ dan $b\neq 0$ , maka $a\nmid b$ .

Proposisi 1.12. Untuk $a,b\in{\mathbb Z}$ dengan $a\neq 0$ , berlaku $a\mid b\Leftrightarrow a\mid|b|$ .

Teorema 1.13. Jika $a$ , $b$ , dan $c$ adalah bilangan bulat yang memenuhi $a\mid b$ dan $b\mid c$ , maka $a\mid c$ .

Bukti. Karena $a\mid b$ dan $b\mid c$ , terdapat $k_1,k_2\in{\mathbb Z}$ sedemikian sehingga $b=k_1a$ dan $c=k_2b$ . Oleh karena itu, $c=k_1k_2a$ , sehingga $a\mid c$ . ◻

Contoh 1.14. Karena $6\mid 18$ dan $18\mid 36$ , maka $6\mid 36$ .

Teorema berikut menyatakan bahwa jika suatu bilangan bulat membagi dua bilangan bulat lain, bilangan tersebut juga membagi setiap kombinasi linear keduanya.

Teorema 1.15. Untuk setiap $a,b,c,m,n\in{\mathbb Z}$ , jika $c\mid a$ dan $c\mid b$ , maka $c\mid (ma+nb)$ .

Bukti. Karena $c\mid a$ dan $c\mid b$ , terdapat $k_1,k_2\in{\mathbb Z}$ sedemikian sehingga $a=k_1c$ dan $b=k_2c$ . Dengan demikian, $\begin{equation*} ma+nb=mk_1c+nk_2c=c(mk_1+nk_2), \end{equation*}$ dan karena itu $c\mid (ma+nb)$ . ◻

Teorema 1.15 dapat diperumum ke setiap kombinasi linear berhingga sebagai berikut. Jika $\begin{equation*} n\in{\mathbb N},\ a,b_1,\dots,b_n\in{\mathbb Z}\text{\ dan\ }a\mid b_1, a\mid b_2,\dots,a\mid b_n, \end{equation*}$ maka, untuk setiap $k_1,\dots,k_n\in{\mathbb Z}$ , $\begin{equation} a\mid \sum_{j=1}^nk_jb_j \end{equation}$ Pembuktian perumuman ini dengan induksi merupakan latihan yang baik.

1.3.2 Algoritma Pembagian

Teorema 1.16. Algoritma Pembagian Diberikan $a,b\in{\mathbb Z}$ dengan $b>0$ , terdapat pasangan tunggal $q,r\in{\mathbb Z}$ sedemikian sehingga $a=qb+r$ dan $0\leq r<b$ . Bilangan $q$ disebut hasil bagi, sedangkan $r$ disebut sisa pembagian $a$ oleh $b$ .

Bukti. Perhatikan himpunan $A=\{a-bk\mid k\in{\mathbb Z},\ a-bk\geq 0\}$ . Himpunan $A$ tidak kosong karena untuk $k<a/b$ berlaku $a-bk>0$ . Menurut prinsip keterurutan baik, $A$ memiliki elemen terkecil $r=a-qb$ untuk suatu $q\in{\mathbb Z}$ . Berdasarkan konstruksinya, $r\geq 0$ . Sekarang, jika $r\geq b$ , maka (karena $b>0$ ) $\begin{equation*} r>r-b=a-qb-b=a-(q+1)b\geq 0. \end{equation*}$ Hal ini menghasilkan kontradiksi karena $r$ diasumsikan sebagai elemen terkecil $A$ . Oleh karena itu, $0\leq r<b$ .

Selanjutnya kita tunjukkan bahwa $q$ dan $r$ tunggal. Misalkan $a=q_1b+r_1$ dan $a=q_2b+r_2$ , dengan $0\leq r_1<b$ dan $0\leq r_2<b$ . Maka $\begin{equation*} a-a=q_1b+r_1-(q_2b+r_2)=(q_1-q_2)b+(r_1-r_2)=0. \end{equation*}$ Akibatnya, $\begin{equation*} (q_1-q_2)b=r_2-r_1. \end{equation*}$ Jadi, $\begin{equation*} b\mid (r_2-r_1). \end{equation*}$ Karena $0\leq|r_2-r_1|\leq\max(r_1,r_2)$ dan $b>\max(r_1,r_2)$ , maka $r_2-r_1$ harus sama dengan $0$ , yaitu $r_2=r_1$ . Karena $bq_1+r_1=bq_2+r_2$ , kita juga memperoleh $q_1=q_2$ . Hal ini membuktikan ketunggalan. ◻

Contoh 1.17. Jika $a=71$ dan $b=6$ , maka $71=6\cdot 11+5$ . Di sini $q=11$ dan $r=5$ .

Latihan untuk §1.3

Latihan 1.8. Tunjukkan bahwa $5\mid 25$ , $19\mid38$ , dan $2\mid 98$ .

Latihan 1.9. Gunakan Algoritma Pembagian untuk menentukan hasil bagi dan sisa ketika 76 dibagi oleh 13.

Latihan 1.10. Gunakan Algoritma Pembagian untuk menentukan hasil bagi dan sisa ketika -100 dibagi oleh 13.

Latihan 1.11. Tunjukkan bahwa jika $a,b,c$ , dan $d$ adalah bilangan bulat, dengan $a$ dan $c$ tidak nol, serta $a\mid b$ dan $c\mid d$ , maka $ac\mid bd$ .

Latihan 1.12. Tunjukkan bahwa jika $a$ dan $b$ adalah bilangan bulat positif dan $a\mid b$ , maka $a\leq b$ .

Latihan 1.13. Buktikan bahwa jumlah dua bilangan bulat genap adalah genap, jumlah dua bilangan bulat ganjil adalah genap, dan jumlah sebuah bilangan bulat genap dengan sebuah bilangan bulat ganjil adalah ganjil.

Latihan 1.14. Tunjukkan bahwa hasil kali dua bilangan bulat genap adalah genap, hasil kali dua bilangan bulat ganjil adalah ganjil, dan hasil kali sebuah bilangan bulat genap dengan sebuah bilangan bulat ganjil adalah genap.

Latihan 1.15. Tunjukkan bahwa jika $m$ adalah bilangan bulat, maka $3$ membagi $m^3-m$ .

Latihan 1.16. Tunjukkan bahwa kuadrat setiap bilangan bulat ganjil berbentuk $8m+1$ untuk suatu $m\in{\mathbb Z}$ .

Latihan 1.17. Tunjukkan bahwa untuk setiap bilangan bulat $n$ , kuadrat $n$ berbentuk $3m$ atau $3m+1$ untuk suatu $m\in{\mathbb Z}$ , tetapi tidak pernah berbentuk $3m+2$ untuk $m\in{\mathbb Z}$ .

Latihan 1.18. Tunjukkan bahwa jika $ac\mid bc$ , maka $a\mid b$ .

Latihan 1.19. Tunjukkan bahwa jika $a\mid b$ dan $b\mid a$ , maka $a=\pm b$ .

1.4 Representasi Bilangan Bulat dalam Berbagai Basis

Pada bagian ini, kita menunjukkan bahwa setiap bilangan bulat positif dapat dituliskan secara unik dalam ekspansi pada sebarang basis bilangan bulat yang lebih besar dari $1$ . Biasanya kita menggunakan notasi desimal untuk merepresentasikan bilangan bulat. Kita akan menunjukkan cara mengubah bilangan bulat dari notasi desimal ke notasi dengan sebarang basis bilangan bulat lain, dan sebaliknya. Notasi desimal mungkin menjadi tradisi dalam kehidupan sehari-hari semata-mata karena kita memiliki sepuluh jari tangan. (“Lalu bagaimana dengan jari kaki kita?” protes Anda. Saya tidak tahu. Dan tampaknya bangsa Babilonia memiliki $30$ jari pada setiap tangan, atau $15$ jari pada setiap tangan dan kaki, sebab mereka menggunakan basis $60$ .)

Notasi Bilangan bulat $a$ yang ditulis dalam ekspansi basis $b$ dilambangkan dengan $(a)_b$ .

Teorema 1.18. Misalkan $b\in{\mathbb Z}$ memenuhi $b>1$ . Maka, untuk setiap $m\in{\mathbb N}$ , terdapat tepat satu $l\in{\mathbb Z}_{\geq 0}$ beserta digit-digit $a_0,a_1,\dots,a_l\in{\mathbb Z}$ sedemikian sehingga $\begin{align*} m=\sum_{j=0}^{l}a_jb^j,\\ 0\leq a_j<b\text{\ untuk\ }j=0,1,\dots,l,\text{\ dan}\ \ \ \\ a_l\neq 0. \end{align*}$

Bukti. Ambil sebarang $m\in{\mathbb N}$ . Mula-mula kita membagi $m$ dengan $b$ menggunakan Algoritma Pembagian, sehingga diperoleh $\begin{equation*} m=q_0b+a_0, \ \ \ 0\leq a_0 <b. \end{equation*}$ Jika $q_0\neq 0$ , selanjutnya kita membagi $q_0$ dengan $b$ dan memperoleh $\begin{equation*} q_0=q_1b+a_1, \ \ \ 0\leq a_1<b. \end{equation*}$ Jika $q_0=0$ , ambil $l=0$ dan $a_0=m$ ; bagian eksistensi selesai. Selanjutnya, anggap $q_0>0$ . Karena setiap hasil bagi positif berikutnya lebih kecil daripada hasil bagi sebelumnya, untuk suatu $l\geq1$ proses ini pertama kali berakhir pada $q_l=0$ . Dengan demikian, $\begin{align*} q_{j-1}&=q_jb+a_j, \qquad 0\leq a_j<b \quad (j=1,\dots,l),\\ q_l&=0, \qquad a_l=q_{l-1}\neq0. \end{align*}$

Sekarang, dengan menyubstitusikan persamaan $q_0=q_1b+a_1$ ke dalam $m=q_0b+a_0$ , diperoleh $\begin{equation*} m=(q_1b+a_1)b+a_0=q_1b^2+a_1b+a_0. \end{equation*}$ Dengan menyubstitusikan persamaan-persamaan tersebut secara berturut-turut (atau dengan induksi pada $j$ ), diperoleh $\begin{align*} m&=q_{j-1}b^j+\sum_{i=0}^{j-1}a_ib^i \qquad (j=1,\dots,l),\\ &=a_lb^l+\sum_{i=0}^{l-1}a_ib^i =\sum_{i=0}^{l}a_ib^i. \end{align*}$ Yang masih harus dibuktikan ialah bahwa representasi tersebut tunggal. Sekarang misalkan $\begin{equation*} m=\sum_{i=0}^{l}a_ib^i=\sum_{i=0}^{s}c_ib^i. \end{equation*}$ Ambil $L=\max\{l,s\}$ dan tambahkan koefisien nol pada ekspansi yang lebih pendek. Dengan mengurangkan kedua ekspansi tersebut, diperoleh $\begin{equation*} \sum_{i=0}^{L}(a_i-c_i)b^i=0. \end{equation*}$ Jika kedua ekspansi berbeda, ambil indeks terkecil $0\leq j\leq L$ sedemikian sehingga $c_j\neq a_j$ . Semua suku berindeks lebih kecil daripada $j$ lenyap, sehingga diperoleh $\begin{equation*} b^j\sum_{i=j}^{L}(a_i-c_i)b^{i-j}=0, \end{equation*}$ dan karena $b\neq 0$ , diperoleh $\begin{equation*} \sum_{i=j}^{L}(a_i-c_i)b^{i-j}=0. \end{equation*}$ Oleh karena itu, $\begin{equation*} a_j-c_j=-b\sum_{i=j+1}^{L}(a_i-c_i)b^{i-j-1}, \end{equation*}$ sehingga $b\mid (a_j-c_j)$ . Karena $0\leq a_j<b$ dan $0\leq c_j<b$ , berlaku $|a_j-c_j|<b$ . Dengan demikian, $a_j=c_j$ . Ini bertentangan dengan pemilihan $j$ , sehingga ekspansi tersebut tunggal. ◻

Definisi 1.19. Misalkan $b\in{\mathbb Z}$ memenuhi $b>1$ . Untuk $m\in{\mathbb N}$ , misalkan $\ell\in{\mathbb Z}_{\geq 0}$ dan $a_0,a_1,\dots,a_\ell\in{\mathbb Z}$ sebagaimana dalam teorema di atas (1.18). Maka representasi basis $b$ dari $m$ adalah rangkaian digit $(m)_b=a_\ell\dots a_1a_0$ . Jika $b\ge10$ , kita sering menggunakan simbol tunggal lain untuk merepresentasikan nilai-nilai $a_i$ yang mungkin, dari $10$ sampai $b-1$ . Sebagai contoh, $\begin{align*} 10&\leftrightsquigarrow A\\ 11&\leftrightsquigarrow B\\ 12&\leftrightsquigarrow C\\ &\text{dst.} \end{align*}$ Representasi bilangan bulat dalam basis 2 disebut representasi biner. Representasi biner berguna bagi komputer: semua koefisien $a_0,\dots,a_\ell$ dalam representasi biner memenuhi $0\leq a_j<2$ , sehingga nilainya 0 atau 1. Jadi, untuk merepresentasikan bilangan bulat melalui $\ell+1$ kawat, setiap kawat dapat diberi tegangan (1) atau tidak (0). (Istilah bit berasal dari frasa bahasa Inggris binary digit, yang berarti “digit biner”.)

Pemrogram komputer juga sering menggunakan basis 8 dan basis 16, yang masing-masing disebut oktal dan heksadesimal, atau heks. Bangsa Babilonia menggunakan basis $60$ , yang disebut seksagesimal.

Contoh 1.20. Untuk mencari ekspansi basis 3 dari 214, kita melakukan pembagian berikut: $\begin{align*} 214&=3\cdot 71+1\\ 71&= 3\cdot 23+2\\ 23&= 3\cdot 7+2\\ 7&= 3\cdot 2+1\\ 2&= 3\cdot 0+2\\ \end{align*}$ Untuk memperoleh ekspansi basis 3 dari 214, kita membaca sisa-sisa pembagian tersebut dari bawah ke atas, sehingga $(214)_{10}=(21221)_3$ .

Contoh 1.21. Untuk mencari ekspansi basis $10$ , yaitu ekspansi desimal, dari $(364)_7$ , kita menghitung $4\cdot 7^0+6\cdot 7^1+3\cdot 7^2=4+42+147=193$ .

1.4.1 Latihan untuk §1.4

Latihan 1.20. Ubah $(7482)_{10}$ ke notasi basis 6.

Latihan 1.21. Ubah $(98156)_{10}$ ke notasi basis 8.

Latihan 1.22. Ubah $(101011101)_2$ ke notasi desimal.

Latihan 1.23. Ubah $(AB6C7D)_{16}$ ke notasi desimal.

Latihan 1.24. Ubah $(9A0B)_{16}$ ke notasi biner.

1.5 Faktor Persekutuan Terbesar

Pada bagian ini kita mendefinisikan faktor persekutuan terbesar (FPB) dari dua bilangan bulat dan membahas sifat-sifatnya. Kita juga membuktikan bahwa FPB dua bilangan bulat merupakan kombinasi linear dari kedua bilangan tersebut.

Jika dua bilangan bulat $a$ dan $b$ tidak keduanya $0$ , setidaknya salah satunya taknol dan hanya mempunyai berhingga banyak pembagi (lihat Latihan 1.12). Karena itu, $a$ dan $b$ hanya mempunyai berhingga banyak pembagi bersama. Pada bagian ini kita membahas pembagi terbesar di antara pembagi-pembagi bersama tersebut.

Definisi 1.22. Untuk $a,b\in{\mathbb Z}$ yang tidak keduanya nol, faktor persekutuan terbesar adalah bilangan bulat terbesar yang membagi $a$ sekaligus $b$ , dan ditulis $\gcd(a,b)$ (atau kadang-kadang cukup $(a,b)$ ).

Jika hal ini menyederhanakan suatu rumus, kita menetapkan $\gcd(0,0)=0$ .

Contoh 1.23. Faktor persekutuan terbesar dari 24 dan 18 adalah 6. Dengan kata lain, $\gcd(24,18)=6$ .

Definisi 1.24. Bilangan $a,b\in{\mathbb Z}$ disebut relatif prima jika $\gcd(a,b)=1$ .

Contoh 1.25. Faktor persekutuan terbesar dari 9 dan 16 adalah 1; jadi, kedua bilangan tersebut relatif prima.

Perhatikan bahwa setiap bilangan bulat mempunyai pembagi positif dan negatif. Jika $a$ adalah pembagi positif dari $m$ , maka $-a$ juga merupakan pembagi dari $m$ . Karena itu, dari definisi faktor persekutuan terbesar terlihat bahwa $\gcd(a,b)=\gcd(|a|, |b|)$ .

Kita dapat menggunakan FPB dua bilangan bulat untuk membentuk bilangan-bilangan yang relatif prima:

Teorema 1.26. Jika $a,b\in{\mathbb Z}$ tidak keduanya nol dan $\gcd(a,b)=d$ , maka
$\gcd(a/d,b/d)=1$ .

Bukti. Ambil $a,b\in{\mathbb Z}$ . Kita akan menunjukkan bahwa $a/d$ dan $b/d$ tidak mempunyai pembagi bersama positif selain $1$ . Misalkan $k\in{\mathbb N}$ membagi $a/d$ sekaligus $b/d$ . Maka $\exists m,n\in{\mathbb Z}$ sedemikian sehingga $\begin{equation*} a/d=km \hspace{0.3cm}\mbox{dan} \ \ b/d=kn \end{equation*}$ Dengan demikian, $\begin{equation*} a=kmd \hspace{0.3cm}\mbox{dan} \ \ b=knd. \end{equation*}$ Jadi, $kd$ merupakan pembagi bersama dari $a$ dan $b$ . Selain itu, $kd\geq d$ . Namun, $d$ adalah faktor persekutuan terbesar dari $a$ dan $b$ , sehingga $kd\leq d$ . Oleh karena itu, $k=1$ . ◻

Teorema berikut menunjukkan bahwa faktor persekutuan terbesar dari dua bilangan bulat tidak berubah ketika suatu kelipatan dari salah satunya ditambahkan pada bilangan yang lain.

Teorema 1.27. Misalkan $a,b,c\in{\mathbb Z}$ . Maka $\gcd(a,b)=\gcd(a+cb,b)$ .

Bukti. Kita akan menunjukkan bahwa setiap pembagi bersama dari $a$ dan $b$ juga merupakan pembagi bersama dari $a+cb$ dan $b$ , demikian pula sebaliknya. Jadi, kedua pasangan itu mempunyai himpunan pembagi bersama yang persis sama. Karena itu, faktor persekutuan terbesar dari $a$ dan $b$ juga menjadi faktor persekutuan terbesar dari $a+cb$ dan $b$ . Misalkan $k$ adalah pembagi bersama dari $a$ dan $b$ . Menurut Teorema 1.15, $k \mid (a+cb)$ , sehingga $k$ membagi $a+cb$ . Sekarang misalkan $l$ adalah pembagi bersama dari $a+cb$ dan $b$ . Sekali lagi, menurut Teorema 1.15, $\begin{equation*} l\mid ((a+cb)-cb)=a. \end{equation*}$ Jadi, $l$ merupakan pembagi bersama dari $a$ dan $b$ , dan hasil yang dimaksud pun terbukti. ◻

Contoh 1.28. Perhatikan bahwa $\gcd(4,14)=\gcd(4,14-3\cdot 4)=\gcd(4,2)=2$ .

Sekarang kita menyajikan teorema yang membuktikan bahwa faktor persekutuan terbesar dari dua bilangan bulat dapat ditulis sebagai kombinasi linear dari kedua bilangan tersebut.

Teorema 1.29.

Misalkan $a,b\in{\mathbb Z}$ tidak keduanya nol. Maka $\gcd(a,b)$ adalah bilangan asli terkecil yang berbentuk $d=ma+nb$ untuk suatu $m,n\in{\mathbb Z}$ .

Bukti. Dengan mengganti $a$ dan $b$ masing-masing oleh $|a|$ dan $|b|$ serta menyerap tandanya ke dalam koefisien, tanpa mengurangi keumuman kita dapat menganggap $a,b\geq 0$ dan tidak keduanya nol. Tinjau himpunan $\begin{equation*} S=\{d\in{\mathbb N}\mid d=ma+nb\text{\ untuk suatu\ }m,n\in{\mathbb Z}\}\ . \end{equation*}$ $S$ tidak kosong karena setidaknya salah satu dari $a$ dan $b$ positif. Jika $a>0$ , maka $a=1\cdot a+0\cdot b\in S$ ; jika $b>0$ , maka $b=0\cdot a+1\cdot b\in S$ . Misalkan $d\in{\mathbb N}$ adalah elemen terkecil dari $S$ ; keberadaannya dijamin oleh Prinsip Keterurutan Baik. Karena $d\in S$ , terdapat $m,n\in{\mathbb Z}$ sedemikian sehingga $d=ma+nb$ . Kita masih harus membuktikan bahwa $d$ membagi $a$ sekaligus $b$ dan bahwa $d$ adalah pembagi bersama terbesar dengan sifat tersebut.

Menurut Algoritma Pembagian, $\exists q,r\in{\mathbb Z}$ sedemikian sehingga $\begin{equation*} a=qd+r, \ \ \ 0\leq r<d. \end{equation*}$ Dengan demikian, $\begin{equation*} r=a-qd=a-q(ma+nb)=(1-qm)a-qnb. \end{equation*}$ Jadi, $r$ merupakan kombinasi linear dari $a$ dan $b$ . Karena $0\leq r<d$ dan $d$ adalah bilangan bulat positif terkecil yang merupakan kombinasi linear dari $a$ dan $b$ , haruslah $r=0$ , sehingga $a=qd$ . Jadi, $d\mid a$ .

Argumen yang sama menunjukkan bahwa $d\mid b$ .

Sekarang, misalkan $c$ membagi $a$ sekaligus $b$ . Menurut Teorema 1.15, $c$ membagi setiap kombinasi linear dari $a$ dan $b$ . Jadi, $c\mid d$ . Hal ini membuktikan bahwa setiap pembagi bersama dari $a$ dan $b$ membagi $d$ . Karena itu, $c\leq d$ , dan $d$ adalah faktor persekutuan terbesar. ◻

Berikut suatu penerapan sederhana yang akan sangat berguna kelak:

Akibat 1.30. Jika $a,b\in{\mathbb Z}$ relatif prima, maka $\exists m,n\in{\mathbb Z}$ sedemikian sehingga $ma+nb=1$ .

Definisi 1.31. Untuk suatu $n\in{\mathbb N}$ , misalkan $a_1,a_2,\dots,a_n\in{\mathbb Z}$ tidak semuanya $0$ . Faktor persekutuan terbesar dari bilangan-bilangan tersebut adalah bilangan bulat terbesar yang membagi semuanya, dan dilambangkan dengan $\gcd(a_1,\dots,a_n)$ .

Definisi 1.32. Untuk suatu $n\in{\mathbb N}$ , bilangan-bilangan $a_1,a_2,\dots,a_n\in{\mathbb Z}$ disebut relatif prima secara bersama-sama jika $\gcd(a_1,a_2,\dots,a_n)=1$ .

Contoh 1.33. Bilangan-bilangan bulat $3, 6, 7$ relatif prima secara bersama-sama karena $(3,6,7)=1$ , meskipun $(3,6)=3$ .

Definisi 1.34. Untuk suatu $n\in{\mathbb N}$ , bilangan-bilangan $a_1,a_2,\dots,a_n\in{\mathbb Z}$ disebut relatif prima berpasangan jika $\forall i,j\in{\mathbb N}$ dengan $i\le n$ , $j\le n$ , dan $i\neq j$ , berlaku $\gcd(a_i,a_j)=1$ .

Contoh 1.35. Bilangan-bilangan bulat $3,14,25$ relatif prima berpasangan. Perhatikan pula bahwa bilangan-bilangan tersebut relatif prima secara bersama-sama.

Proposisi 1.36. Untuk $n\in{\mathbb N}$ dengan $n\geq 2$ dan $a_1,\dots,a_n\in{\mathbb Z}$ , jika $a_1,a_2,\dots,a_n$ relatif prima berpasangan, maka bilangan-bilangan tersebut relatif prima secara bersama-sama.

Latihan untuk §1.5

Latihan 1.25. Tentukan faktor persekutuan terbesar dari 15 dan 35.

Latihan 1.26. Tentukan faktor persekutuan terbesar dari 100 dan 104.

Latihan 1.27. Tentukan faktor persekutuan terbesar dari -30 dan 95.

Latihan 1.28. Misalkan $m\in{\mathbb N}$ . Tentukan faktor persekutuan terbesar dari $m$ dan $m+1$ .

Latihan 1.29. Misalkan $m\in{\mathbb N}$ . Tentukan faktor persekutuan terbesar dari $m$ dan $m+2$ .

Latihan 1.30. Tunjukkan bahwa jika $m,n\in{\mathbb Z}$ memenuhi $\gcd(m,n)=1$ , maka $\gcd(m+n,m-n)=1$ atau $2$ .

Latihan 1.31. Tunjukkan bahwa jika $m\in{\mathbb N}$ , maka $3m+2$ dan $5m+3$ relatif prima.

Latihan 1.32. Tunjukkan bahwa jika $a,b\in{\mathbb Z}$ relatif prima, maka $\gcd(a+2b,2a+b)=1$ atau $3$ .

Latihan 1.33. Tunjukkan bahwa jika $a_1,a_2,\dots,a_n\in{\mathbb Z}$ tidak semuanya $0$ dan $c\in{\mathbb N}$ , maka

$\gcd(ca_1,ca_2,\dots,ca_n)=c\cdot\gcd(a_1,a_2,\dots,a_n).$

1.6 Algoritma Euklides

Pada bagian ini kita menjelaskan metode sistematis untuk menentukan faktor persekutuan terbesar dari dua bilangan bulat. Metode ini berasal dari Euklides dan karena itu disebut Algoritma Euklides.

Lema 1.37. Jika $a,b,q,r\in{\mathbb Z}$ dan $a=qb+r$ , maka $\gcd(a,b)=\gcd(r,b)$ .

Bukti. Menurut sifat invariansi FPB terhadap penambahan kelipatan yang dibuktikan pada bagian sebelumnya, $\gcd(bq+r,b)=\gcd(b,r)$ . ◻

Sekarang kita beralih ke bentuk umum Algoritma Euklides. Pada dasarnya, algoritma ini menyatakan bahwa faktor persekutuan terbesar dari dua bilangan bulat adalah sisa taknol terakhir dalam pembagian berulang.

Teorema 1.38. Misalkan $a,b\in{\mathbb N}$ dan $a\geq b$ . Tetapkan $r_0=a$ , $r_1=b$ , $s_0=1$ , $s_1=0$ , $t_0=0$ , dan $t_1=1$ . Terapkan Algoritma Pembagian secara berulang: selama $r_{j+1}\neq 0$ , tentukan $q_{j+1}\in{\mathbb N}$ dan $r_{j+2}\in{\mathbb Z}_{\geq 0}$ sedemikian sehingga $r_j=r_{j+1}q_{j+1}+r_{j+2}$ dan $0\leq r_{j+2}<r_{j+1}$ . Berhentilah pada indeks $n$ yang memenuhi $r_n>0$ dan $r_{n+1}=0$ . Pada setiap langkah, tetapkan $s_{j+2}=s_j-q_{j+1}s_{j+1}$ dan $t_{j+2}=t_j-q_{j+1}t_{j+1}$ . Maka $\gcd(a,b)=r_n=s_na+t_nb$ .

Bukti. Dengan menerapkan Algoritma Pembagian, diperoleh $\begin{align*} r_j&=q_{j+1}r_{j+1}+r_{j+2}, &&0\leq r_{j+2}<r_{j+1}\quad (j=0,1,\dots,n-1). \end{align*}$ Proses ini akhirnya menghasilkan sisa $0$ , sebab selama sisanya taknol, sisa-sisa tersebut membentuk barisan menurun ketat dari bilangan bulat taknegatif. Menurut Lema 1.37, $\begin{equation*} \gcd(a,b)=\gcd(r_0,r_1)=\gcd(r_n,r_{n+1})=\gcd(r_n,0)=r_n. \end{equation*}$ ◻

Versi lengkap teorema ini, yang menyertakan $s_j$ dan $t_j$ , disebut Algoritma Euklides diperluas, sedangkan versi yang lebih sederhana tanpa koefisien-koefisien tersebut disebut Algoritma Euklides.

Pembaca yang teliti akan melihat bahwa kita belum membuktikan klaim bahwa $s_j$ dan $t_j$ dapat digunakan untuk menuliskan FPB sebagai kombinasi linear dari $a$ dan $b$ . Bukti tersebut diserahkan sebagai latihan di bawah ini.

Contoh 1.39. Kita akan menentukan faktor persekutuan terbesar dari $4147$ dan $10672$ . Perhatikan bahwa $\begin{align*} 10672&=4147\cdot 2+2378,\\ 4147&=2378\cdot 1+1769,\\ 2378&=1769\cdot 1+609,\\ 1769&=609\cdot 2 +551,\\ 609&=551\cdot 1+58, \\ 551&=58\cdot 9+ 29,\\ 58&=29\cdot 2,\\ \end{align*}$ Jadi, $\gcd(4147,10672)=29$ .

Latihan untuk §1.6

Latihan 1.34. Gunakan Algoritma Euklides untuk menentukan faktor persekutuan terbesar dari 412 dan 32, lalu nyatakan hasilnya sebagai kombinasi linear kedua bilangan tersebut.

Latihan 1.35. Gunakan Algoritma Euklides untuk menentukan faktor persekutuan terbesar dari 780 dan 150, lalu nyatakan hasilnya sebagai kombinasi linear kedua bilangan tersebut.

Latihan 1.36. Tentukan faktor persekutuan terbesar dari $70,98,108$ .

Latihan 1.37. Misalkan $a,b\in{\mathbb N}$ genap. Buktikan bahwa $\gcd(a,b)=2\gcd(a/2,b/2)$ .

Latihan 1.38. Tunjukkan bahwa jika $a\in{\mathbb N}$ genap dan $b\in{\mathbb N}$ ganjil, maka $\gcd(a,b)=\gcd(a/2,b)$ .

Latihan 1.39. Buktikan klaim mengenai koefisien dalam Algoritma Euklides diperluas.