Digits Modulo 1000

From the binomial expansion, we have $11^7 = (10+1)^7 \equiv 2100+70+1 = 171 \pmod{1000}$ . Hence, $171^{172} \equiv (11^7)^{172} \equiv 11^{1204} \pmod{1000}$ . Since $\phi(1000) = 1000\left(1-\frac{1}{5}\right)\left(1-\frac{1}{2}\right)= 400$ , we use Euler's Theorem to obtain $11^{1204} \equiv 11^4 \equiv 14641 \equiv 641 \pmod{1000}$ .

Note: There are other ways to arrive at the answer, like attempting to multiply it out.

Hello calvin i also had a solution

171^172 = 57^172 x 3^172 so 57^172 has 001 as its last digits.....

so we have to find last three digits of 3^172

3^8 === 561(mod1000) 3^168 === 561^21(mod 1000) 3^172 ===561^21 x 81

So by using Binomial Theorem, expanding 561^21,, and by checking, its last 3 digits came to be 761.As all the starting terms would have last 3 digits as 000,we have to see its last 4 terms,and adding there last 3 digits we get 761 so 761 x 81 = 61641 Hence last 3 digits will be 641..........Calvin have a look at my solution,is it correct or any defect is there......

Hmm. I have a solution, but it's a lot more straight-forward than the other ones put up. It's not as elegant as I hoped it'd be, and involves a lot of hacking and numerical work, but I'll put it up, while I look for a quicker one, in time. To simulate the exam conditions, I did not use a Calculator, and solved it in about 12 minutes, which is perhaps too much for a 1 hour paper.

Now, we need to find 171^172 mod 1000.

I split 1000 into it's co-prime factors, 125 and 8 and found those moduli individually.

171^172 mod 8 === 3^172 mod 8

And by Euler's theorem, phi (8) = 4, so,

3^172 mod 8 === 3^ (172 mod 4) mod 8 === 3^ 0 mod 8 === 1 So, 171^172 mod 8 === 1

Now,

171^172 mod 125 === 46^172 mod 125

And by Euler's Theorem, phi (125) = 100, so,

46^172 === 46^72 mod 125===(2^72) (23^72)

Here, the biggest problem we have are the enormous exponents. We've got to make them more tractable. So,

Now, 2^72 === (2^9)^8 === 512^8 === 12^8 mod 125 12^8=== 144^4 mod 125 === 19^4 ===361^2 mod 125 === (-14)^2 mod 125 === 196 === 71 mod 125

So, 2^ 72 === 71 mod 125

And, 23^72 === (529)^36 === 29^36

Now, 29^3 ===24389 ==== 14 mod 125, so,

29^36 ===14^12 mod 125 === (14^3)^4=== 2744^4===(-6)^4 mod 125 (-6)^4 ===1296 === 46 mod 125

So, 2^72(23^72) === 71(46) mod 125 And, 71(46) === 16 mod 125

So, we have 171^172 === 16 mod 125 and, 171^172 === 1 mod 8

From here, we can deduce that, 171^172 === either 16 or 141 or 266 or... 641 satisfies both equations, so we can say, that, 171^172=== 641.

[Calvin - Edits have been added in to reflect Sreejato's latter comments.]

To compute the last three digits of a number is equivalent to find its value modulo 1000.

Now, 171^172= (100+71) ^172= 100^172 + (172C1) (100^171) (71^1) + … + (172C170) (100^2) (71^170) + (172C171) (100) (71^171) + 71^172

Now, 100^2= 10000, and 1000 divides 100^2. So, if k>=2, 1000 divides 100^k.

Thus, 1000 divides (100+71) ^172 + (172C1) (100^171) (71^1) + … + (172C170) (100^2) (71^170).

This implies that 100^172 + (172C1) (100^171) (71^1) + … + (172C170) (100^2) (71^170) + (172C171) (100) (71^171) + 71^172== (172C171) (100) (71^171) + 71^172 (mod 1000)

Now, 172C171= 172! /171!1!= 172 So, 171^172==172 100 71^171 + 71^172 == 71^171(17200+71) == 71^171 * 17271 == 271 * 71^171(mod 1000)

Now, 70^3= 343000, and 1000 divides 70^3. So it can be concluded that if k>=3, 1000 divides 70^k.

Therefore 1000 divides 70^171+(171C1) (70^169) +… + (171C168) 70^3.

This implies that 71^171 == 14535 * (-100) + 171*70+1== -1441529 == 471 (mod 1000)

So, 271* 71^171 == 271*471== 127641 == 641 (mod 1000)

So, the last three digits are 641.