finding remainder of a division

**hunkydory19** · February 17th 2008, 04:59 AM

Find the remainder of the division of $23^{666342}$ by $49$

Could someone please explain how I would do this without a calculator??

Thanks in advance!

**TriKri** · February 17th 2008, 06:38 AM

$23^{666342} = (23^{333171})^2$
$23^{333171} = (23^{166585})^2\cdot 23$
$23^{166585} = (23^{83292})^2\cdot 23$
$23^{83292} = (23^{41646})^2$
$23^{41646} = (23^{20823})^2$
$23^{20823} = (23^{10411})^2\cdot 23$
...
and so on until you have come down to $23^1$ , is one way. Then you will have to work your way up again, but use the modulus rule $a\cdot b\ (mod\ x) = (a\ (mod\ x))\cdot (b\ (mod\ x))$ this time to get the values in the interval $[0, 49)$ .

Another way is to make a table over modulus values for different exponents of 23.

$23^1\ (mod\ 49) = 23$
$23^2\ (mod\ 49) = 23^1\cdot 23\ (mod\ 49) = 23\cdot 23\ (mod\ 49) = 39$
$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 $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 $2^{666342}$ .

**Soroban** · February 17th 2008, 07:45 AM

Hello, hunkydory19!

Find the remainder of the division of $23^{666342}$ by $49$

There is a rather primitive method for solving these . . .
. . (I'll omit a LOT of the trial-and-error that I used.)

We try: . $23^7 \:=\:3,404,825,497$

. . Then: . $3,404,825,497 \;=\;(49)(69,486,233) + 30$

Hence: . $23^7 \;=\;49a + 30$

Then: . $23^{14} \;=\;(23^7)^2$

. . . . . . . . $=\;(49a + 30)^2$

. . . . . . . . $=\;49^2a^2 + 60\!\cdot\!49a + 900$

. . . . . . . . $= \;49^2a^2+60\!\cdot\!49a + (49)(14) + 18$

. . . . . . . . $= \;49(49a^2 + 60a + 14) + 18$

Hence: . $23^{14} \;=\;49b + 18$

Then: . $23^{21} \;=\;(23^7)(23^{14})$

. . . . . . . . $= \;(49a + 30)(49b + 18)$

. . . . . . . . $= \;49^2ab + 18\!\cdot\!49a + 30\!\cdot\!49b + 540$

. . . . . . . . $= \;49^2ab + 18\!\cdot\!49a + 30\!\cdot\!49b + (49)(11) + 1$

. . . . . . . . $= \;49(49ab + 18a + 30b + 11) + 1$

Hence: . $23^{21} \;=\;49c + 1$

That is: . $23^{21} \div 49$ has a remainder of 1.

Then: . $23^{666342} \;=\;23^{666330}\cdot23^{12} \;=\;(23^{21})^{31730}(23^{12})\;\to \;1^{31730}\cdot23^{12} \:=\:23^{12}$

Now go to work on $23^{12}$

. . [Hint: . $23^4 \:=\:49k + 2$ ]

**galactus** · February 17th 2008, 07:48 AM

There are 21 mod 49 residues.

We note that $666342\equiv{12(mod \;\ 21)}$

This tells us that 666342 is 12 more than a multiple of 21.

So, $23^{666342}=23^{12}\equiv{8(mod \;\ 49)}$

The remainder is 8.

**TriKri** · February 17th 2008, 08:15 AM

Soroban, why did you choose 7 as an exponent? And galactus, how did you know that there are 21 mod 49 residues? Are there any quick ways?

Thread: finding remainder of a division

LinkBack

Thread Tools

Display

finding remainder of a division

Similar Math Help Forum Discussions

Division and remainder

Remainder with polynomial division

The remainder of integer division

Division & Remainder of Polynomials - please need help

Finding remainder of polynomial division

Search Tags