Lima digit terakhir dari 15 berpangkat

Tadi siang saat mengawas ujian Statprob, saya mengerjakan soal olimpiade tingkat SMP yang namanya SASMO yang saya tidak tahu kepanjangannya. Kalau kata Google sih SASMO: Singapore and Asian Schools Math Olympiad. Salah satu soalnya adalah sebagai berikut.

Soal. Tentukan lima digit terakhir dari 15^{2015}.

Jawaban:

Perhatikan bahwa

\displaystyle (10+5)^{2015} = \sum_{k=0}^{2015} {2015 \choose k} 10^k \cdotp 5^{2015}-k.

Dengan demikian, cukup dicari lima digit terakhir dari bilangan-bilangan berikut:

\displaystyle {2015 \choose 0} 5^{2015}

\displaystyle {2015 \choose 1} 10 \cdotp 5^{2014}

\displaystyle {2015 \choose 2} 10^2 \cdotp 5^{2013}

\displaystyle {2015 \choose 3} 10^3 \cdotp 5^{2012}

\displaystyle {2015 \choose 4} 10^4 \cdotp 5^{2011}

karena suku-suku penjumlahan yang lain hanya berkontribusi 00000 pada lima digit terakhirnya. Perhatikan bahwa jika kita dapat menghitung lima digit terakhir dari 5^{2011}, maka digit-digit 5^k untuk k=2012,2013,2014,2015 dapat kita dapatkan dengan mudah. Sekarang, kita cukup cari lima digit terakhir dari 5^{2011}. Ini berarti, kita mencari $m$ demikian sehingga

10^5|5^{2011}-k.

Namun, karena 5^5|5^{2011}, haruslah 5^5|k. Misalkan k=5^5\ell. Dengan demikian, kita cukup mencari \ell sehingga

2^5|5^{2006}-\ell.

Dengan Teorema Euler, berlaku 2^5|5^{16}-1 sehingga 2^5|5^{2000}-1. Jadi, 2^5|5^{2006}-5^6. Jadi, 10^5|5^{2011}-5^{11}. Mudah dihitung bahwa lima digit terakhir dari 5^{11} adalah 28215.

Sekarang, hanya masalah komputasi saja untuk mencari lima digit terakhir dari masing-masing suku di atas

\displaystyle {2015 \choose 4} 10^4 \cdotp 5^{2011} memiliki hasil (mod 100000): 50000

\displaystyle {2015 \choose 3} 10^3 \cdotp 5^{2012} memiliki hasil (mod 100000): 29455 \cdotp 1000 \cdotp 41075 = 25000

\displaystyle {2015 \choose 2} 10^2 \cdotp 5^{2013} memiliki hasil (mod 100000): 29105 \cdotp 100 \cdotp 05375 = 37500

\displaystyle {2015 \choose 1} 10 \cdotp 5^{2014} memiliki hasil (mod 100000): 2015 \cdotp 10 \cdotp 26875 = 31250

\displaystyle {2015 \choose 0} 5^{2015} memiliki hasil (mod 100000): 34375.

Jadi, lima digit terakhirnya adalah

50000+25000+37500+31250+34375 \pmod{100000} \equiv 78125.

Refleksi.

Soalnya lumayan seru, namun solusi saya sepertinya kurang “elementer” untuk anak SMP karena ada bagian yang memerlukan Teorema Euler. Memang biasanya sih anak SMP biasanya soalnya mencari pola-pola atau dengan mencoba. Namun, sepertinya sulit sekali untuk memperoleh bahwa 2^5|5^6-1.

Di luar ini, soalnya menarik sekali, terutama di bagian yang membutuhkan ekspansi binomial untuk membuang 10^k dengan k \ge 5.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s