Pembahasan Soal Teori Bilangan Russian Mathematical Olympiad 1999
Soal. Buktikan bahwa setiap bilangan asli dapat dituliskan sebagai selisih dua bilangan asli yang
mempunyai faktor-fakor prima sama banyaknya.
Diskusi Pendahuluan.
Maksud dari soal di atas adalah sebagai berikut. Misalkan $n$ adalah bilangan asli. Kita harus membuktikan bahwa
terdapat dua bilangan asli $u$ dan $w$, sehingga $n=u-w$,
dengan faktor prima prima dari $u$ sama banyaknya dengan faktor prima dari $w$.
Bukti.
Misalkan $n$ adalah bilangan asli. Menurut Teorema Dasar Aritmatika (Fundamental Theorem of Arithmatic),
terdapat bilangan asli $m$ sehingga
\begin{equation*}
n = p_{1}^{k_{1}} p_{2}^{k_{2}} \cdots p_{m}^{k_{m}}, \qquad (1)
\end{equation*}
dengan $p_{1}, p_{2}, \dots, p_{k}$ adalah bilangan-bilangan prima (saling berbeda), dan $ k_{1}, k_{2}, \dots, k_{m} $
adalah bilangan-bilangan asli. Notasi (1) menyatakan bahwa terdapat sebanyak $m$ faktor-faktor prima dari $n$.
Bukti terbagi menjadi dua kasus, pertama $n$ genap dan kedua $n$ ganjil.
Misalkan $n$ genap. Perhatikan bahwa $n=2n-n$. Selanjutnya, karena $n$ genap, maka salah satu faktor prima dari $n$
adalah $2$. Misalkan saja $p_1 = 2$. Dengan demikian, banyaknya faktor-faktor prima dari $n$ adalah $m$. Selanjutnya, perhatikan
bahwa, menurut (1), diperoleh
\begin{equation*}
2n = 2p_{1}^{k_{1}} p_{2}^{k_{2}} \cdots p_{m}^{k_{m}} = 22^{k_{1}} p_{2}^{k_{2}} \cdots p_{m}^{k_{m}}
= 2^{k_{1}+1} p_{2}^{k_{2}} \cdots p_{m}^{k_{m}} = p_{1}^{k_{1}+1} p_{2}^{k_{2}} \cdots p_{m}^{k_{m}}.
\end{equation*}
Hal ini berarti, faktor-faktor prima dari $2n$ juga sebanyak $m$. Jadi, soal terbukti untuk kasus ini.
Misalkan $n$ ganjil dan $d$ adalah bilangan prima ganjil terkecil sehingga $ d $ tidak membagi $n$, yaitu $ d \nmid n $ (eksistensi
$d$ dijamin oleh Well Order Property of Natural Numbers). Berarti $d \neq p_{i}$, untuk setiap $ i = 1, 2, \dots, m $.
Akibatnya $dn$ mempunyai faktor-faktor prima sebanyak $m+1$, karena
\begin{equation*}
nd = dp_{1}^{k_{1}} p_{2}^{k_{2}} \cdots p_{m}^{k_{m}} = p_{1}^{k_{1}} p_{2}^{k_{2}} \cdots p_{m}^{k_{m}}d^{1} = p_{1}^{k_{1}} p_{2}^{k_{2}} \cdots p_{m}^{k_{m}}p_{m+1}^{k_{m+1}}, \quad p_{m+1} = d, k_{m+1} = 1.
\end{equation*}
Selanjutnya, karena $d$ ganjil, maka $d-1$ genap. Hal ini berarti $2$ merupakan salah satu faktor prima dari $d-1$.
Sekarang, misalkan $q$ faktor prima ganjil dari $d-1$. Hal ini berarti $q\le d-1 < d $. Dengan demikian, menurut
definisi $d$, haruslah $ q | d $. Oleh karena itu, 2 adalah satu-satunya faktor prima $d-1$ yang bukan faktor prima dari $d$.
Diperoleh $(d-1)n$ hanya mempunyai sebanyak $m+1$ faktor-faktor prima. Karena $n=(dn)-((d-1)n)$, maka solah terbukti. QED
Komentar
Posting Komentar