I need to find the remainder of 2^70/96. I need to show my work so I can't just plug it into a calculator. Thanks

to start with, the prime factorization of 96 is 2^5 * 3. so it becomes the remainder of 2^65 / 3 => what is 2^65 mod 3

now take a look at the pattern of the power of 2s:
2^2 = 4 => 1 mod 3
when we double that, what happens to the remainder? well, we have 1 mod 3 + 1 mod 3 => 2 mod 3
so, 2^3 = 8 => 2 mod 3
when we double that, what happens to the remainder? well, we have 2 mod 3 + 2 mod 3 => 4 mod 3 => 1 mod 3
what happens when we double that? well, we just created a cycle. i assume you can take it from here

This post was edited by carteblanche on Oct 8 2015 06:57pm

If I'm understanding correctly, we're saying the remainder is 1?

if you understand correctly, you should be able to show your work. so show me your work.

This post was edited by carteblanche on Oct 8 2015 07:51pm

Ooooh I think I got it, the remainder is 2 right?

we can use your work above
"2^2 = 4 => 1 mod 3
when we double that, what happens to the remainder? well, we have 1 mod 3 + 1 mod 3 => 2 mod 3
so, 2^3 = 8 => 2 mod 3
when we double that, what happens to the remainder? well, we have 2 mod 3 + 2 mod 3 => 4 mod 3 => 1 mod 3"


i think the remainder will continue to alternate between 1 and 2 depending on the power of 2, if its even we get remainder 1 and if its odd we get remainder 2
because we have 2^65 we get remainder 2

This post was edited by rwarth on Oct 8 2015 08:27pm

Just have a look at that pattern :

2^0 = 1 , mod 96
2^1 = 2 , mod 96
2^2 = 4 , mod 96
2^3 = 8 , mod 96
2^4 = 16 , mod 96
2^5 = 32 , mod 96
2^6 = 64 , mod 96
2^7 = 32 , mod 96
2^8 = 64 , mod 96
2^9 = 32 , mod 96
...

Since 64 * 2 = 128 = 32 , mod 96, each time you multiply by 2, you alternate between 32 and 64 mod 96.

For every even integer n greater than 5, 2^n = 64, mod 96,
for every odd integer p greater than 4, 2^p = 32 , mod 96.

Hence 2^70 = 64 mod 96.

You need to multiply your answer by 2^5 to get 64 which is correct the answer. This is because when you reduced the fraction by cancelling 2^5, you also reduced the remainder by that factor.

Carteblanche's and feanur's answer are both great answers.
But heres another way you can answer this without using congruent modulo notation

You can rewrite your expression as
2^70 / (2^5 *3)
By cancelling
2^65/3

Now if we just look at the numbers 2 and 3, let's say the remainder of 2/3 is -1. (Works due to modular arithmetic)
Claim: The remainder of 2^65/3 is also -1

Proof: suppose we have ab/d
By the division theorem, we can write a=cd+r_1, and b=ed+r_2
For some integers c,e and for integers r_1,r_2 in [0,d)

Multiplying ab gives us
ab = cded + cdr_2 + r_1ed + r_1r_2
Factoring d from first three terms
ab = (cde + cr_2 + r_1e +)d + r_1r_2

So we see the remainder of ab/d is the remainder of a times the remainder of b. And thus of the remainder of 2^65/3 is the same as the remainder of 2/3 multiplied by itself 65 times. (-1)^65 = -1

But we need a positive remainder so we just add 3(our divisor) to our negative remainder (this also works due to modulo arithmetic)

-1 + 3 = 2
And now the final step of multiplying by 2^5 as reasoned in the first paragraph.

1+1=2