Salah satu materi yang diujikan pada Olimpiade Sains Nasional (OSN) [sekarang dikenal dengan nama Kompetisi Sains Nasional] teori bilangan. Pada OSN tahun 2008 yang diselenggarakan di Makasar pada tanggal 8-14 Agustus, soal materi teori bilangan yang diujikan berhubungan dengan keterbagian. Pada artilkel ini, diberikan soal dan pembahasan soal OSN 2008 hari kedua soal teori bilangan.

[latexpage]

Soal

Misalkan $m,n>1$ bilangan-bilangan bulat sedemikian sehingga $n$ membagi $4^{m}-1$ dan $2^{m}$ membagi $n-1$.

Haruskah $n=2^{m}+1$ ? Jelaskan.

OSN 2008 Hari Kedua Soal Teori Bilangan

Pembahasan

Diketahui $m,n>1$ bilangan-bilangan bulat dan memenuhi
\begin{equation*}
n\mid 4^{m}-1~~\text{dan}~2^{m}\mid n-1
\end{equation*}
Apakah harus $n=2^{m}+1$ ?

Claim: $n=2^{m}+1$.

Diperhatikan bahwa
\begin{equation*}
2^{m}\mid n-1
\end{equation*}
artinya terdapat bilangan asli $k$ sehingga $n-1=k2^{m}$
Akan dibuktikan bahwa $k=1$.

Diperhatikan bahwa
\begin{equation*}
\begin{split}
n&\mid 4^{m}-1\\
k2^{m}+1&\mid 4^{m}-1\\
k2^{m}+1&\mid k2^{m}+1\\
k2^{m}+1&\mid k(4^{m}-1)-2^{m}(k2^{m}+1)\\
k2^{m}+1&\mid k4^{m}-k-k4^{m}-2^{m}\\
k2^{m}+1&\mid k-2^{m}\\
k2^{m}+1&\mid k+2^{m}\\
\end{split}
\end{equation*}
Diperoleh
\begin{equation*}
\begin{split}
k2^{m}+1&\leq k+2^{m}\\
2^{m}(k-1)+(1-k)&\leq 0\\
(k-1)(2^{m}-1)&\leq 0
\end{split}
\end{equation*}
Karena $m>1$, maka $2^{m}-1>0$. Jadi haruslah $k-1\leq 0$, atau dengan kata lain $k\leq 1$. Karena $k\in \mathbb{N}$, diperoleh $k=1$. Jadi haruslah $n=2^{m}+1$.