Find the remainder of the division of $\displaystyle 23^{666342}$ by $\displaystyle 49$
Could someone please explain how I would do this without a calculator??
Thanks in advance!
$\displaystyle 23^{666342} = (23^{333171})^2$
$\displaystyle 23^{333171} = (23^{166585})^2\cdot 23$
$\displaystyle 23^{166585} = (23^{83292})^2\cdot 23$
$\displaystyle 23^{83292} = (23^{41646})^2$
$\displaystyle 23^{41646} = (23^{20823})^2$
$\displaystyle 23^{20823} = (23^{10411})^2\cdot 23$
...
and so on until you have come down to $\displaystyle 23^1$, is one way. Then you will have to work your way up again, but use the modulus rule $\displaystyle a\cdot b\ (mod\ x) = (a\ (mod\ x))\cdot (b\ (mod\ x))$ this time to get the values in the interval $\displaystyle [0, 49)$.
Another way is to make a table over modulus values for different exponents of 23.
$\displaystyle 23^1\ (mod\ 49) = 23$
$\displaystyle 23^2\ (mod\ 49) = 23^1\cdot 23\ (mod\ 49) = 23\cdot 23\ (mod\ 49) = 39$
$\displaystyle 23^3\ (mod\ 49) = 23^2\cdot 23\ (mod\ 49) = 39\cdot 23\ (mod\ 49) = 15$
...
and so on. Eventually, you will get the same modulu value as you have had before, then you know that the modulu values will begin to repeat. When you have found the period of repetition (in this case $\displaystyle 23^{22}\equiv 23^1\ (mod\ 49)$, so the period will be 21), you can calculate which of the exponents in your table that has the same modulu value as $\displaystyle 2^{666342}$.
Hello, hunkydory19!
There is a rather primitive method for solving these . . .Find the remainder of the division of $\displaystyle 23^{666342}$ by $\displaystyle 49$
. . (I'll omit a LOT of the trial-and-error that I used.)
We try: .$\displaystyle 23^7 \:=\:3,404,825,497$
. . Then: .$\displaystyle 3,404,825,497 \;=\;(49)(69,486,233) + 30$
Hence: .$\displaystyle 23^7 \;=\;49a + 30$
Then: .$\displaystyle 23^{14} \;=\;(23^7)^2$
. . . . . . . . $\displaystyle =\;(49a + 30)^2$
. . . . . . . . $\displaystyle =\;49^2a^2 + 60\!\cdot\!49a + 900 $
. . . . . . . . $\displaystyle = \;49^2a^2+60\!\cdot\!49a + (49)(14) + 18$
. . . . . . . . $\displaystyle = \;49(49a^2 + 60a + 14) + 18$
Hence: .$\displaystyle 23^{14} \;=\;49b + 18$
Then: .$\displaystyle 23^{21} \;=\;(23^7)(23^{14})$
. . . . . . . . $\displaystyle = \;(49a + 30)(49b + 18)$
. . . . . . . . $\displaystyle = \;49^2ab + 18\!\cdot\!49a + 30\!\cdot\!49b + 540$
. . . . . . . . $\displaystyle = \;49^2ab + 18\!\cdot\!49a + 30\!\cdot\!49b + (49)(11) + 1$
. . . . . . . . $\displaystyle = \;49(49ab + 18a + 30b + 11) + 1$
Hence: .$\displaystyle 23^{21} \;=\;49c + 1$
That is: .$\displaystyle 23^{21} \div 49$ has a remainder of 1.
Then: .$\displaystyle 23^{666342} \;=\;23^{666330}\cdot23^{12} \;=\;(23^{21})^{31730}(23^{12})\;\to \;1^{31730}\cdot23^{12} \:=\:23^{12}$
Now go to work on $\displaystyle 23^{12}$
. . [Hint: .$\displaystyle 23^4 \:=\:49k + 2$]