Last 3 digits of $7^{12341}$

Question

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 ?

Answer 1

$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}$

Answer 2

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.

Answer 3

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.

Answer 4

$$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}$

Answer 5

If $7^n \equiv 1 \pmod{1000}$ then $7^{-1} \equiv 7^{n-1} \pmod{1000}$.

Solving $7x \equiv 1 \pmod{1000}$ we find that $x \equiv 143 \pmod{1000}$.

If we perform $\pmod{10}$ calculations on $7^n, n \ge 1$ we get

$$ 7,9,3,1,7,9,3 \dots$$

Since this is of period $4$ we are looking for the first $k \ge 1$ where

$$ 7^3 \cdot (7^4)^k \equiv 143 \pmod{1000}$$

Now $7^3 \equiv 343 \pmod{1000}$ and $7^4 \equiv 401 \pmod{1000}$ and

$\; (300 + 43) * (400 + 1) \equiv 300 + 200 + 43 \equiv 543 \pmod{1000}$
$\; (500 + 43) * (400 + 1) \equiv 500 + 200 + 43 \equiv 743 \pmod{1000}$
$\; (700 + 43) * (400 + 1) \equiv 700 + 200 + 43 \equiv 943 \pmod{1000}$
$\; (900 + 43) * (400 + 1) \equiv 900 + 200 + 43 \equiv 143 \pmod{1000}$

So $k = 4$ gets us to the inverse $7^{-1} \equiv 7^{19} \pmod{1000}$ and therefore

$$ 7^{20} \equiv 1 \pmod{1000}$$

We can take the last line of Antony's answer to wrap this up.