# Find $7^{999,999}$ modulo (10)

I am trying to find $7^{999,999}$ modulo (10) using Euler's Theorem:

If $m \in \mathbb{Z^+}, a \in \mathbb{Z}, (a,m) = 1$ then $a^{\phi(m)} \equiv 1$ (mod m).

I am unsure though how to use it since it doesn't seem useful to consider $7^{999,999} \equiv 1$ (mod 999,999). Any help is appreciated.

• HINT: What about $7^{1000000}$? – Crostul Jun 11 '15 at 7:59
• $phi (10)=4$ and $999996$ is divisible by $4$. – Uncountable Jun 11 '15 at 7:59
• So I tried playing with that but I didn't have any further ideas. – letsmakemuffinstogether Jun 11 '15 at 8:00
• It's not relevant here, but $\phi(999999)$ is $466560$, not $999999$. (And even if $999999$ were prime, $\phi(999999)$ would be $999998$.) – TonyK Jun 11 '15 at 8:19

## 5 Answers

Using Euler's theorem:

$$7^4 \equiv 1 \mod 10$$

Then raise each side to the power of $249999$ to get

$$7^{999996} \equiv 1 \mod 10$$

Multiply each side by $7^3$:

$$7^{999999} \equiv 343 \mod 10$$

Or

$$7^{999999} \equiv 3 \mod 10$$

The key point is that $\gcd(7,10) = 1$ and $\phi(10) = (2-1)(5-1)=4$ so $$7^{999,999} \equiv 7^{999,999 \bmod 4} \pmod{10}$$ So you have to compute $999,999 \bmod 4 = 3$ (Because $1,\!000,\!000 = 999,\!999 + 1$ is a multiple of $4$, this can be done without a calculator) $$7^{999,999} \equiv 7^3 = 49 \cdot 7 \equiv 9 \cdot 7 = 63 \equiv 3 \pmod{10}$$ The way we did this, you don't even need a calculator.

$$7^{999,999} \equiv 7 \cdot 7^{999,998} \equiv 7 \cdot 49^{499,999} \equiv 7 \cdot (-1)^{499,999} \equiv -7$$ There's no need even for Euler's theorem.

• This is incorrect. – letsmakemuffinstogether Jun 11 '15 at 9:12
• @letsmakemuffinstogether you're wrong. $-7 \equiv 3 \pmod{10}$ – man and laptop Jun 11 '15 at 9:12
• You are correct. It is 2:13am where I am and I should go to sleep; my mistake. – letsmakemuffinstogether Jun 11 '15 at 9:14

$\gcd(7,10)=1$ and $\varphi(10)=4$, so Euler's theorem says $7^4\equiv 1\bmod 10$.

Now what can you conclude about $7^{999999} = 7^{(249999\cdot 4)+3} = (7^4)^{249999}\cdot 7^3$ modulo $10$?

Since $(7,10)=1$, and $\phi(10)=4$, then $7^4\equiv1$(mod $10$) by Euler's Theorem. Notice that $999999=4*249999+3$. Then $$7^{999999}\equiv7^{4*249999+3}\equiv(7^4)^{249999}(7^3)$$ $$\equiv1^{249999}(7^3)\equiv7^3\equiv(-3)^3\equiv-27\equiv3(mod\ 10)$$