Mengapa Harus Menguasai Divisibility?
Dalam Olimpiade Matematika, baik pada tingkat sekolah, kabupaten/kota, provinsi, OSN, kompetisi regional, hingga IMO, Teori Bilangan (Number Theory) merupakan salah satu bidang penting yang sering diuji.
Salah satu konsep fundamental dalam Teori Bilangan adalah Divisibility (Keterbagian).
Memahami divisibility bukan hanya tentang mengetahui apakah suatu bilangan dapat dibagi habis oleh bilangan lain. Konsep ini menjadi dasar untuk memahami sifat-sifat bilangan, menemukan pola, membangun argumen logis, serta menyusun pembuktian matematis.
Karena itu, sebelum mempelajari topik yang lebih lanjut seperti Aritmetika Modular (Modular Arithmetic), Persamaan Diophantine (Diophantine Equations), dan berbagai teknik dalam Teori Bilangan, pastikan kamu sudah memiliki pemahaman yang kuat mengenai Divisibility.
Part A : Divisibility Properties
Pada bagian ini, kamu akan mengerjakan 15 soal yang disusun secara progresif, mulai dari mengenali definisi dan notasi divisibility, memahami sifat-sifat dasarnya, hingga menerapkannya dalam pembuktian dan permasalahan yang lebih menantang.
Yang perlu kamu pahami dari kelimabelas soal ini adalah bahwa semuanya berhubungan dengan:
Special Properties : Sifat-sifat divisibility, seperti closure, commutativity, associativity, dan identity.
Rangkaian soal ini dirancang untuk membantu kamu membangun intuisi, ketelitian, dan kemampuan berpikir matematis secara bertahap.
Saran Cara Belajar
Kerjakan setiap soal secara mandiri terlebih dahulu sebelum membuka solusi. Cobalah mengalokasikan sekitar 10–15 menit untuk setiap soal. Jika kamu menemukan kesulitan, gunakan tombol Lihat Solusi untuk mempelajari proses berpikir dan strategi yang digunakan. Jangan hanya melihat jawaban akhirnya. Perhatikan mengapa setiap langkah dilakukan, karena kemampuan memahami pola penyelesaian jauh lebih penting daripada sekadar mendapatkan jawaban yang benar. Setelah menyelesaikan seluruh 15 soal, coba kembali ke soal-soal yang sebelumnya terasa sulit. Kemampuan matematika berkembang ketika kamu mampu melihat kembali suatu masalah dan memahami mengapa pendekatan tertentu berhasil. Selamat belajar dan selamat membangun fondasi Teori Bilangan yang kuat.
Question 1
Is this statement true or false?
Any number that is a multiple of 5, and is said to be divisible by 5.
Pilihan Jawaban
- A. True
- B. False
解 Lihat Solusi
Step 1 → Bilangan yang merupakan kelipatan 5 dapat ditulis sebagai hasil perkalian 5 dengan suatu bilangan bulat.
Contohnya:
5 × 1 = 5, 5 × 2 = 10, 5 × 3 = 15
Contohnya:
5 × 1 = 5, 5 × 2 = 10, 5 × 3 = 15
Step 2 → Bilangan yang merupakan kelipatan 5 juga dapat dikatakan divisible by 5, karena bilangan tersebut dapat dibagi 5 tanpa sisa.
Statement = True
Jawaban: A. True
Jawaban: A. True
Question 2
Is this statement true or false?
Any number that is called a multiple of 6, and is said to be divisible by 3.
Pilihan Jawaban
- A. True
- B. False
解 Lihat Solusi
Step 1 → Setiap kelipatan 6 dapat ditulis sebagai:
6 × 1 = 6, 6 × 2 = 12, 6 × 3 = 18, dan seterusnya.
6 × 1 = 6, 6 × 2 = 12, 6 × 3 = 18, dan seterusnya.
Step 2 → Karena 6 merupakan kelipatan dari 3, setiap kelipatan 6 juga dapat dibagi 3 tanpa sisa.
Contoh:
6 ÷ 3 = 2, 12 ÷ 3 = 4, 18 ÷ 3 = 6
Contoh:
6 ÷ 3 = 2, 12 ÷ 3 = 4, 18 ÷ 3 = 6
Statement = True
Jawaban: A. True
Jawaban: A. True
Question 3
What is the correct way to read the following mathematical notation?
\(m \mid n\)
Pilihan Jawaban
- A. m divides n
- B. m divided by n
- C. n divides m
- D. m is divided by n
解 Lihat Solusi
Step 1 → Simbol \(\mid\) dalam matematika berarti "divides" atau "membagi habis".
Jadi, $$ m \mid n $$ dibaca: "m divides n" atau dalam bahasa Indonesia: "m membagi habis n."
Jadi, $$ m \mid n $$ dibaca: "m divides n" atau dalam bahasa Indonesia: "m membagi habis n."
Step 2 → Artinya, \(n\) dapat dibagi oleh \(m\) tanpa sisa.
Contoh: $$ 3 \mid 12 $$ karena $$ 12 \div 3 = 4 $$ tanpa sisa.
Contoh: $$ 3 \mid 12 $$ karena $$ 12 \div 3 = 4 $$ tanpa sisa.
\(m \mid n\) = "m divides n"
Jawaban: A. m divides n
Jawaban: A. m divides n
Question 4
Which one is not correct from this theorem?
• We have \(x \mid x\).
• We always have \(1 \mid x\) and \(x \mid 0\).
• If \(x \mid y\) and \(y \mid z\), then \(x \mid z\).
• If \(x \mid y\), we can find an integer \(k\) so that \(y = kx\). Here, \(k\) cannot be negative.
Theorem 1.2.1. Let \(x, y, z\) be integers.
• We have \(x \mid x\).
• We always have \(1 \mid x\) and \(x \mid 0\).
• If \(x \mid y\) and \(y \mid z\), then \(x \mid z\).
• If \(x \mid y\), we can find an integer \(k\) so that \(y = kx\). Here, \(k\) cannot be negative.
Pilihan Jawaban
- A. \(x \mid x\)
- B. \(1 \mid x\) and \(x \mid 0\)
- C. If \(x \mid y\) and \(y \mid z\), then \(x \mid z\)
- D. If \(x \mid y\), then \(y = kx\), where \(k\) cannot be negative
解 Lihat Solusi
Step 1 → Perhatikan pernyataan terakhir:
Jika \(x \mid y\), maka terdapat bilangan bulat \(k\) sehingga $$ y=kx $$
Jika \(x \mid y\), maka terdapat bilangan bulat \(k\) sehingga $$ y=kx $$
Step 2 → Bilangan bulat \(k\) dapat bernilai negatif.
Contoh: $$ 3 \mid -12 $$ karena $$ -12=(-4)(3) $$ Di sini, \(k=-4\), yang merupakan bilangan bulat negatif.
Contoh: $$ 3 \mid -12 $$ karena $$ -12=(-4)(3) $$ Di sini, \(k=-4\), yang merupakan bilangan bulat negatif.
Step 3 → Jadi, pernyataan bahwa \(k\) cannot be negative adalah tidak benar. Nilai \(k\) harus merupakan bilangan bulat, dan boleh positif, negatif, atau nol.
Pernyataan yang tidak benar = D
Jawaban: D. If \(x \mid y\), then \(y=kx\), where \(k\) cannot be negative
Jawaban: D. If \(x \mid y\), then \(y=kx\), where \(k\) cannot be negative
Question 5
What is the meaning of this:
Pilihan Jawaban
- A. m is greater than n
- B. m divides n if and only if n divided by m is an integer
- C. m equals n
- D. n divides m if and only if m/n is an integer
- E. m and n are relatively prime
解 Lihat Solusi
Step 1 → Pahami simbol-simbol yang digunakan:
• m | n artinya “m membagi n” (m adalah pembagi dari n)
• ⇐⇒ artinya “jika dan hanya jika”
• n / m ∈ ℤ artinya “n dibagi m menghasilkan bilangan bulat”
• m | n artinya “m membagi n” (m adalah pembagi dari n)
• ⇐⇒ artinya “jika dan hanya jika”
• n / m ∈ ℤ artinya “n dibagi m menghasilkan bilangan bulat”
Step 2 → Gabungkan artinya:
Pernyataan tersebut berarti: m membagi n jika dan hanya jika hasil bagi n dengan m adalah bilangan bulat.
Pernyataan tersebut berarti: m membagi n jika dan hanya jika hasil bagi n dengan m adalah bilangan bulat.
Jawaban: B
Question 6
If \( x \mid y \), then \( x \) must be “smaller” than \( y \). Is this true?
Note: You can choose more than one answer.
Note: You can choose more than one answer.
Pilihan Jawaban
- A. Yes, always true
- B. Yes, but only when both are positive
- C. No, because \( x \) can be equal to \( y \)
- D. No, because \( x \) can be larger than \( y \) (especially when \( y \) is negative)
- E. Yes, because the quotient must be greater than 1
解 Lihat Solusi
Step 1 → Ingat definisi \( x \mid y \):
Artinya terdapat bilangan bulat \( k \) sehingga \( y = x \cdot k \).
Artinya terdapat bilangan bulat \( k \) sehingga \( y = x \cdot k \).
Step 2 → Apakah \( x \) harus lebih kecil dari \( y \)?
• Jika \( k = 1 \), maka \( x = y \) (tidak lebih kecil).
• Jika \( y \) negatif, \( x \) bisa lebih besar dari \( y \). Contoh: \( 2 \mid (-4) \), padahal \( 2 > -4 \).
• Jika \( k = 1 \), maka \( x = y \) (tidak lebih kecil).
• Jika \( y \) negatif, \( x \) bisa lebih besar dari \( y \). Contoh: \( 2 \mid (-4) \), padahal \( 2 > -4 \).
Step 3 → Kesimpulan:
Pernyataan tersebut tidak benar. \( x \) tidak harus lebih kecil dari \( y \).
Pernyataan tersebut tidak benar. \( x \) tidak harus lebih kecil dari \( y \).
Jawaban: C and D
Question 7
Look at the following set of multiples of 5:
\[ \mathcal{M} = \{\ldots, -5, 0, 5, 10, 15, 20, 25, 30, 35, 40, 45, 50, 55, 60, \ldots\} \]
If any number from this set is multiplied by a random integer (for example by 7), will the result still be divisible by 5?
\[ \mathcal{M} = \{\ldots, -5, 0, 5, 10, 15, 20, 25, 30, 35, 40, 45, 50, 55, 60, \ldots\} \]
If any number from this set is multiplied by a random integer (for example by 7), will the result still be divisible by 5?
Pilihan Jawaban
- A. Yes, always
- B. No, never
- C. Only if the random number is also a multiple of 5
- D. Only if the random number is odd
- E. Only if the original number is positive
解 Lihat Solusi
Step 1 → Setiap bilangan di himpunan \( \mathcal{M} \) adalah kelipatan 5, artinya bisa ditulis sebagai:
\[ m = 5k \] untuk suatu bilangan bulat \( k \).
\[ m = 5k \] untuk suatu bilangan bulat \( k \).
Step 2 → Kalikan dengan bilangan acak (misalnya 7):
\[ 7 \cdot m = 7 \cdot (5k) = 5 \cdot (7k) \]
Hasilnya masih berbentuk \( 5 \times \) (bilangan bulat), jadi tetap habis dibagi 5.
\[ 7 \cdot m = 7 \cdot (5k) = 5 \cdot (7k) \]
Hasilnya masih berbentuk \( 5 \times \) (bilangan bulat), jadi tetap habis dibagi 5.
Step 3 → Kesimpulan:
Ya, hasil perkalian tetap selalu habis dibagi 5, berapa pun bilangan bulat yang dikalikan.
Ya, hasil perkalian tetap selalu habis dibagi 5, berapa pun bilangan bulat yang dikalikan.
Jawaban: A
Question 8
Look at the following set of multiples of 5:
\[ \mathcal{M} = \{\ldots, -5, 0, 5, 10, 15, 20, 25, 30, 35, 40, 45, 50, 55, 60, \ldots\} \]
If any two numbers from \( \mathcal{M} \) are added, will the result still be divisible by 5?
\[ \mathcal{M} = \{\ldots, -5, 0, 5, 10, 15, 20, 25, 30, 35, 40, 45, 50, 55, 60, \ldots\} \]
If any two numbers from \( \mathcal{M} \) are added, will the result still be divisible by 5?
Pilihan Jawaban
- A. Yes, always
- B. No, never
- C. Only if both numbers are positive
- D. Only if both numbers are even multiples of 5
- E. Only if one of them is zero
解 Lihat Solusi
Step 1 → Setiap bilangan di himpunan \( \mathcal{M} \) adalah kelipatan 5, sehingga dapat ditulis:
\[ m_1 = 5a \quad \text{dan} \quad m_2 = 5b \] untuk bilangan bulat \( a \) dan \( b \).
\[ m_1 = 5a \quad \text{dan} \quad m_2 = 5b \] untuk bilangan bulat \( a \) dan \( b \).
Step 2 → Jumlahkan kedua bilangan tersebut:
\[ m_1 + m_2 = 5a + 5b = 5(a + b) \]
Hasilnya masih berbentuk \( 5 \times \) (bilangan bulat), jadi tetap habis dibagi 5.
\[ m_1 + m_2 = 5a + 5b = 5(a + b) \]
Hasilnya masih berbentuk \( 5 \times \) (bilangan bulat), jadi tetap habis dibagi 5.
Step 3 → Kesimpulan:
Ya, jumlah dua bilangan apa pun dari \( \mathcal{M} \) selalu masih habis dibagi 5.
Ya, jumlah dua bilangan apa pun dari \( \mathcal{M} \) selalu masih habis dibagi 5.
Jawaban: A
Question 9
Is this statement correct?
For any two numbers \( x, y \in \mathcal{M} \), we have \( ax + by \in \mathcal{M} \) for any integers \( a, b \).
(where \( \mathcal{M} \) is the set of all multiples of 5)
For any two numbers \( x, y \in \mathcal{M} \), we have \( ax + by \in \mathcal{M} \) for any integers \( a, b \).
(where \( \mathcal{M} \) is the set of all multiples of 5)
Pilihan Jawaban
- A. Yes, it is always correct
- B. No, it is never correct
- C. Only true when \( a = b = 1 \)
- D. Only true when \( a \) and \( b \) are positive
- E. Only true when \( x = y \)
解 Lihat Solusi
Step 1 → Karena \( x, y \in \mathcal{M} \), maka:
\[ x = 5k \quad \text{dan} \quad y = 5m \] untuk bilangan bulat \( k \) dan \( m \).
\[ x = 5k \quad \text{dan} \quad y = 5m \] untuk bilangan bulat \( k \) dan \( m \).
Step 2 → Hitung kombinasi linear \( ax + by \):
\[ ax + by = a(5k) + b(5m) = 5(ak + bm) \]
Hasilnya adalah kelipatan 5, sehingga \( ax + by \in \mathcal{M} \).
\[ ax + by = a(5k) + b(5m) = 5(ak + bm) \]
Hasilnya adalah kelipatan 5, sehingga \( ax + by \in \mathcal{M} \).
Step 3 → Contoh dengan angka:
Ambil \( x = 10 \) dan \( y = -15 \) (keduanya anggota \( \mathcal{M} \)).
Misalkan \( a = 3 \) dan \( b = -2 \).
Maka: \[ 3 \cdot 10 + (-2) \cdot (-15) = 30 + 30 = 60 \]
60 adalah kelipatan 5, jadi \( 60 \in \mathcal{M} \).
Ambil \( x = 10 \) dan \( y = -15 \) (keduanya anggota \( \mathcal{M} \)).
Misalkan \( a = 3 \) dan \( b = -2 \).
Maka: \[ 3 \cdot 10 + (-2) \cdot (-15) = 30 + 30 = 60 \]
60 adalah kelipatan 5, jadi \( 60 \in \mathcal{M} \).
Step 4 → Kesimpulan:
Pernyataan tersebut benar untuk sembarang bilangan bulat \( a \) dan \( b \).
Pernyataan tersebut benar untuk sembarang bilangan bulat \( a \) dan \( b \).
Jawaban: A
Question 10
Is this statement correct?
Suppose \( c \mid x \) and \( c \mid y \). Then \( c \mid (ax + by) \) for any integers \( a, b \).
Suppose \( c \mid x \) and \( c \mid y \). Then \( c \mid (ax + by) \) for any integers \( a, b \).
Pilihan Jawaban
- A. Yes, it is always true
- B. No, it is never true
- C. Only true when \( a = b = 1 \)
- D. Only true when \( c \) is prime
- E. Only true when \( x = y \)
解 Lihat Solusi
Step 1 → Karena \( c \mid x \) dan \( c \mid y \), maka:
\[ x = c \cdot k \quad \text{dan} \quad y = c \cdot m \] untuk bilangan bulat \( k \) dan \( m \).
\[ x = c \cdot k \quad \text{dan} \quad y = c \cdot m \] untuk bilangan bulat \( k \) dan \( m \).
Step 2 → Hitung \( ax + by \):
\[ ax + by = a(ck) + b(cm) = c(ak + bm) \]
Jelas bahwa \( c \) membagi \( ax + by \).
\[ ax + by = a(ck) + b(cm) = c(ak + bm) \]
Jelas bahwa \( c \) membagi \( ax + by \).
Step 3 → Contoh dengan angka:
Misalkan \( c = 4 \), \( x = 12 \), \( y = -8 \) (4 membagi keduanya).
Ambil \( a = 3 \) dan \( b = 5 \).
Maka: \[ 3 \cdot 12 + 5 \cdot (-8) = 36 - 40 = -4 \]
4 membagi −4, karena \( -4 = 4 \cdot (-1) \).
Misalkan \( c = 4 \), \( x = 12 \), \( y = -8 \) (4 membagi keduanya).
Ambil \( a = 3 \) dan \( b = 5 \).
Maka: \[ 3 \cdot 12 + 5 \cdot (-8) = 36 - 40 = -4 \]
4 membagi −4, karena \( -4 = 4 \cdot (-1) \).
Step 4 → Kesimpulan:
Pernyataan tersebut benar untuk sembarang bilangan bulat \( a \) dan \( b \).
Pernyataan tersebut benar untuk sembarang bilangan bulat \( a \) dan \( b \).
Jawaban: A
Question 11
How many statements are incorrect from the following about divisibility?
Let \( x, y, z \) be integers.
Let \( x, y, z \) be integers.
- \( x \mid x \).
- \( 1 \mid x \) and \( x \mid 0 \).
- \( x \mid y \), \( y \mid z \) \(\implies\) \( x \mid z \).
- If \( z \mid x, y \), then \( z \mid ax + by \) for any integers \( a, b \) (possibly negative).
- If \( x \mid y \), then either \( y = 0 \), or \( |x| \leq |y| \).
- If \( x \mid y \) and \( y \mid x \), then \( x = \pm y \), i.e. \( |x| = |y| \).
- \( x \mid y \) if and only if \( xz \mid yz \) for some non-zero integer \( z \).
- \( x \mid y \) \(\implies\) \( x \mid yz \) for any \( z \).
Pilihan Jawaban
- A. 5
- B. 4
- C. 2
- D. 3
- E. 0
解 Lihat Solusi
Step 1 → Periksa satu per satu:
1. \( x \mid x \) → Benar (karena \( x = x \cdot 1 \))
2. \( 1 \mid x \) dan \( x \mid 0 \) → Benar (1 membagi semua bilangan; setiap bilangan membagi 0)
3. Transitivitas: \( x \mid y \) dan \( y \mid z \) \(\implies\) \( x \mid z \) → Benar
4. Jika \( z \) membagi \( x \) dan \( y \), maka \( z \) membagi kombinasi linear apa pun → Benar
5. Jika \( x \mid y \), maka \( y = 0 \) atau \( |x| \leq |y| \) → Benar
6. Jika \( x \mid y \) dan \( y \mid x \), maka \( |x| = |y| \) → Benar
7. \( x \mid y \) \(\iff\) \( xz \mid yz \) untuk suatu \( z \neq 0 \) → Benar
8. \( x \mid y \) \(\implies\) \( x \mid yz \) untuk sembarang \( z \) → Benar
1. \( x \mid x \) → Benar (karena \( x = x \cdot 1 \))
2. \( 1 \mid x \) dan \( x \mid 0 \) → Benar (1 membagi semua bilangan; setiap bilangan membagi 0)
3. Transitivitas: \( x \mid y \) dan \( y \mid z \) \(\implies\) \( x \mid z \) → Benar
4. Jika \( z \) membagi \( x \) dan \( y \), maka \( z \) membagi kombinasi linear apa pun → Benar
5. Jika \( x \mid y \), maka \( y = 0 \) atau \( |x| \leq |y| \) → Benar
6. Jika \( x \mid y \) dan \( y \mid x \), maka \( |x| = |y| \) → Benar
7. \( x \mid y \) \(\iff\) \( xz \mid yz \) untuk suatu \( z \neq 0 \) → Benar
8. \( x \mid y \) \(\implies\) \( x \mid yz \) untuk sembarang \( z \) → Benar
Step 2 → Semua 8 pernyataan di atas adalah benar.
Jumlah pernyataan yang salah = 0
Jawaban: E
Jawaban: E
Question 12
Show that if \( n > 1 \) is an integer, we can’t have \( n \mid 2n^2 + 3n + 1 \).
解 Lihat Solusi
Step 1 → Misalkan \( n \mid 2n^2 + 3n + 1 \). Maka terdapat bilangan bulat \( k \) sehingga:
\[ 2n^2 + 3n + 1 = n \cdot k \]
\[ 2n^2 + 3n + 1 = n \cdot k \]
Step 2 → Karena \( n \) membagi \( 2n^2 \) dan \( 3n \), maka \( n \) juga harus membagi sisanya, yaitu 1:
\[ n \mid (2n^2 + 3n + 1) \implies n \mid 1 \]
\[ n \mid (2n^2 + 3n + 1) \implies n \mid 1 \]
Step 3 → Satu-satunya pembagi dari 1 adalah \( \pm 1 \).
Tetapi \( n > 1 \), sehingga \( n \) tidak mungkin membagi 1.
Tetapi \( n > 1 \), sehingga \( n \) tidak mungkin membagi 1.
Step 4 → Contoh angka:
• \( n = 2 \): \( 2(2)^2 + 3(2) + 1 = 15 \), 2 tidak membagi 15.
• \( n = 3 \): \( 2(9) + 9 + 1 = 28 \), 3 tidak membagi 28.
• \( n = 4 \): \( 2(16) + 12 + 1 = 45 \), 4 tidak membagi 45.
• \( n = 2 \): \( 2(2)^2 + 3(2) + 1 = 15 \), 2 tidak membagi 15.
• \( n = 3 \): \( 2(9) + 9 + 1 = 28 \), 3 tidak membagi 28.
• \( n = 4 \): \( 2(16) + 12 + 1 = 45 \), 4 tidak membagi 45.
Kesimpulan: Tidak mungkin \( n \mid 2n^2 + 3n + 1 \) jika \( n > 1 \).
Question 13
Let \( a > b \) be natural numbers. Show that we can’t have \( a \mid 2a + b \).
解 Lihat Solusi
Step 1 → Misalkan \( a \mid 2a + b \). Maka terdapat bilangan bulat \( k \) sehingga:
\[ 2a + b = a \cdot k \]
\[ 2a + b = a \cdot k \]
Step 2 → Karena \( a \) membagi \( 2a \), maka \( a \) juga harus membagi \( b \):
\[ a \mid (2a + b) \implies a \mid b \]
\[ a \mid (2a + b) \implies a \mid b \]
Step 3 → Namun \( a > b \) dan keduanya bilangan asli (natural numbers), sehingga \( a \) tidak mungkin membagi \( b \) (karena pembagi positif dari \( b \) paling besar adalah \( b \) itu sendiri).
Step 4 → Contoh angka:
• \( a = 5 \), \( b = 3 \): \( 2(5) + 3 = 13 \), 5 tidak membagi 13.
• \( a = 7 \), \( b = 2 \): \( 2(7) + 2 = 16 \), 7 tidak membagi 16.
• \( a = 4 \), \( b = 1 \): \( 2(4) + 1 = 9 \), 4 tidak membagi 9.
• \( a = 5 \), \( b = 3 \): \( 2(5) + 3 = 13 \), 5 tidak membagi 13.
• \( a = 7 \), \( b = 2 \): \( 2(7) + 2 = 16 \), 7 tidak membagi 16.
• \( a = 4 \), \( b = 1 \): \( 2(4) + 1 = 9 \), 4 tidak membagi 9.
Kesimpulan: Tidak mungkin \( a \mid 2a + b \) jika \( a > b \) bilangan asli.
Question 14
For 2 fixed integers \( x, y \), prove that
\[ x - y \mid x^n - y^n \]
for any integer \( n \). (Hint: Long division)
解 Lihat Solusi
Step 1 → Kita buktikan untuk \( n \geq 1 \) (kasus \( n = 0 \) trivial karena \( x^0 - y^0 = 0 \)).
Gunakan pembagian bersusun (long division) atau faktorisasi: \[ x^n - y^n = (x - y)(x^{n-1} + x^{n-2}y + x^{n-3}y^2 + \cdots + xy^{n-2} + y^{n-1}) \]
Gunakan pembagian bersusun (long division) atau faktorisasi: \[ x^n - y^n = (x - y)(x^{n-1} + x^{n-2}y + x^{n-3}y^2 + \cdots + xy^{n-2} + y^{n-1}) \]
Step 2 → Karena ruas kanan adalah \( (x - y) \) dikalikan dengan suatu bilangan bulat (polinomial dengan koefisien bilangan bulat), maka jelas:
\[ x - y \mid x^n - y^n \]
Step 3 → Bukti dengan induksi (alternatif):
• Basis: \( n = 1 \), jelas \( x - y \mid x - y \).
• Asumsi benar untuk \( n = k \): \( x - y \mid x^k - y^k \).
• Untuk \( n = k+1 \): \[ x^{k+1} - y^{k+1} = x \cdot x^k - y \cdot y^k = x(x^k - y^k) + y^k (x - y) \]
Kedua suku habis dibagi \( x - y \), sehingga hasilnya juga.
• Basis: \( n = 1 \), jelas \( x - y \mid x - y \).
• Asumsi benar untuk \( n = k \): \( x - y \mid x^k - y^k \).
• Untuk \( n = k+1 \): \[ x^{k+1} - y^{k+1} = x \cdot x^k - y \cdot y^k = x(x^k - y^k) + y^k (x - y) \]
Kedua suku habis dibagi \( x - y \), sehingga hasilnya juga.
Step 4 → Contoh angka:
• \( x = 5 \), \( y = 2 \), \( n = 3 \): \( 5-2=3 \), \( 5^3 - 2^3 = 125 - 8 = 117 \), dan \( 117 \div 3 = 39 \).
• \( x = 4 \), \( y = -1 \), \( n = 2 \): \( 4-(-1)=5 \), \( 16 - 1 = 15 \), \( 15 \div 5 = 3 \).
• \( x = 5 \), \( y = 2 \), \( n = 3 \): \( 5-2=3 \), \( 5^3 - 2^3 = 125 - 8 = 117 \), dan \( 117 \div 3 = 39 \).
• \( x = 4 \), \( y = -1 \), \( n = 2 \): \( 4-(-1)=5 \), \( 16 - 1 = 15 \), \( 15 \div 5 = 3 \).
Kesimpulan: \( x - y \) selalu membagi \( x^n - y^n \) untuk setiap bilangan bulat \( n \geq 0 \).
Question 15
Problem (IMO Level)
Let \( a \) and \( b \) be positive integers. Prove that if \( ab + 1 \) divides \( a^2 + b^2 \), then \[ \frac{a^2 + b^2}{ab + 1} \] must be a perfect square.
Let \( a \) and \( b \) be positive integers. Prove that if \( ab + 1 \) divides \( a^2 + b^2 \), then \[ \frac{a^2 + b^2}{ab + 1} \] must be a perfect square.
解 Lihat Solusi
Step 1 → Misalkan
\[
k = \frac{a^2 + b^2}{ab + 1}
\]
adalah bilangan bulat positif. Kita akan membuktikan bahwa \( k \) harus berupa kuadrat sempurna.
Step 2 → Anggap \( k \) bukan kuadrat sempurna. Di antara semua pasangan bilangan asli \( (a,b) \) yang memenuhi persamaan
\[
a^2 + b^2 = k(ab + 1)
\]
dengan \( k \) tetap, pilih pasangan yang memiliki \( a + b \) paling kecil. Tanpa mengurangi keumuman, asumsikan \( a \ge b \).
Step 3 → Tinjau persamaan kuadrat dalam variabel \( x \):
\[
x^2 - (kb)x + (b^2 - k) = 0.
\]
Karena \( a \) adalah salah satu akar, menurut rumus Vieta, akar yang lain (sebut \( a' \)) memenuhi:
\[
a + a' = kb, \qquad a \cdot a' = b^2 - k.
\]
Sehingga
\[
a' = \frac{b^2 - k}{a}.
\]
Step 4 → Tunjukkan bahwa \( a' \) bilangan bulat positif:
• \( a' \ne 0 \) karena \( k \) bukan kuadrat sempurna (jadi \( b^2 \ne k \)).
• \( a' \) tidak mungkin negatif: jika \( a' < 0 \), maka substitusi ke persamaan kuadrat menghasilkan kontradiksi (nilai ruas kiri positif).
• Karena \( a \ge b \), maka \[ a' = \frac{b^2 - k}{a} < \frac{b^2}{a} \le b \le a, \] sehingga \( a' < a \) dan \( a' + b < a + b \).
• \( a' \ne 0 \) karena \( k \) bukan kuadrat sempurna (jadi \( b^2 \ne k \)).
• \( a' \) tidak mungkin negatif: jika \( a' < 0 \), maka substitusi ke persamaan kuadrat menghasilkan kontradiksi (nilai ruas kiri positif).
• Karena \( a \ge b \), maka \[ a' = \frac{b^2 - k}{a} < \frac{b^2}{a} \le b \le a, \] sehingga \( a' < a \) dan \( a' + b < a + b \).
Step 5 → Pasangan \( (a', b) \) juga memenuhi
\[
\frac{a'^2 + b^2}{a'b + 1} = k
\]
dengan jumlah yang lebih kecil dari \( a + b \). Ini bertentangan dengan minimalitas pasangan \( (a,b) \).
Step 6 → Kontradiksi ini menunjukkan bahwa asumsi “\( k \) bukan kuadrat sempurna” salah. Jadi \( k \) harus berupa kuadrat sempurna.
Kesimpulan: Jika \( ab + 1 \) membagi \( a^2 + b^2 \), maka hasil baginya adalah kuadrat sempurna.
Message for you 💬
Lihat pesan
Cool! Kalau kamu belum paham soal no 28, 29 dan 30, itu karena ini memang soal yang sudah sangat advanced. Pastikan saja soal sampai no 27 kamu bisa paham.Lanjut ke part berikutntya tentang: Prime dan The Fundamental Theorem of Arithmetic.
from: Equalyra
Baca juga dalam seri Divisibility Olimpiade Matematika: