- #1
san_1420
- 10
- 0
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.
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.