last two digits of 2^999

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

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

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

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 [tex]\phi(100)=40[/tex] and [tex]4^{40n+k}\equiv4^{k}(mod 100)[/tex].
[tex]2^{999}\equiv2*4^{499}\equiv2*4^{40*12+19}\equiv2*4^{19}\equiv2^{39}\eq uiv2^{10}2^{10}2^{10}2^{9}\equiv24*24*24*12\equiv88(mod 100)[/tex]

whodsow

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