SOLUTION: What is the remainder of dividing 2^70+3^70 over 13.

Click here to see ALL problems on Divisibility and Prime Numbers

Question 1200460: What is the remainder of dividing 2^70+3^70 over 13.
Found 2 solutions by MathLover1, math_tutor2020:
Answer by MathLover1(20850) (Show Source):
You can put this solution on YOUR website!

use calculator

so the remainder is

Answer by math_tutor2020(3817) (Show Source):
You can put this solution on YOUR website!

Answer: 0

===================================================================================================

Explanation:

I'll assume the following:
You are in a number theory class (or similar).
You are familiar with modular arithmetic.
You are familiar with exponent rules.
You are familiar with Fermat's Little Theorem (FLT).
That theorem says:
If p is prime and 'a' is any positive integer, then
a^p = a (mod p)

A slight modification of that theorem is:
a^(p-1) = 1 (mod p)
if and only if p is not a factor of 'a'.

I'll be using this second format to help compute 2^70 (mod 13) and 3^70 (mod 13).
These look at the remainders of (2^70)/13 and (3^70)/13

The ultimate goal is to find 2^70+3^70 (mod 13)

---------------------------------------------------------

In our case we have p = 13 as our modulus.
For 2^70, we have a = 2 as the base.
Using the 2nd version of FLT mentioned above, we can say:
a^(p-1) = 1 (mod p)
2^(13-1) = 1 (mod 13)
2^12 = 1 (mod 13)

This is extremely useful because 1 is a very easy number to work with in terms of exponents and multiplication.
Pay careful attention to the fact we did not calculate 2^12 to get some massive number. Same goes for 2^60 and so on.

Then,
2^60 = 2^(12*5) = (2^12)^5 = (1)^5 = 1 (mod 13)
in short
2^60 = 1 (mod 13)

Then multiply both sides by 2^4, aka 16
2^60 = 1 (mod 13)
2^4*2^60 = 2^4*1 (mod 13)
2^64 = 16 (mod 13)
2^64 = 3 (mod 13)

Repeat that step again. The goal is to have the exponent reach 70.
2^64 = 3 (mod 13)
2^4*2^64 = 2^4*3 (mod 13)
2^68 = 16*3 (mod 13)
2^68 = 3*3 (mod 13)
2^68 = 9 (mod 13)
I'm doing this in small chunks to avoid having massive results.

Then finally we need to multiply both sides by 2^2
2^68 = 9 (mod 13)
2^2*2^68 = 2^2*9 (mod 13)
2^70 = 36 (mod 13)
2^70 = 10 (mod 13)
We'll come back to this later.

Through similar steps, you should find that:
3^12 = 1 (mod 13)
(3^12)^5 = 1^5 (mod 13)
3^60 = 1 (mod 13)
and
3^4*3^60 = 3^4*1 (mod 13)
3^64 = 81 (mod 13)
3^64 = 3 (mod 13)
and
3^4*3^64 = 3^4*3 (mod 13)
3^68 = 3*3 (mod 13)
3^68 = 9 (mod 13)
and
3^2*3^68 = 3^2*9 (mod 13)
3^70 = 9*9 (mod 13)
3^70 = 81 (mod 13)
3^70 = 3 (mod 13)

-----------------------

Summary:
2^70 = 10 (mod 13)
3^70 = 3 (mod 13)

Then finally,
2^70+3^70 = 10+3 = 13 = 0 (mod 13)
in short
2^70+3^70 = 0 (mod 13)

It tells us that computing (2^70+3^70)/13 will get us some very large quotient (in which we do not care about) with remainder 0.

The following statements are equivalent and interconnected:
13 is a factor of 2^70+3^70.
2^70+3^70 is a multiple of 13.
13k = 2^70+3^70 for some integer k.
(2^70+3^70)/13 is some large integer.
(2^70+3^70)/13 leads to some quotient, and remainder 0.
You can use WolframAlpha to confirm the answer.

Further Reading:
https://mathworld.wolfram.com/FermatsLittleTheorem.html