1. ## Last two digit

Find the last digit two digit of the expression?
(201 * 202 * 203 *204 * 246 * 247 * 248 * 249)^2.

Is there any shortcut to find the last two digit of the above expression.

Any help would be appreciated.

Thanks,
Ashish

2. Do you know the chinese remainder theorem? If so let me know, and I will show you a much easier way. I got 76.

If not, you can just multiply and reduce modulo 100 at each stage, and the worst you will ever have to multiply is some 2 digit numbers. It will take a while, but you will get the correct answer. I suggest multiplying in a smart fashion to reduce some of the work like do
2*49=98=-2 (mod 100)
4*48=2*2*48=2*-4=-8 (mod 100)
etc

Can you please let me know how we can do it with Chinese remainder theorem?

Thanks,

4. ## Chinese Remainder Theorem in Action

Sure thing mate. So the goal is to figure out what this beast is mod 100. Fortunately, we have $\displaystyle 100=2^2\cdot 5^2$. Now we notice that gcd(5^2,2^2)=1, which means we are in business for using the chinese remainder theorem. So this means we can just figure what this thing is mod 4 and mod 25 separately and the chinese remainder theorem will give us the unique solution mod $\displaystyle 100=25\cdot 4$.

mod 4 is really easy because one of the numbers is 0 mod 4, so the product will be 0.

We are not quite as fortunate when we look mod 25.
This is the product when each term has been reduced.
$\displaystyle (1\cdot 2\cdot 3\cdot 4\cdot -4 \cdot -3 \cdot -2 \cdot -1)^2=(24\cdot 24)^2=(-1\cdot -1)^2=1^2=1$ (mod 25).

So there is precisely 1 number between 1 and 100 which is both 0 mod 4 and 1 mod 25. By inspection it is pretty clear it is 76, so this will be the last two digits of this product.

Just to prove to you that the CRT works in general, you have numbers that are relatively prime, that is gcd(a,b)=1. Then say we are looking to solve this congruence
$\displaystyle n\equiv x$ (mod a)
$\displaystyle n\equiv y$ (mod b)

Then there is 1 number mod ab that will satisfy this and this is how you figure out in general what it is.

Use the Euclidean Algorithm to find integers s,t, such that $\displaystyle as+bt=1$. Now take the number yas+xbt notice the sort of cross multiplying aspect of choosing this number.

now we consider $\displaystyle yas+xbt$ (mod ab)
$\displaystyle yas+xbt \equiv xbt \equiv x(1-as) \equiv x-xas \equiv x$ (mod a)

Similarly
$\displaystyle yas+xbt \equiv yas \equiv y(1-bt) \equiv y-xbt \equiv y$ (mod b)

And presto, there you have it in general.

In our case we notice that $\displaystyle -6\cdot 4 + 1\cdot 25=1$, so we should choose $\displaystyle 1\cdot (-6)\cdot 4 + 0\cdot 1\cdot 25=-24=76$ (mod 100) as claimed. There ya have it.

5. Thanks a lot Gamma,it is very informative