Last two digit

**a69356** · August 13th 2009, 10:08 PM

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

**Gamma** · August 13th 2009, 11:54 PM

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

**a69356** · August 14th 2009, 01:50 AM

Thanks Gamma for your reply.

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

Thanks,

**Gamma** · August 14th 2009, 02:23 AM

Sure thing mate. So the goal is to figure out what this beast is mod 100. Fortunately, we have $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 $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.
$(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
$n\equiv x$ (mod a)
$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 $as+bt=1$ . Now take the number yas+xbt notice the sort of cross multiplying aspect of choosing this number.

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

Similarly
$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 $-6\cdot 4 + 1\cdot 25=1$ , so we should choose $1\cdot (-6)\cdot 4 + 0\cdot 1\cdot 25=-24=76$ (mod 100) as claimed. There ya have it.

**a69356** · August 14th 2009, 05:12 AM

Thanks a lot Gamma,it is very informative

Thread: Last two digit

LinkBack

Thread Tools

Display

Last two digit

Chinese Remainder Theorem in Action

Similar Math Help Forum Discussions

[SOLVED] How many 3 digit ...

Digit sum & digit product of number x

digit

Last digit

decimal digit as final digit

Search Tags