0
$\begingroup$

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.

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

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

$\endgroup$
6
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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

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

$\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$?

$\endgroup$
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.