1
$\begingroup$

There are many examples on math SE on how to use Euler's theorem to compute modulos of large powers. Yet, I can't seem to find a solution to the following problem:

Compute $1808^{80085^{2014}} \mod 17$

Euler's theorem is $a^{\phi(n)} \equiv 1 \mod n \iff gcd(a,n) = 1$

The solution is as follows:

$ \begin{align} &1808^{80085^{2014}} & \mod 17 \\ =& 6^{80085^{2014} mod \phi(17)} & \mod 17 \\ =&6^{5^{2014 \mod \phi(16)} \mod 16} & \mod 17 \\ =&6^{5^{2014 \mod 8} \mod 16} & \mod 17 \\ =&6^{5^{6} \mod 16} & \mod 17 \\ =&6^{9} & \mod 17 \\ =&11 \end{align} $

I know how to compute $\phi(n)$, I know that $1808 \mod 17 = 6$, but how does $6^{80085^{2014} mod \phi(17)} \mod 17$ follow from $1808^{80085^{2014}} \mod 17$?

$\endgroup$
  • 1
    $\begingroup$ Do you mean 80085 or 8085? (although both ≡ 5 (mod 16)) $\endgroup$ – kennytm Aug 23 '16 at 8:01
  • $\begingroup$ @kennytm 80085. Fixed the question. Thank you! $\endgroup$ – Auberon Aug 23 '16 at 8:03
2
$\begingroup$

That is because $n^m \equiv (n-17)^m \mod 17$ thus

$$n^m \equiv (n \mod 17)^m \mod 17$$

$$1808^m \equiv(1808 \mod 17)^m \equiv 6^m \mod 17$$

then you have

$$6^m \equiv 6^{m \mod \phi(17)} \mod 17$$ due to Euler's theorem.

Detail:

$$ 6^{\phi(17)} \equiv 1\mod 17$$ thus $$ 6^m = 6^{m-\phi(17)}\cdot 6^{\phi(17)} \equiv 6^{m-\phi(17)}\cdot1 \equiv 6^{m-\phi(17)}\mod 17$$ so $$6^m \equiv 6^{m \mod \phi(17)} \mod 17$$

$\endgroup$
  • $\begingroup$ Excellent! Blew my mind a little. $\endgroup$ – Auberon Aug 23 '16 at 8:20
1
$\begingroup$

We want to calculate $1808^{80085^{2014}}\bmod{17}$.


Let's observe $1808^{k}\pmod{17}$:

  • By Euler's theorem: $\gcd(1808,17)=1\implies1808^{\phi(17)}\equiv1\pmod{17}$
  • Since $17$ is prime, $\phi(17)=17-1=16$, hence $1808^{16}\equiv1\pmod{17}$

Let's observe $80085^{k}\pmod{16}$:

  • By Euler's theorem: $\gcd(80085,16)=1\implies80085^{\phi(16)}\equiv1\pmod{16}$
  • Since $16$ is a power of two, $\phi(16)=16/2=8$, hence $80085^{8}\equiv1\pmod{16}$

Let's compute $80085^{2014}\bmod{16}$:

  • $80085^{2014}\equiv80085^{8\cdot251+6}\equiv(80085^{8})^{251}\cdot80085^{6}\equiv1^{251}\cdot80085^{6}\equiv80085^{6}\pmod{16}$
  • $80085^{6}\bmod{16}=(80085\bmod{16})^{6}\bmod{16}=5^{6}\bmod{16}=15625\bmod{16}=9$

Let's compute $1808^{80085^{2014}}\bmod{17}$:

  • $1808^{80085^{2014}}\equiv1808^{16n+9}\equiv(1808^{16})^{n}\cdot1808^{9}\equiv1^{n}\cdot1808^{9}\equiv1808^{9}\pmod{17}$
  • $1808^{9}\bmod{17}=(1808\bmod{17})^{9}\bmod{17}=6^{9}\bmod{17}=10077696\bmod{17}=11$
$\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.