ok, let's try this:
1999 is 11111001111 in binary
or 1999=2^0+2^1+2^2+2^3+2^6+2^7+2^8+2^9+2^10 (go ahead, check it out, hehe)
So, 3^1999 = 3^(2^0+2^1+2^2+2^3+2^6+2^7+2^8+2^9+2^10)=
=3^2^0 * 3^2^1 * 3^2^2 * 3^2^3 * 3^2^6 * 3^2^7 * 3^2^8 * 3^2^9 * 3^2^10
ugh .. it looks better on paper
Now...
Now, a property of congruences is that you can multiply them... so that is, you can take each product individually, instead of taking all at once,
Also, (3^2^a)^2 = 3^2^(a+1)
(right associative)
Ok, mod 100 now
3^2^0 = 3 (mod 100)
3^2^1 = 9 (mod 100)
3^2^2 = (9)^2 (mod 100)= 81 (mod 100) = -19 (mod 100) [cuz 100 divides 81-(-19)=100
3^2^3 = (-19)^2 (mod 100)= 61 (mod 100) = -39
3^2^6 = (-39)^8 = 81 = -19
3^2^7 = (-19)^2 = -39
3^2^8 = (-39)^2= 21
3^2^9 = 21^2= 41
3^2^10 = 41^2=81=-19
so ... now,
3^1999 is congruent to 3*9*(-19)*(-39)*(-19)*(-39)*21*41*(-19)
Now, you could simplify it further using congruences, but I think most calculators will handle this
This equals to -242525234133 = -33 (mod 100) = 67 (mod 100)
So, drumroll .. the last 2 digits of 3^1999 is 67 !
or also
3*9*(-19)*(-39)*(-19)*(-39)*21*41*(-19)=
=3*9*(-19)^3*(-39)^2*21*41 =
=3*9*(-59)*21*21*41 (mod 100)
=27*41*21^2*41=27*41^2*21^2=27*(-19)*41=-21033=67 (mod 100)
this number any calc will handle
So, again 67.. phew ! :)
|
