Sign in to follow this  
-_-

Simulasi OSN TOSKA 2016 Nomor 4 - 69

Recommended Posts

Pemilihan angkanya unik :-)

Spoiler

Diberikan $a$ bilangan asli. Untuk setiap $x$ bilangan bulat ganjil, ada $n$ bil asli shg $2^a \mid{n^n-x}$.

 

Bukti:

Misalkan kebenaran pernyataan disimbolkan $P(a)$ untuk setiap $a\in{Z^+}$. Akan dibuktikan $P(a)$ benar $\iff P(a-1)$ benar untuk setiap $a\ge 2$.

 

Misalkan $n=2^{a-1}.k+p$ dg $k$ sebarang bil bulat non negatif dan $p$ bil asli. Kita punya dari binomial newton:

$n^n = 2^{2a-2}.D+C^{n}_1.2^{a-1}.k.p^{n-1}+p^n$ (mis $D$ suatu bil)

$\equiv (2^{a-1}.k+p).2^{a-1}.k.p^{n-1}+p^n (mod 2^a)$ (karena $2a-2\ge a$, sehingga $2^{2a-2} \equiv 0 (mod 2^a)$)

$\equiv \left( 2^{a-1}.k+1 \right).p^n (mod 2^a)$.

 

Perhatikan bahwa $P(a)$ benar jika dan hy jika $p$ ganjil, jadi $FPB(p,2^a)=1$. Menurut Fermat, $p^{phi{2^a} \equiv 1 (mod 2^a} \iff p^{2^{a-1}} \equiv 1 (mod 2^a)$.

Jadi $p^n \equiv p^p (mod 2^a)$ dan $n^n \equiv \left( 2^{a-1}.k+1 \right).p^p (mod 2^a)$.

 

Sehingga pernyataan $2^a \mid{n^n-x}$ ekuivalen dg:

$2^a \mid{(2^{a-1}.k+1).p^p-x}$

$\iff 2^a \mid{2^{a-1}.k.p^p+(p^p-x)}$.

Perhatikan bahwa ini berakibat ada $p$ bil asli shg $2^{a-1}\mid{p^p-x} \iff P(a-1) benar$; sedangkan jika $P(a-1)$ benar: 1. $p$ dipastikan bernilai ganjil (modulo $2$ untuk $a-1 \ge 1$), 2. misalkan $p^p-x=b.2^{a-1}$, set $k \equiv b (mod 2)$. Jadi $2^{a} \mid{2^{a-1}(k.p^p+b}} = 2^{a-1}.k.p^p+(p^p-x)$.

Terbukti bahwa $P(a)$ benar jika dan hy jika $P(a-1)$ benar. Jelas $P(a)$ benar sepenuhnya hanya jika $P(1)$ benar, yg jelas benar (ambil saja $n=1$). Jd pernyataan terbukti

Secara particular untuk $x=69$ ada $n in Z^+$ memenuhi soal. CMIIW.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this