Soal Olimpiade Matematika SMA dan Pembahasan Tentang Teori Bilangan

1.      Misalkan M dan m berturut-turut menyatakan bilangan terbesar dan bilangan terkecil di antara semua bilangan 4-angka yang memuat jumlah keempat angkanya adalah 9. Berapakah faktor prima terbesar dari M – m ? (OSP Matematika SMA 2002)

Pembahasan :

Misal bilangan itu adalah : abcd

Agar abcd sebesar besarnya maka a harus sebesar-besarnya. Maka a = 9.

Karena a = 9, agar a + b + c + d = 9, maka b = 0 ; c = 0 ; d = 0. Maka M = 9000.

Agar a, b, c, dan d sekecil-kecilnya maka a harus sekecil-kecilnya dan karena a ≠ 0, maka a = 1.

b juga harus sekecil-kecilnya, maka b = 0.

c juga harus sekecil-kecilnya, maka c = 0.

Karena a + b + c + d = 9, maka d = 8. Akibatnya m = 1008.

M – m = 9000 – 1008 = 7992 = 8 . 999 = 8 . 27 . 37

M – m = 2³ . 3³ . 37

v Maka faktor prima terbesar dari M – m adalah 37.

2.      Berapakah sisa pembagian (43⁴³)⁴³ oleh 100 ? (OSP Matematika SMA 2002)

Pembahasan :

Karena 43⁴³ = (4 . 11 – 1)⁴³ maka 43⁴³ ≡ (-1)⁴³ (mod 4)

43⁴³ ≡ -1 (mod 4) ≡ 3 (mod 4)

Berarti 43⁴³ = 4k + 3 dengan k adalah bilangan asli.

(43⁴³)⁴³ ≡ 43^4k+3 ≡ (1849)^2k . 43³

(43⁴³)⁴³ ≡ (49)^2k . 43⁴³ (mod 100)

(43⁴³)⁴³ ≡ (2401)^k . 7 ( mod 100) sebab 43⁴³ ≡ 7 (mod 100)

(43⁴³)⁴³ ≡ 1^k . 7 (mod 100)

(43⁴³)⁴³ ≡ 7 (mod 100)

Karena (43⁴³)⁴³ ≡ 7 (mod 100) berarti (43⁴³)⁴³ ≡ 100p + 7 dengan p adalah bilangan asli.

v Maka (43⁴³)⁴³ jika dibagi 100 akan bersisa 7.

3.      Ada berapa banyak diantara bilangan-bilangan 20000002, 20011002, 20022002, 20033002 yang habis dibagi 9 ?

A.   0                   B. 1                                                   C. 2            D. 3                              E. 4

(OSK Matematika SMA 2003)

Pembahasan :

(Jawaban : A)

Teori : Sebuah bilangan bulat habis dibagi 9 jika jumlah digit bilangan tersebut habis dibagi 9.

Jumlah digit 20000002 = 2 + 0 + 0 + 0 + 0 + 0 + 0 + 2 = 4 (Tidak habis dibagi 9)

Jumlah digit 20011002 = 2 + 0 + 0 + 1 + 1 + 0 + 0 + 2 = 6 (Tidak habis dibagi 9)

Jumlah digit 20022002 = 2 + 0 + 0 + 2 + 2 + 0 + 0 + 2 = 8 (Tidak habis dibagi 9)

Jumlah digit 20033002 = 2 + 0 + 0 + 3 + 3 + 0 + 0 + 2 = 10 (Tidak habis dibagi 9)

v Jadi, banyaknya bilangan yang habis dibagi 3 adalah 0

4.      Misalkan k, m, n adalah bilangan-bilangan asli demikian, sehingga k > n > 1 dan faktor persekutuan terbesar k dan n sama dengan 1. Buktikan bahwa jika k – n membagi   k^m – n^m-1, maka k ≤ 2n – 1. (OSN Matematika SMA 2003)

Pembahasan :

k – n | k^m – n^m-1

k – n | k^m – n^m + n^m – n^m-1

k – n | k^m – n^m + n^m-1 (n – 1)

Untuk m ∈ bilangan asli maka k – n membagi k^m – n^m.

Karena FPB (k,n) = 1 maka FPB (k – n, n^m-1) = 1. Akibatnya k – n harus membagi n – 1.

Karena k – n membagi n – 1 maka k – n ≤ n – 1

k ≤ 2n – 1

v Terbukti bahwa k ≤ 2n – 1

5.      Misalkan a, b, c adalah bilangan-bilangan asli. Jika 30 | (a + b + c), buktikan bahwa 

       30 | (a⁵ + b⁵ + c⁵).

[Catatan : x | y menyatakan x habis membagi y.] (OSN Matematika SMA 2006)

Pembahasan :

Akan dibuktikan bahwa 30 ⏐ n⁵ − n untuk n bilangan asli.

n⁵ − n = n(n² − 1)(n² + 1) = n(n − 1)(n + 1)(n² − 4 + 5)

n⁵ − n = (n − 2)(n − 1)n(n + 1)(n + 2) + 5(n − 1)n(n + 1)

Karena n − 2, n − 1, n, n + 1, n + 2 adalah 5 bilangan bulat berurutan

Maka (n − 2)(n − 1)n(n + 1)(n + 2) habis dibagi 5! = 120

Sehingga 30 ⏐ (n − 2)(n − 1)n(n + 1)(n + 2)

Karena n − 1, n dan n + 1 adalah 3 bilangan bulat berurutan 

Maka 3! = 6 membagi (n −1)n(n + 1)

Akibatnya 30 ⏐ 5(n − 1)n(n + 1)

Maka 30 ⏐ n⁵ − n untuk n bilangan asli

30 ⏐ a⁵ − a + b⁵ − b + c⁵ − c untuk a, b, c bilangan asli

Maka 30 ⏐ a⁵ + b⁵ + c⁵ − (a + b + c)

v Karena 30 | (a + b + c) maka 30 | (a⁵ + b⁵ + c⁵) (terbukti)

6.      Misalkan m, n > 1 bilangan-bilangan bulat sedemikian hingga n membagi 4^m – 1 dan 2^m membagi n – 1. Haruskah n = 2^m + 1 ? Jelaskan. (OSN Matematika SMA 2008)

Pembahasan :

Karena 2^m⏐n − 1 maka n = k . 2^m + 1 untuk suatu bilangan asli k.

Karena n⏐4^m − 1 maka n ≤ 4^m – 1

k . 2^m + 1 ≤ 4^m − 1 < 4^m + 1

Maka k < 2^m .............................. (1)

Karena n⏐4^m − 1 maka n⏐(4^m −1) . k² = (k . 2^m)² − k²

Sehingga n⏐(n − 1)² − k² = n² − 2n + 1 − k²

Karena n⏐n² − 2n maka n⏐k² − 1. Jadi, n ≤ k² − 1 untuk k ≠ 1 .............................. (2)

n ≤ k² − 1 < k² < k . 2^m < k . 2^m + 1 = n kontradiksi untuk k ≠ 1

Jika k = 1 maka n = 2^m + 1 yang memenuhi 2^m⏐n − 1 dan n⏐4^m – 1

v Jadi, haruslah n = 2^m + 1

7.      Jika 10^999999999 dibagi oleh 7, maka sisanya adalah ... ( OSK Matematika SMA 2009)

Pembahasan :

10^999999999 = 1000^333333333 = (7 . 143 – 1)^333333333

10^999999999 ≡ (-1)^333333333 (mod 7) ≡ -1 (mod 7)

10^999999999 dibagi 7 maka akan bersisa 6

v 10^999999999 dibagi 7 akan bersisa 6.

8.  Misalkan d = FPB(7n + 5, 5n + 4), dimana n adalah bilangan asli.

(a)   Buktikan bahwa untuk setiap bilangan asli n berlaku d = 1 atau 3.

(b)   Buktikan bahwa d = 3 jika dan hanya jika n = 3k + 1, untuk suatu bilangan asli k.

Pembahasan :

d = FPB(7n + 5, 5n + 4)

a.    Maka d⏐7n + 5 dan d⏐5n + 4

Karena d membagi 7n + 5 maka d juga membagi 5(7n + 5)

Karena d membagi 5n + 4 maka d juga membagi 7(5n + 4)

Akibatnya d juga membagi 7(5n + 4) − 5(7n + 5) = 3

Karena d|3 maka d = 1 atau 3 (terbukti)

b.    Sebuah bilangan akan termasuk ke dalam salah satu bentuk dari 3k, 3k+1 atau 3k+2

Jika n = 3k maka 7n + 5 = 21k + 5 ≡ 2 (mod 3) dan 5n + 4 = 15k + 4 ≡ 1 (mod 3)

Jika n = 3k + 1 maka 7n + 5 = 21k + 12 ≡ 0 (mod 3) dan 5n + 4 = 15k + 9 ≡ 0 (mod 3)

Jika n = 3k + 2 maka 7n + 5 = 21k + 19 ≡ 1 (mod 3) dan 5n+4 = 15k+14 ≡ 2 (mod 3)

v Terbukti bahwa hanya bentuk n = 3k + 1 yang menyebabkan kedua bilangan   7n + 5 dan 5n + 4 habis dibagi 3 untuk n bilangan asli.