What is the remainder when 2^87 +3 is divided by 7?

[brucejin]

What is the remainder when 2^87 +3 is divided by 7?

How to start? 2^87 is a huge number. Do I have to calculate it?

Thanks.

 

[Deleted member 4993]

What is the remainder when 2^87 +3 is divided by 7?

How to start? 2^87 is a huge number. Do I have to calculate it?

Thanks.

List about first 12 powers (2^(12) + 3) - you would see a pattern. Depending on the level of math - you may have to prove your inference.

 

[DrMike]

What is the remainder when 2^87 +3 is divided by 7?

How to start? 2^87 is a huge number. Do I have to calculate it?

Thanks.

No.

The key insight for this kind of question is that

"remainder when A x B is divided by Z"

is the same as

"remainder when (remainder when A is divded by Z) x (remainder when B is divided by Z) is divided by Z"

Let me make this slightly less confusing with an example...

67 x 23 = 1541. When this is divided by 15, the remainder is 11. But we didn't have to multiply the numbers out to discover this.
Instead :
* 67, when divided by 15, gives a remainder of 7.
* 23, when divided by 15, gives a remainder of 8.
* 7 x 8 = 56.
* 56, when divided by 15, gives a remainder of 11, just like 1541 does.

A similar rule applies when you add numbers : The remainder when 67+23 is divided by 15 can be worked out without actually adding 67 and 23, just by adding their remainders instead.

Look up Modular Arithmetic on the net.

Now, I'll do a similar question to yours. I'll find the remainder when 5^107 is divided by 13.

* First, I'll note that 5x5x5x5 = 13x48 + 1. So if I divide 5^4 by 13, the remainder is 1.
* Next, I'll note that 107 = 104+3, so 5^107 = 5^104 x 5^3
* Next, I'll note that 5^104 = (5^4)^26.
* The remainder when I divide 5^4 by 13 is 1, so if I divide (5^4)^26 by 13, the remainder is 1x1x1x1x...x1 = 1^26 = 1.
* So, the remainder when I divide 5^107 by 13 is the same as if I divide 1x125 by 13, that is, 8.

Just to check, I'll use some software to work it out the hard way...

$ maxima
Maxima 5.12.99rc2 [url]http://maxima.sourceforge.net[/url]
Using Lisp CLISP 2.41 (2006-10-13)
Distributed under the GNU Public License. See the file COPYING.
Dedicated to the memory of William Schelter.
This is a development version of Maxima. The function bug_report()
provides bug reporting information.
(%i1) 5^107;
(%o1) 
    616297582203915472977912941627176741932192527428924222476780414581298828125
(%i2) mod(%,13);
(%o2)                                  8

and again...

$ python
Python 2.4.3 (#1, May 24 2008, 13:57:05) 
[GCC 4.1.2 20070626 (Red Hat 4.1.2-14)] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> pow(5,107) % 13;
8L
>>>

 

[soroban]

Hello, brucejin!

Subhotosh has the best approach . . .

\(\displaystyle \text{What is the remainder when }\,2^{87} +3\,\text{ is divided by 7?}\)

\(\displaystyle \text{Crank out the first few values of }\,2^n + 87\,\text{ and divide by 7}\)

. . \(\displaystyle \begin{array}{|c|c|c|} \hline n & 2^n+3 & \text{remainder} \\ \hline 0 & 4 & 4 \\ 1 & 5 & 5 \\ 2 & 7 & 0 \\ 3 & 11 & 4 \\ 4 & 19 & 5 & 5 & 35 & 0 \\ 6 & 67 & 4 \\ \vdots & \vdots & \vdots \end{array}\)


\(\displaystyle \text{The remainders loop throutgh a 3-step cycle: }\:4\text{-}5\text{-}0, \: 4\text{-}5\text{-}0, \: \hdots\)

\(\displaystyle \text{Since }\,87 \div 3\,\text{ has remainder 0, the remainder of }\,\left(2^{87} + 3\right) \div 7\)
. . \(\displaystyle \text{is the same as the remainder of }\,\left(2^0 + 3\right) \div 7\)

\(\displaystyle \text{Therefore: }\:\left(2^{87}{ + 3) \div 7 \quad\Rightarrow\quad \text{rem. }4\)