Materi Olimpiade SMP : Bab 4 Teori Bilangan [Basic] : Pembagian Bersisa dan Kongruensi

Materi sebelumnya : Materi Olimpiade SMP : Bab 3 Teori Bilangan [Basic] : FPB, KPK, dan Algoritma Pembagian

Sebelum melangkah lebih jauh, terlebih dahulu saya akan menjelaskan definisi dari kongruensi terlebih dahulu

Misalkan $a, b$, dan $m$ bilangan bulat dengan $m > 0$. Bilangan $a$ disebut kongruen dengan $b$ modulo $m$ jika $m|(a - b)$ atau biasany ditulis dengan $a \equiv b \pmod{m}$

Contoh :
$481 \equiv 1 \pmod{12}$ karena $12|(481 - 1)$
$-6 \equiv 18 \pmod{12}$ karena $12|(-6 - 18)$

Berikut adalah teorema - teorema yang sering dijumpai pada kongruensi

Teorema 1
Jika $a \equiv b \pmod{m}$, maka untuk setiap bilangan bulat $c$ berlaku
(1) $a + c \equiv b + c \pmod{m}$
(2) $ac \equiv bc \pmod{m}$

Teorema 2
Jika $a \equiv \pmod{m}$ dan $c \equiv d \pmod{m}$, maka
(1) $a + c \equiv b + d \pmod{m}$
(2) $ac \equiv bd \pmod{m}$

Teorema 3
Jika $a, b, d$ dan $m$ bilangan yang memenuhi $ca \equiv cb \pmod{m}$ dan $\text{FPB}(c, m) = 1$, maka $a \equiv b \pmod{m}$

Teorema 4
Jika $a, b, d$ dan $m$ bilangan yang memenuhi $ca \equiv cb \pmod{m}$ dan $c|m$, maka $a \equiv b \pmod{\frac{m}{c}}$

Teorema 5
Jika $a \equiv b \pmod{m}$, maka $a^n \equiv b^n \pmod{m}$ untuk semua bilangan asli $n$


Untuk lebih jelasnya, berikut saya sajikan contoh soal beserta dengan pembahasannya

Soal 1
Diberikan bahwa $N = 2013 \times 2014 + 2014 \times 2015 + 2015 \times 2016$.
(a) Tentukan apakah $N$ bilangan ganjil atau genap
(b) Tentukan angka satuan pada $N$
(c) Tentukan sisa pembagian $N$ oleh $7$

Solusi
(a) Perhatikan bahwa kita cukup melihat $N$ sebagai bilangan ganjil atau genap dengan memandang $N$ dalam kongruen $2$. Sebagai contoh, perhatikan bahwa

$2013 \equiv 1 \pmod{2}$ dan $2014 \equiv 0 \pmod{2}$. Dengan menggunakan Teorema 2 bagian (b) diperoleh bahwa $2013 \times 2014 \equiv 1 \times 0 \pmod{2} \equiv 0 \pmod{2}$. Oleh karena itu

$2013 \times 2014 + 2014 \times 2015 + 2015 \times 2016 \equiv 1 \times 0 + 0 \times 1 + 1 \times 0 \pmod{2}$
$\equiv 0 \pmod{2}$

Jadi $2| (N - 0)$ yang berarti $N$ adalah bilangan genap


(b) Untuk mencari satuan, kita cukup melakukan perhitungan dalam modulo $10$, begitu pula dengan puluhan menggunakan modulo $100$, dst. Oleh karena itu

$2013 \times 2014 + 2014 \times 2015 + 2015 \times 2016 \equiv 3 \times 4 + 4 \times 5 + 5 \times 6 \pmod{10}$
$\equiv 62 \pmod{10} \equiv 2 \pmod{10}$

Jadi, satuan dari $N$ adalah $2$


(c) Dengan munggunakan modulo $8$ diperoleh bahwa

$2013 \times 2014 + 2014 \times 2015 + 2015 \times 2016 \equiv 5 \times 6 + 6 \times 7 + 7 \times 8 \pmod{8}$
$\equiv 128 \pmod{8} \equiv 0 \pmod{8}$

Jadi, sisa pembagian $N$ oleh $8$ adalah $0$


Soal 2
Buktikan bahwa untuk setiap bilangan bulat $n$, bilangan $n^3 - n$ habis dibagi $3$

Solusi
Perhatikan bahwa ada $3$ kemungkinan nilai dari $n$

• Jika $n \equiv 0 \pmod{3}$ maka $n^3 - n \equiv 0^3 - 0 \pmod{3} \equiv 0 \pmod{3}$.
• Jika $n \equiv 1 \pmod{3}$ maka $n^3 - n \equiv 1^3 - 1 \pmod{3} \equiv 0 \pmod{3}$. 
• Jika $n \equiv 2 \pmod{3}$ maka $n^3 - n \equiv 2^3 - 2 \pmod{3} \equiv 0 \pmod{3}$. 

Karena untuk semua kasus mengahasilkan $n^3 - n \equiv 0 \pmod{3}$, jadi benar bahwa $n^3 - n$ habis dibagi $3$ untuk setiap bilangan bulat $n$.


Soal 3
Buktikan bahwa $49^n - 36^n$ habis dibagi $13$

Solusi
Perhatikan bahwa $49 \equiv 36 \pmod{13}$. Dengan menggunakan teorema $5$ diperoleh bahwa $49^n \equiv 36^n \pmod{13}$, artinya dengan menggunakan definisi kongruensi adalah $13|49^n - 36^n$. Terbukti


Soal 4
Tentukan semua bilangan asli $n$ agar $2^n + 1$ habis dibagi $3$

Solusi
Perhatikan bahwa $2^n + 1 \equiv (-1)^n + 1 \pmod{3}$. Akan dibagi menjadi 2 kasus :

• Jika $n$ genap, maka $2^n + 1 \equiv (-1)^n + 1 \pmod{3} \equiv 2 \pmod{3}$. Hal ini berarti, untuk $n$ genap, $2^n + 1$ tidak habis dibagi $3$
• Jika $n$ ganjil, maka $2^n + 1 \equiv (-1)^n + 1 \pmod{3} \equiv 0 \pmod{3}$. Hal ini berarti, untuk $n$ ganjil, $2^n + 1$ habis dibagi $3$

Jadi, bilangan asli $n$ yang memenuhi agar $2^n + 1$ habis dibagi $3$ adalah bilangan ganjil


Soal 5
Buktikan bahwa untuk setiap bilangan ganjil $n$ berlaku $8|n^2 - 1$

Solusi
Perhatikan bahwa ada $4$ kemungkinan nilai dari $n$ ketiga dibagi dengan $8$

• Jika $n \equiv 1 \pmod{8}$ maka $n^2 - 1 \equiv 1^2 - 1 \pmod{8} \equiv 0 \pmod{8}$
• Jika $n \equiv 3 \pmod{8}$ maka $n^2 - 1 \equiv 3^2 - 1 \pmod{8} \equiv 0 \pmod{8}$
• Jika $n \equiv 5 \pmod{8}$ maka $n^2 - 1 \equiv 5^2 - 1 \pmod{8} \equiv 0 \pmod{8}$
• Jika $n \equiv 7 \pmod{8}$ maka $n^2 - 1 \equiv 7^2 - 1 \pmod{8} \equiv 0 \pmod{8}$

Dari keempat kasus terlihat bahwa, $8|n^2 - 1$ untuk semua bilangan ganjil $n$


Soal 6
Hitunglah digit terakhir dari $3^{2015}$

Solusi
Perhatikan bahwa $3^4 \equiv 81 \pmod{10} \equiv 1 \pmod{10}$. Akibatnya $3^{2015} \equiv (3^4)^{503} \times 3^3 \pmod {10}  \equiv 1^{503} \times 7 \pmod{10} \equiv 7 \pmod{3}$

Jadi, digit terakhir dari $3^{2015}$ adalah $7$


Soal 7
Jika $n$ asli serta $2n + 1$ dan $3n + 1$ merupakan bilangan kuadrat, buktikan bahwa $8|n$

Solusi
Perhatikan bahwa $x^2 \equiv 0, 4$ atau $1 \pmod{8}$ untuk semua bilangan bulat $n$. Perhatikan bahwa $2n + 1$ merupakan bilangan kudrat ganjil jadi haruslah $2n + 1 \equiv 1 \pmod{8} \implies n \equiv 0 \pmod{4}$.

Karena $n$ genap, maka $3n + 1$ bilangan kuadrat yang ganjil. Jadi $3n + 1 \equiv 1 \pmod{8} \implies 3n \equiv 0 \pmod{8} \implies n \equiv 0 \pmod{8}$ Jadi benar bahwa $8|n$



Latihan 1
Buktikan bahwa untuk setiap bilangan bulat $n$, bilangan $n^5 - n$ habis dibagi $5$

Latihan 2
Buktikan bahwa
(a) $2903^n - 803^n - 464^n + 261^n$ habis dibagi $7$
(b) $3^{2n} - 1$ habis dibagi $8$
(c) $4^{4n} - 5^{3n}$ habis dibagi $131$

Latihan 3
Carilah $2$ digit terakhir dari $81^{100}.121^{100} - 1$

Latihan 4
Untuk setiap bilangan ganjil $n$, buktikan bahwa $n^2 + (n + 2)^2 + (n + 4)^2 + 1$ habis dibagi $12$

Latihan 5
Buktikan bahwa untuk setiap bilangan bulat $n$ berlaku  $n^2 + 1 \equiv 0$ atau $1 \pmod{3}$

Latihan 6
Misalkan $n$ adalah bilangan asli. Buktikan bahwa :
(a) Jika $2n + 1$ dan $3n + 1$ adalah bilangan kuadrat maka $5|n$
(b) Jika $2n + 1$ dan $3n + 1$ adalah bilangan kuadrat maka $40|n$
(c)JIka $3n + 1$ dan $4n + 14$ adalah bilangan kuadrat maka $56|n$

Latihan 7
Tentukan digit terakhir dari $7^{7^7}$

Latihan 8
Tentukan sisanya jika :
(a) $8^{103}$ dibagi $13$
(b) $7^{1000}$ dibagi $24$
(c) $3^{47}$ dibagi $23$
(d) $37^{49}$ dibagi $7$
(e) $45^{2001}$ dibagi $41$
(f) $7^{348}$ dibagi $8$

Latihan 9
Jika $x, y,$ dan $z$ adalah bilangan asli yang memenuhi $x^2 + y^2 = z^2$, maka $60|xyz$