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$
2
  • 1
    $\begingroup$ Do you mean 80085 or 8085? (although both ≡ 5 (mod 16)) $\endgroup$
    – kennytm
    Commented Aug 23, 2016 at 8:01
  • $\begingroup$ @kennytm 80085. Fixed the question. Thank you! $\endgroup$
    – Auberon
    Commented Aug 23, 2016 at 8:03

2 Answers 2

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$
1
  • $\begingroup$ Excellent! Blew my mind a little. $\endgroup$
    – Auberon
    Commented Aug 23, 2016 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$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .