# Last 3 digits of $7^{12341}$

I know that I need to reduce $7^{12341} \pmod {1000}$

By Euler I have $7^{\phi(1000)}\equiv 7^{400}\equiv1\pmod{1000}$

That leaves me with the monster $7^{341}\pmod{1000}$

Is there a way to reduce this smoothly without working $7^2, 7^4, 7^8$ etc manually ?

#### Solutions Collecting From Web of "Last 3 digits of $7^{12341}$"

$7^{20}=(7^5)^4=((16807)^2)^2\equiv((807)^2)^2\equiv(651249)^2\equiv249^2\equiv62001\equiv1\pmod {1000}$

Then we write $7^{341}=7*(7^{20})^{17}\equiv7*1^{17}\equiv7\pmod {1000}$

To find $7^{341} (\bmod 1000)$, it suffices to work out $7^{341} (\bmod 125)$ and $7^{341} (\bmod 8)=-1$. The former can be done with successive squaring, as you mentioned.

$$7^2=50-1$$

$$7^{20n+1}=7(7^2)^{10n}$$

Now $(7^2)^{10n}=(50-1)^{10n}=(1-50)^{10n}$

Using Binomial Theorem,
$(7^2)^{10n}=1-\binom{10n}150+\binom{10n}2(50)^2\cdots+(50)^{2n}$

$\implies(7^2)^{10n}\equiv1-500n+\dfrac{10n(10n-1)}250^2\pmod{1000}\ \ \ \ (1)$ for $n\ge2$

Again, $\dfrac{10n(10n-1)}250^2=50n^2(50^2)-5n(2500)\equiv-500n\pmod{1000}$ as $2500\equiv100\pmod{200}\implies5(50^2)\equiv5\cdot100\pmod{5\cdot200}\equiv500$

From $(1),$

$(7^2)^{10n}\equiv1-500n-500n\pmod{1000}\equiv1$

Here $n=\dfrac{12341 -1}{20}$

As you simplified it till $7^{341}$ (mod 1000);

from there => $7^{341}$ = $7^{340}$*$7^{1}$
= $7^{4(85)}$*$7^{1}$
= $2401^{85}$*$7^{1}$

so last three digits of $2401^{85}$*$7^{1}$ = last three digits of product of the last three digits of $2401^{85}$ and $7^{1}$

As we know the last digit of $7^{1}$ = 7;

To calculate the last three digits of $2401^{85}$ it we use last three digits of the no 2401 i.e, 401.

last two digits of any power of a number ending with 01 gives 01 only and the third last digit will be the units digit in 4*85 or simply 4*5 i.e, 0

So the last three digits of $2401^{85}$ are 001.

And the last three digits of the original number $7^{12341}$ will be 001*7 = 007.