# Arithmetic Modular help!!

• Mar 24th 2010, 04:44 AM
jvignacio
Arithmetic Modular help!!
Hey guys, im trying to find the remainders when this number $(800)^{367}$ is divided into 73.

From my working out, i broke it down to

$(800)^{367}$ $= (800)^{24*15+7}$ $= (800^{24})^{15} * 800^7$

since $800^7 = (800^4 * 800^3)$ $\equiv$ 3 remainder (mod 73)
and since $800^{24} = (800^{12} * 800^{12})$ $\equiv$ 1 remainder (mod 73)

so then im left with $(800^{24})^{15} * 800^7 = 1^{15} *3$ Reminder (mod 73)

therefore:
$(800)^{367}$ $\equiv$ 3 Reminder (mod 73)

is this correct?

thanks!!
• Mar 24th 2010, 06:57 AM
jvignacio
Any help or ideas guys?
• Mar 24th 2010, 08:44 AM
Soroban
Hello, jvignacio!

I approached it differently.
(No surprise ... There must be brizillions of ways.)

Quote:

Find the remainder when $(800)^{367}$ is divided by 73.
I craniked out the first few powers of 800.

. . $\begin{array}{cccc} 800^1 & \equiv & 70 & \text{(mod 73)} \\
800^2 &\equiv& 9 & \text{(mod 73)} \\
800^3 &\equiv& 46 & \text{(mod 73)} \\
800^4 &\equiv & 8 & \text{(mod 73)} \end{array}$

Then I noted that: . $800^2\cdot800^4 \;\equiv\;9\cdot8 \;\equiv\;72 \text{ (mod 73)}$

Hence: . $800^6 \;\equiv\;-1\text{ (mod 73)}$

We have: . $800^{367} \;=\;800^{6(61)+1}$

. . . . . . . . . . . . $=\;800^{6(61)}\cdot800^1$

. . . . . . . . . . . . $=\;\left(800^6\right)^{61}\cdot800$

. . . . . . . . . . . . $\equiv \;(-1)^{61}\cdot 70 \text{ (mod 73)}$

. . . . . . . . . . . . $\equiv\;(-1)(70)\text{ (mod 73)}$

. . . . . . . . . . . . $\equiv\; -70\text{ (mod 73)}$

. . . . . . . . . . . . $\equiv\;3\text{ (mod 73)}$