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 C : Prime and The Fundamental Theorem of Arithmetic
Pada bagian ini, kamu akan mengerjakan 15 soal yang disusun secara progresif, mulai dari soal yang paling sederhana hingga yang lebih kompleks.
Yang perlu kamu pahami dari kelimabelas soal ini adalah bahwa semuanya berhubungan dengan:
Prime & The Fundamental Theorem of Arithmetic: tentang aturan yang menyatakan bahwa bilangan prima adalah "the building blocks" dari semua bilangan bulat positif yang lebih besar dari 1. Dengan kata lain, setiap bilangan asli yang lebih besar dari 1 dapat dinyatakan sebagai produk dari bilangan prima secara unik, terlepas dari urutan faktor-faktor primanya.
Rangkaian soal ini dirancang untuk membantu kamu membangun intuisi, ketelitian, dan kemampuan berpikir matematis secara bertahap tentang topik ini.
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 1 a prime number?
Pilihan Jawaban
- A. Yes, because it is only divisible by 1
- B. Yes, because it is a positive integer
- C. No, because a prime must be greater than 1
- D. No, because 1 has too many divisors
- E. Yes, according to the Prime Number Theorem
✅ Lihat Solusi
Step 1 → Definisi bilangan prima:
Bilangan prima adalah bilangan bulat positif yang lebih besar dari 1 dan hanya memiliki dua pembagi positif, yaitu 1 dan dirinya sendiri.
Bilangan prima adalah bilangan bulat positif yang lebih besar dari 1 dan hanya memiliki dua pembagi positif, yaitu 1 dan dirinya sendiri.
Step 2 → Mengapa 1 bukan prima?
• 1 tidak lebih besar dari 1.
• 1 hanya memiliki satu pembagi positif (yaitu 1 itu sendiri), bukan dua.
Jika 1 dianggap prima, banyak teorema penting dalam teori bilangan (seperti Teorema Fundamental Aritmetika) akan menjadi rusak.
• 1 tidak lebih besar dari 1.
• 1 hanya memiliki satu pembagi positif (yaitu 1 itu sendiri), bukan dua.
Jika 1 dianggap prima, banyak teorema penting dalam teori bilangan (seperti Teorema Fundamental Aritmetika) akan menjadi rusak.
Step 3 → Catatan:
Teks menyebutkan bahwa bilangan prima adalah “atoms of all numbers”. 1 bukan atom, melainkan unit.
Teks menyebutkan bahwa bilangan prima adalah “atoms of all numbers”. 1 bukan atom, melainkan unit.
Jawaban: C
Question 2
Is this statement true or false?
You can reduce any composite number into a product of primes.
Pilihan Jawaban
- A. True
- B. False
解 Lihat Solusi
Step 1 → Menurut Fundamental Theorem of Arithmetic, setiap bilangan bulat lebih besar dari 1 dapat dinyatakan sebagai hasil kali bilangan prima (secara unik, kecuali urutannya).
Step 2 → Bilangan komposit adalah bilangan yang lebih besar dari 1 dan bukan bilangan prima. Oleh karena itu, setiap bilangan komposit pasti dapat diuraikan menjadi hasil kali bilangan-bilangan prima.
Contoh:
12 = 2 × 2 × 3
45 = 3 × 3 × 5
100 = 2 × 2 × 5 × 5
Contoh:
12 = 2 × 2 × 3
45 = 3 × 3 × 5
100 = 2 × 2 × 5 × 5
Statement = True
Jawaban: A. True
Jawaban: A. True
Question 3
What does this statement mean?
Fundamental Theorem of Arithmetic: Any natural number greater than 1 has a unique prime factorization up to order.
Pilihan Jawaban
- A. Every natural number greater than 1 can only be factored into primes in one single way, and the order of the factors must also be the same.
- B. Every natural number greater than 1 can be written as a product of primes, and this factorization is unique except for the order of the factors.
- C. Every natural number greater than 1 is always a prime number.
- D. Every natural number greater than 1 can be factored into primes in many completely different ways, including different prime factors.
解 Lihat Solusi
Step 1 → Fundamental Theorem of Arithmetic menyatakan bahwa setiap bilangan asli (natural number) yang lebih besar dari 1 dapat ditulis sebagai hasil kali bilangan-bilangan prima.
Step 2 → Faktorisasi prima tersebut bersifat unik, kecuali urutan faktor-faktornya. Artinya, tidak peduli bagaimana kita menguraikannya, kumpulan bilangan primanya selalu sama (hanya boleh berbeda urutan).
Contoh:
60 = 2 × 2 × 3 × 5
60 = 2 × 3 × 2 × 5
60 = 5 × 3 × 2 × 2
Ketiga cara di atas menghasilkan faktor prima yang sama: dua buah 2, satu buah 3, dan satu buah 5. Hanya urutannya yang berbeda.
Contoh:
60 = 2 × 2 × 3 × 5
60 = 2 × 3 × 2 × 5
60 = 5 × 3 × 2 × 2
Ketiga cara di atas menghasilkan faktor prima yang sama: dua buah 2, satu buah 3, dan satu buah 5. Hanya urutannya yang berbeda.
Step 3 → “Up to order” berarti kita mengabaikan urutan. Jadi, faktorisasi prima dianggap sama selama bilangan primanya sama, meskipun posisinya berbeda.
Step 4 → Kata unique di sini berarti dua hal:
1. Ada setidaknya satu cara (existence) untuk menguraikan bilangan tersebut menjadi hasil kali bilangan prima.
2. Ada paling banyak satu cara (uniqueness) — tidak ada cara lain yang berbeda (kecuali urutan).
1. Ada setidaknya satu cara (existence) untuk menguraikan bilangan tersebut menjadi hasil kali bilangan prima.
2. Ada paling banyak satu cara (uniqueness) — tidak ada cara lain yang berbeda (kecuali urutan).
Jawaban yang benar: B
Pilihan B paling tepat menggambarkan arti pernyataan tersebut.
Pilihan B paling tepat menggambarkan arti pernyataan tersebut.
Question 4
Because every integer greater than 1 can be completely factored into primes, and those primes uniquely identify the number, it is helpful to regard each number as a multiset of its prime factors.
Under this view:
The number 1 corresponds to the empty multiset.
6 = 2 × 3 is written {2, 3}.
70 = 2 × 5 × 7 is written {2, 5, 7}.
4 = 2² is written {2, 2} (multisets allow repeated elements).
In general, if \[ n = p_1^{\alpha_1} p_2^{\alpha_2} \cdots p_k^{\alpha_k}, \] then \[ n \equiv \{\underbrace{p_1,\dots,p_1}_{\alpha_1\text{ times}},\; \underbrace{p_2,\dots,p_2}_{\alpha_2\text{ times}},\; \dots,\; \underbrace{p_k,\dots,p_k}_{\alpha_k\text{ times}}\}. \] For a negative number we simply add −1 to the multiset; for example, −20 ≡ {−1, 2, 2, 5}.
Which statement best summarizes this representation?
Under this view:
In general, if \[ n = p_1^{\alpha_1} p_2^{\alpha_2} \cdots p_k^{\alpha_k}, \] then \[ n \equiv \{\underbrace{p_1,\dots,p_1}_{\alpha_1\text{ times}},\; \underbrace{p_2,\dots,p_2}_{\alpha_2\text{ times}},\; \dots,\; \underbrace{p_k,\dots,p_k}_{\alpha_k\text{ times}}\}. \] For a negative number we simply add −1 to the multiset; for example, −20 ≡ {−1, 2, 2, 5}.
Which statement best summarizes this representation?
Pilihan Jawaban
- A. Every number is represented as a multiset of its prime factors (with repetition allowed according to the exponents). The number 1 is the empty set, and negative numbers include −1.
- B. Numbers are represented only as ordinary sets without repetition, so powers like 4 = 2² cannot be written.
- C. Only prime numbers can be written as sets; composite numbers cannot be represented this way.
- D. The number 1 is written as {1}, and every number must include the factor 1 in its set.
解 Lihat Solusi
Step 1 → Setiap bilangan bulat dapat diuraikan menjadi faktor-faktor primanya. Faktor-faktor prima tersebut menjadi “identitas” bilangan tersebut, sehingga bilangan dapat dipandang sebagai multiset (himpunan yang memperbolehkan elemen berulang).
Step 2 → Contoh:
- Bilangan 1 = himpunan kosong { }
- Bilangan 6 = 2 × 3 ≡ {2, 3}
- Bilangan 70 = 2 × 5 × 7 ≡ {2, 5, 7}
- Bilangan 4 = 2² ≡ {2, 2} (pengulangan diperbolehkan karena multiset)
- Bilangan 1 = himpunan kosong { }
- Bilangan 6 = 2 × 3 ≡ {2, 3}
- Bilangan 70 = 2 × 5 × 7 ≡ {2, 5, 7}
- Bilangan 4 = 2² ≡ {2, 2} (pengulangan diperbolehkan karena multiset)
Step 3 → Secara umum, eksponen pada faktorisasi prima menunjukkan berapa kali bilangan prima tersebut muncul di dalam multiset.
Step 4 → Jika bilangan negatif, cukup tambahkan −1 ke dalam multiset. Contoh: −20 ≡ {−1, 2, 2, 5}.
Jawaban yang benar: A
Pilihan A paling lengkap dan sesuai dengan penjelasan di atas.
Pilihan A paling lengkap dan sesuai dengan penjelasan di atas.
Question 5
Theorem (Divisibility in Sets):
Let \( a \) and \( b \) be two integers. Then
\[
a \mid b \iff A \subset B,
\]
where \( A \) and \( B \) are the multisets of prime factors of \( a \) and \( b \) respectively.
What is the main advantage of viewing numbers as multisets of their prime factors and using the above theorem?
What is the main advantage of viewing numbers as multisets of their prime factors and using the above theorem?
Pilihan Jawaban
- A. It allows us to use Venn diagrams and geometric/pictorial thinking, which makes many properties of GCD and LCM much simpler and more intuitive.
- B. It eliminates the need to use prime factorization at all.
- C. It only works for prime numbers and cannot be applied to composite numbers.
- D. It forces us to abandon the concepts of GCD and LCM completely.
解 Lihat Solusi
Step 1 → Theorem menyatakan bahwa \( a \) membagi \( b \) jika dan hanya jika multiset faktor prima dari \( a \) merupakan subset dari multiset faktor prima dari \( b \).
Step 2 → Keuntungan utama memandang bilangan sebagai multiset faktor prima adalah kita dapat menggunakan diagram Venn dan pemikiran geometris/pictorial. Otak manusia lebih mudah memahami konsep secara visual.
Step 3 → Banyak sifat GCD dan LCM menjadi jauh lebih sederhana (bahkan trivial) ketika dipandang melalui kacamata himpunan dan Theorem di atas.
Jawaban yang benar: A
Pilihan A paling tepat menggambarkan keuntungan yang dijelaskan.
Pilihan A paling tepat menggambarkan keuntungan yang dijelaskan.
Question 6
Using the multiset representation of numbers (where a number is identified with the multiset of its prime factors), the GCD of two numbers \( m \) and \( n \) is defined as the intersection of their multisets:
\[
\gcd(m,n) = M \cap N.
\]
For example, if \( m = 2^2 \times 5^3 \times 7 \) and \( n = 2^3 \times 3^2 \times 7^2 \), then \[ \gcd(m,n) = 2^2 \times 7. \]
It is also known that:
\( \gcd(a,b) \) is the largest positive integer that divides both \( a \) and \( b \).
If \( c \mid a \) and \( c \mid b \), then \( c \mid \gcd(a,b) \).
Problem: Let \( a, b, c \) be positive integers such that \[ \gcd(a,b) = 12, \quad \gcd(b,c) = 18, \quad \gcd(c,a) = 24. \] Find \( \gcd(a,b,c) \).
For example, if \( m = 2^2 \times 5^3 \times 7 \) and \( n = 2^3 \times 3^2 \times 7^2 \), then \[ \gcd(m,n) = 2^2 \times 7. \]
It is also known that:
Problem: Let \( a, b, c \) be positive integers such that \[ \gcd(a,b) = 12, \quad \gcd(b,c) = 18, \quad \gcd(c,a) = 24. \] Find \( \gcd(a,b,c) \).
Pilihan Jawaban
- A. 6
- B. 12
- C. 18
- D. 24
解 Lihat Solusi
Step 1 → Karena GCD adalah irisan multiset faktor prima, maka
\[
\gcd(a,b,c) = A \cap B \cap C.
\]
Step 2 → Kita tahu:
\[
\begin{align*}
\gcd(a,b) &= 12 = 2^2 \times 3,\\
\gcd(b,c) &= 18 = 2 \times 3^2,\\
\gcd(c,a) &= 24 = 2^3 \times 3.
\end{align*}
\]
Step 3 → Irisan ketiga multiset \( A \cap B \cap C \) harus mengambil eksponen terkecil yang muncul di ketiga GCD berpasangan:
- Untuk prima 2: eksponen minimum yang mungkin adalah \( \min(2,1,3) = 1 \)
- Untuk prima 3: eksponen minimum yang mungkin adalah \( \min(1,2,1) = 1 \)
Sehingga
\[
\gcd(a,b,c) = 2^1 \times 3^1 = 6.
\]
Step 4 → Memang, 6 membagi ketiga bilangan \( a,b,c \), dan tidak ada bilangan yang lebih besar dari 6 yang dapat membagi ketiganya sekaligus (karena eksponen 2 dan 3 sudah minimal).
Jawaban yang benar: A. 6
Question 7
Lemma:
If \( c \mid a \) and \( c \mid b \), then \( c \mid \gcd(a,b) \). This follows from the multiset view:
\( C \subset A \) and \( C \subset B \) implies \( C \subset A \cap B \).
Problem: Let \( a \) and \( b \) be positive integers such that \[ \gcd(a,b) = 12 \quad \text{and} \quad \operatorname{lcm}(a,b) = 180. \] How many ordered pairs \( (a,b) \) satisfy these conditions?
If \( c \mid a \) and \( c \mid b \), then \( c \mid \gcd(a,b) \). This follows from the multiset view:
\( C \subset A \) and \( C \subset B \) implies \( C \subset A \cap B \).
Problem: Let \( a \) and \( b \) be positive integers such that \[ \gcd(a,b) = 12 \quad \text{and} \quad \operatorname{lcm}(a,b) = 180. \] How many ordered pairs \( (a,b) \) satisfy these conditions?
Pilihan Jawaban
- A. 4
- B. 6
- C. 8
- D. 9
解 Lihat Solusi
Step 1 →
\[
12 = 2^2 \times 3, \qquad 180 = 2^2 \times 3^2 \times 5.
\]
Step 2 → Misalkan \( a = 2^x 3^y 5^z \) dan \( b = 2^u 3^v 5^w \). Maka:
- \( x = u = 2 \)
- \( \{\min(y,v),\max(y,v)\} = \{1,2\} \) → 2 pilihan
- \( \{\min(z,w),\max(z,w)\} = \{0,1\} \) → 2 pilihan
Step 3 → Total pasangan berurutan: \( 2 \times 2 = 4 \).
Jawaban: A. 4
Question 8
Lemma (Prime Factorization of GCD):
If \[ a = p_1^{\alpha_1} p_2^{\alpha_2} \cdots p_k^{\alpha_k}, \quad b = p_1^{\beta_1} p_2^{\beta_2} \cdots p_k^{\beta_k}, \] then \[ \gcd(a,b) = p_1^{\min(\alpha_1,\beta_1)} p_2^{\min(\alpha_2,\beta_2)} \cdots p_k^{\min(\alpha_k,\beta_k)}. \]
Problem:
Find \[ \gcd(2^5 \cdot 3^4 \cdot 5^2 \cdot 7,\ 2^3 \cdot 3^7 \cdot 5 \cdot 11^2). \]
If \[ a = p_1^{\alpha_1} p_2^{\alpha_2} \cdots p_k^{\alpha_k}, \quad b = p_1^{\beta_1} p_2^{\beta_2} \cdots p_k^{\beta_k}, \] then \[ \gcd(a,b) = p_1^{\min(\alpha_1,\beta_1)} p_2^{\min(\alpha_2,\beta_2)} \cdots p_k^{\min(\alpha_k,\beta_k)}. \]
Problem:
Find \[ \gcd(2^5 \cdot 3^4 \cdot 5^2 \cdot 7,\ 2^3 \cdot 3^7 \cdot 5 \cdot 11^2). \]
Pilihan Jawaban
- A. \(2^3 \cdot 3^4 \cdot 5\)
- B. \(2^3 \cdot 3^4 \cdot 5^2\)
- C. \(2^5 \cdot 3^4 \cdot 5\)
- D. \(2^3 \cdot 3^7 \cdot 5\)
解 Lihat Solusi
Step 1 → Ambil eksponen minimum untuk setiap prima:
- 2: \(\min(5,3) = 3\)
- 3: \(\min(4,7) = 4\)
- 5: \(\min(2,1) = 1\)
- 7: \(\min(1,0) = 0\)
- 11: \(\min(0,2) = 0\)
Step 2 → Jadi
\[
\gcd = 2^3 \cdot 3^4 \cdot 5^1.
\]
Jawaban: A. \(2^3 \cdot 3^4 \cdot 5\)
Question 9
The LCM of two integers \(a\) and \(b\) can be defined in equivalent ways:
- \(\operatorname{lcm}(a,b) = A \cup B\) (union of their prime factor multisets)
- The least positive integer divisible by both \(a\) and \(b\)
- If \(a = p_1^{\alpha_1}\cdots p_k^{\alpha_k}\) and \(b = p_1^{\beta_1}\cdots p_k^{\beta_k}\), then
\[
\operatorname{lcm}(a,b) = p_1^{\max(\alpha_1,\beta_1)}\cdots p_k^{\max(\alpha_k,\beta_k)}.
\]
Problem:
Find \(\operatorname{lcm}(2^5\cdot 3^4\cdot 5^2\cdot 7,\ 2^3\cdot 3^7\cdot 5\cdot 11^2)\).
Problem:
Find \(\operatorname{lcm}(2^5\cdot 3^4\cdot 5^2\cdot 7,\ 2^3\cdot 3^7\cdot 5\cdot 11^2)\).
Pilihan Jawaban
- A. \(2^5\cdot 3^7\cdot 5^2\cdot 7\cdot 11^2\)
- B. \(2^5\cdot 3^7\cdot 5\cdot 7\cdot 11^2\)
- C. \(2^3\cdot 3^4\cdot 5^2\cdot 7\cdot 11^2\)
- D. \(2^5\cdot 3^7\cdot 5^2\cdot 11^2\)
解 Lihat Solusi
Step 1 → Ambil eksponen maksimum untuk setiap prima:
- 2: \(\max(5,3)=5\)
- 3: \(\max(4,7)=7\)
- 5: \(\max(2,1)=2\)
- 7: \(\max(1,0)=1\)
- 11: \(\max(0,2)=2\)
Step 2 → Jadi
\[
\operatorname{lcm} = 2^5 \cdot 3^7 \cdot 5^2 \cdot 7 \cdot 11^2.
\]
Jawaban: A
Question 10
Lemma:
If \( a \mid c \) and \( b \mid c \), then \( \operatorname{lcm}(a,b) \mid c \).
Lemma (Product of GCD and LCM): \[ \gcd(a,b) \cdot \operatorname{lcm}(a,b) = ab. \]
Problem: Given that \( \gcd(a,b) = 15 \) and \( ab = 1800 \), find \( \operatorname{lcm}(a,b) \).
Lemma (Product of GCD and LCM): \[ \gcd(a,b) \cdot \operatorname{lcm}(a,b) = ab. \]
Problem: Given that \( \gcd(a,b) = 15 \) and \( ab = 1800 \), find \( \operatorname{lcm}(a,b) \).
Pilihan Jawaban
- A. 120
- B. 150
- C. 180
- D. 200
解 Lihat Solusi
Step 1 → Dari lemma:
\[
\gcd(a,b) \cdot \operatorname{lcm}(a,b) = ab
\]
Step 2 → Substitusi nilai yang diketahui:
\[
15 \cdot \operatorname{lcm}(a,b) = 1800 \implies \operatorname{lcm}(a,b) = \dfrac{1800}{15} = 120.
\]
Jawaban: A. 120
Baca juga dalam seri Divisibility Olimpiade Matematika: