Obat Ngantuk Konsep Modulus 1

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}$