Pembahasan OSN 2008

Published by iwan.ernanto on

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.

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.

Categories: Soal
Tags:

0 Comments

Leave a Reply

Avatar placeholder

Your email address will not be published.

Related Posts

Soal

Pembahasan OSN 2008

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 Read more…

Soal

Pembahasan OSN 2008

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 Read more…