1. ## Arithmetic Modular help!!

Hey guys, im trying to find the remainders when this number $\displaystyle (800)^{367}$ is divided into 73.

From my working out, i broke it down to

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

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

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

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

is this correct?

thanks!!

2. Any help or ideas guys?

3. Hello, jvignacio!

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

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

. . $\displaystyle \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: .$\displaystyle 800^2\cdot800^4 \;\equiv\;9\cdot8 \;\equiv\;72 \text{ (mod 73)}$

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

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

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

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

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

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

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

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