Find the last 3 digits of ${341}^{101}+ {309}^{201}$.

Question

I was trying to solve it with Fermat–Euler theorem, but this didn't help me with anything. Please give a hint. Thanks.

Answer 1

HINT:

$$341^{101}=(1+340)^{101}\equiv1+\binom{101}1340+\binom{101}2340^2\pmod{1000}$$

$$309^{201}=(310-1)^{201}=-(1-310)^{201}$$

$$(1-310)^{201}\equiv1-\binom{201}1310+\binom{201}2310^2\pmod{1000}$$

Now $\displaystyle\binom{101}134=(100+1)34\equiv34\pmod{100}\implies\binom{101}1340\equiv340\pmod{1000}$

and $\displaystyle\binom{101}234^2=101\cdot34^2\equiv6\pmod{10}\implies\binom{101}2340^2\equiv600\pmod{1000}$

Answer 2

HINT:

Using Carmichael Function, $$\lambda(1000)=\cdots=100$$

As $(309,1000)=1,201\equiv1\pmod{100},$ $$309^{201}\equiv309^1\pmod{1000}$$

Can you take it from here?

Answer 3

You need to reduce modulo $1000 = 125\cdot 8$; the Chinese Remainder Theorem can help. First note that $\phi(125) = 100$, so you have

$$x=341^{101}+309^{201} \equiv 341 +309 \equiv 650 \pmod{125}.$$

Second, note that every odd number to an even power is congruent to $1$ modulo $8$, so you have

$$x=341^{101}+309^{201} \equiv 341+309 \equiv 650 \pmod{8}.$$

Finally, by CRT, $x\equiv 650 \pmod{125\cdot 8}.$

Answer 4

If $\, a,b\,$ are coprime to $\,m,n\,$ and $\,j,k \equiv 1\,$ mod $\,\phi(n)\,$ and $\,\phi(m)\,$ then, by Euler's theorem,

we deduce $\, a^j+b^k \equiv\, a + b\,$ mod $\,m,n,\,$ so also mod $\,{\rm lcm}(m,n).\,$ OP is special case $\,m,n = 8,125$.