Why does Euler's Formula work for finding the remainder of 2^999 modulo 100?

[san_1420]

I was trying to find last two digits of 2^999
I proceeded like this
2=2 (mod 100)
2^2=2*2=4(mod 100)
2^4=4*4=16 (mod 100)
2^8=16*16=256=56 (mod 100)
2^16=56*56=3136=36 (mod 100)
2^32=36*36=96 = -4 (mod 100)
2^64=-4*-4 =16 (mod 100)
2^128=16*16=56 (mod 100)
2^256=56*56=36 (mod 100)
2^512=36*36=-4 (mod 100)

Therefore 2^999= 2^512 * 2^256 * 2^128 * 2^64 * 2^32 * 2^4 *2^2 * 2^1 (mod 100)

=-4*36*56*16*-4*16*4*2 (mod 100)
= 66060288
=88 (mod 100)
Problem is this if reduce 2^999 mod 25 I get
2^1 = 2 mod(25)
2^2 =4 mod(25)
2^4 =16 mod(25)
2^8 =6 mod(25)
2^16 =11 mod(25)
2^32 =21 mod(25)
2^64 =16 mod(25)
2^128 =6 mod(25)
2^256 =11 mod(25)
2^512 =21 mod(25)

2^999 = 21*11*6*16*21*16*4*2 (mod 25)=59609088
If I take remainder of 59609088/100 i get the same result as before.
Why does this work?That is I can reduce 2^999 mod 25 and take reminder of last number I obtain divided by 100
Again is there a simpler way of doing it?
I cannot use Euler as 2 and 100 are not co prime.

 

[matt grime]

It is just a coincidence - you have arbitrarily reduced things mod 25 and 100 when it suits you, and not consistently with regards to choices of remainders. Why did you use 21 and not -4, when you used -4 and not 96? (And if you still don't believe it was fluke, then evaluate 30^1 mod 100 and mod 25 to see you don't get the same things).Assuming everything is random, there was a one in 4 chance of this happening. 2^999 is 13 mod 25, thus if we pick some thing at random that is 13 mod 25, then there is a 1 in 4 chance it was 88 mod 100.

 

[san_1420]

Thanks a lot matt
Here's why I tried 25.
While I took all the pain to evaluate remainders of powers of 2.
A brainier guy suggested this.

2^999 = ((2^10)^99)*(2^9)

Now 2^10 =1024 = -1 (mod 25)
and 2^9=512=12 (mod 25)
2^299=-1*12=-12=13 (mod 25)

Now he suggested this
13 (mod 25) could be any of 13 or 13+25 or 13+50 or 13+75 (mod 100)
or any of 13,38,63,88 .(As you have already observed in your post)
And since 2^999 is exactly divisible by 4
Only choice could be 88
There is only one problem.How did he arrive at 25?
That's where I always get stumped.
Somebody always has an elegant solution to things I work out the hard way...

 

[matt grime]

Well, why not 25?

Have you heard of the chinese remainder theorem? That might tell you what you need to know...

 

[ramsey2879]

Thanks a lot matt
Here's why I tried 25.
While I took all the pain to evaluate remainders of powers of 2.
A brainier guy suggested this.

...
13 (mod 25) could be any of 13 or 13+25 or 13+50 or 13+75 (mod 100)
or any of 13,38,63,88 .(As you have already observed in your post)
And since 2^999 is exactly divisible by 4
Only choice could be 88
There is only one problem.How did he arrive at 25?
That's where I always get stumped.
Somebody always has an elegant solution to things I work out the hard way...

You already noted that 100 has powers of 2 in it which precludes using Euler, so divide 100 by 4 to get a mod that can be evaluated using Euler and used the fact that the result mod 100 must be divisible by 4.

 

[san_1420]

Well, why not 25?

Have you heard of the chinese remainder theorem? That might tell you what you need to know...

Yes I have heard of it.
It says that I can solve a series of modular equations provided moduli are prime to each other .The solution is unique to LCM of moduli.
But how do I arrive at conclusion that 25 is possible candidate??

 

[matt grime]

Let's think about this: the C.R.T. says that if I have X mod A and X mod B, where A and B are coprime, then I can find X mod AB. Now, I don't believe you cannot see how 100, 25 and 4 relate to A, B and AB.

 

[san_1420]

Let's think about this: the C.R.T. says that if I have X mod A and X mod B, where A and B are coprime, then I can find X mod AB. Now, I don't believe you cannot see how 100, 25 and 4 relate to A, B and AB.

I got it thanks...

 

[dodo]

I threw a few numbers out of the calculator, and noticed that 3^20 = 1 (mod 100).
Since 2^10 = 1024 = 2*3 . 3 (mod 100),
I found easier to use these two facts to reduce bigger powers to smaller ones.

In what follows, every time you see a 2^10, you can replace it by 2^3 . 3; and when you see a 2^30 (or a power of it), it can simply vanish.

Starting with 2^1000, you have
2^1000 = (2^3 . 3) ^ 100 = 2^300 . 3^100 = 2^300 (mod 100)
2^300 = (2^3 . 3) ^ 30 = 2^90 . 3^30 = (2^3 . 3) ^ 9 . 3^20 . 3^10 = 2^27 . 3^19 (mod 100)
Now
2^27 . 3^19 = 2^7 . (2^3 . 3) ^ 2 . 3^20 / 3 = 2^7 . 2^6 . 3^2 / 3 = 2^13 . 3 (mod 100)
So
2^999 = 2^1000 / 2 = 2^12 . 3 = 96 . 3 = 88 (mod 100)

 

[whodsow]

100 = 4 * 25, gcd(4, 25) = 1, so \phi(100)=40 and 4^{40n+k}\equiv4^{k}(mod 100).
2^{999}\equiv2*4^{499}\equiv2*4^{40*12+19}\equiv2*4^{19}\equiv2^{39}\equiv2^{10}2^{10}2^{10}2^{9}\equiv24*24*24*12\equiv88(mod 100)

 

[whodsow]

Why 4^{40n+k}\equiv4^{k}(mod\ 100)? this question is the same question as why the remainder of 2^{999} modulo 100 equals the remainder of 2^{999} modulo 25.
let m = pq with gcd(p, q) = 1, then \phi(m)=\phi(p)*\phi(q), let a is divisible by p and not by q, then gcd(a, q) = 1, according to Euler's Formula, we can get a^{n\phi(m)+k}\equiv a^{n\phi(p)\phi(q)+k}\equiv a^{k}(mod\ q), then a^{n\phi(m)+k}-a^{k} is divisible by q, since a is divisible by p, we also have a^{n\phi(m)+k}-a^{k} is divisible by p, since gcd(p, q) = 1, we get pq|a^{n\phi(m)+k}-a^{k}, in orther words a^{n\phi(m)+k}\equiv a^{k}(mod\ m)