Catatan si Jay

Oktober 18, 2010

Obat Ngantuk Konsep Modulus 1

Filed under: Matematika, Puzzle, Teori Bilangan — Hendra Jaya @ 5:29 am

Problem

Buktikan bahwa {2222}^{5555}+{5555}^{2222} habis dibagi 7.

Sumber : Seleksi Tim Olimpiade Matematika Indonesia 1997

Pra-Pembahasan 1

Menurut algoritma pembagian, a=d.q+r dengan 0\leq r<|d|
Jika kita nyatakan sisa pembagian a oleh d sebagai mod(a,d) maka r=mod(a,d)

Salah satu sifat dalam fungsi mod(a, d) adalah sifat distributif-asosiatif, sebagai berikut:

\begin{array}{clllclcr}a&=&d&.&q_1&+&r_1\\b&=&d&.&q_2&+&r_2\\---&-&-&-&----&-&----&+\\a+b&=&d&.&(q_1+q_2)&+&(r_1+r_2)\end{array}

Karena r_1+r_2 mungkin lebih besar dari d, maka :

r_1+r_2=d.q_3+r_3

Sehingga

\begin{array}{lllllll}a+b&=&d&.&(q_1+q_2)&+&(r_1+r_2)\\a+b&=&d&.&(q_1+q_2)&+&d.q_3+r_3\\a+b&=&d&.&(q_1+q_2+q_3)&+&r_3\end{array}

Sekarang, karena

r_1=mod(a,d)
r_2=mod(b,d)
r_3=mod(a+b,d) dan
r_3=mod(r_1+r_2,d)

Maka mod(a+b,d)=mod(mod(a,d)+mod(b,d), d)
Dengan cara yang sama juga kita peroleh mod(a.b,d)=mod(mod(a,d).mod(b,d), d).

Perhatikan bahwa dalam algoritma pembagian, a dikatakan habis dibagi oleh d jika dan hanya jika r=0 atau mod(a,d)=0.

Pra-Pembahasan 2

Menurut Binomial Newton :

\begin{array}{lll}a&=&d.q+r\\a^b&=&(d.q+r)^b\\a^b&=&k_0.d^b.q^b.r^0+k_1.d^{b-1}.q^{b-1}.r^1+k_2.d^{b-2}.q^{b-2}.r^2+...+k_{b-2}.d^2.q^2.r^{b-2}+k_{b-1}.d^1.q^1.r^{b-1}.q+k_b.d^0.q^0.r^b\\a^b&=&k_0.d^b.q^b.r^0+k_1.d^{b-1}.q^{b-1}.r^1+k_2.d^{b-2}.q^{b-2}.r^2+...+k_{b-2}.d^2.q^2.r^{b-2}+k_{b-1}.d^1.q^1.r^{b-1}.q+k_b.r^b\end{array}

Semua suku, kecuali suku ke-b (terakhir), memiliki d sebagai faktor.
Ini memberikan kita kesimpulan bahwa semua suku, kecuali suku ke-b, habis dibagi oleh d.

Karena semua suku, kecuali suku ke-b, habis dibagi oleh d, maka sisa pembagian a^b oleh d bergantung sepenuhnya kepada suku ke-b.

Nilai dari suku ke-b adalah :

\begin{array}{llll}U(b)&=&k_b.r^b\\U(b)&=&C(b,b).r^b\\U(b)&=&1.r^b\\U(b)&=&r^b\end{array}

Dengan demikian sisa bagi a^b oleh d bergantung sepenuhnya kepada r^b dimana r adalah sisa bagi a oleh d. Secara matematis :

\begin{array}{lllclllr}a&=&d.q_1+r&\text{ alias }&a&\equiv&r&\text{(modulo d)}\\a^b&=&d.q_2+r^b&\text{ alias }&a^b&\equiv&r^b&\text{(modulo d)}\end{array}

Pembahasan

Sisa bagi {2222}^{5555}+{5555}^{2222} oleh 7 dapat dinyatakan sebagai :

mod({2222}^{5555}+{5555}^{2222},7)=mod(mod({2222}^{5555},7)+mod({5555}^{2222},7),7)

Bagian 1 : Mencari nilai mod({2222}^{5555},7) :

Karena

{2222}^{5555}={(7.317+3)}^{5555}

Maka

mod({2222}^{5555},7)=mod({3}^{5555},7)

Karena

\begin{array}{lll}{3}^{5555}&=&3.{3}^{5554}\\&=&3.{(3^2)}^{2777}\\&=&3.{9}^{2777}\\&=&3.{(7.1+2)}^{2777}\end{array}

Maka

mod({3}^{5555},7)=mod(3.mod({2}^{2777},7),7)

Karena

\begin{array}{lll}{2}^{2777}&=&{2}^{2}.{2}^{2775}\\&=&4.{(2^3)}^{925}\\&=&4.{(2^3)}^{925}\\&=&4.{8}^{925}\\&=&4.{(7.1+1)}^{925}\end{array}

Maka

\begin{array}{lll}mod({2}^{2777},7)&=&mod(4.mod({1}^{925},7),7)\\&=&mod(4.mod(1,7),7)\\&=&mod(4.1,7)\\&=&mod(4,7))\\&=&4\end{array}

Sehingga

\begin{array}{lll}mod({3}^{5555},7)&=&mod(3.mod({2}^{2777},7),7)\\&=&mod(3.4,7)\\&=&mod(12,7)\\&=&5\end{array}

Sehingga

\begin{array}{lll}mod({2222}^{5555},7)&=&mod({3}^{5555},7)\\&=&5\end{array}

Bagian 2 : Mencari nilai mod({5555}^{2222},7) :

Karena

{5555}^{2222}={(7.793+4)}^{2222}

maka

mod({5555}^{2222},7)=mod({4}^{2222},7)

Karena

\begin{array}{lll}{4}^{2222}&=&4^2.{4}^{2220}\\&=&16.{(4^3)}^{740}\\&=&16.{64}^{740}\\&=&16.{(7.9+1)}^{740}\end{array}

maka

\begin{array}{lll}mod({4}^{2222},7)&=&mod(16.mod({1}^{740},7),7)\\&=&mod(16.mod(1,7),7)\\&=&mod(16.1,7)\\&=&mod(16,7)\\&=&2\end{array}

Sehingga

\begin{array}{lll}mod({5555}^{2222},7)&=&mod({4}^{2222},7)\\&=&2\end{array}

Kesimpulan

\begin{array}{lll}mod({2222}^{5555}+{5555}^{2222},7)&=&mod(mod({2222}^{5555},7)+mod({5555}^{2222},7),7)\\&=&mod(5+2,7)\\&=&mod(7,7)\\&=&0\end{array}

Dengan demikian sisa bagi dari {2222}^{5555}+{5555}^{2222} oleh 7 adalah 0. Alias {2222}^{5555}+{5555}^{2222} habis dibagi oleh 7.

Mathematician Steroids

Tinggalkan sebuah Komentar »

Belum ada komentar.

RSS feed for comments on this post. TrackBack URI

Tinggalkan Balasan

Isikan data di bawah atau klik salah satu ikon untuk log in:

Logo WordPress.com

You are commenting using your WordPress.com account. Logout / Ubah )

Gambar Twitter

You are commenting using your Twitter account. Logout / Ubah )

Foto Facebook

You are commenting using your Facebook account. Logout / Ubah )

Foto Google+

You are commenting using your Google+ account. Logout / Ubah )

Connecting to %s

Blog di WordPress.com.

%d blogger menyukai ini: