Euler's theorem: $1808^{80085^{2014}} \mod 17$

Question

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

Answer 1

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

Answer 2

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$