Find remainder using euler function?

Question

How to find the remainder of $\frac{208^{181}}{209}$ using Euler's function or Fermat's theorem? (I solved this kind of problem easily when base, $208$, is smaller than the power, $184$, but it's hard to solve when the base is larger than the power).

Thank you..

Answer 1

Hint:

Compute $\varphi (209)$. Now divide $181$ by $\varphi(209)$ with remainder and simplify the exponent.

---

Solution:

Since $\varphi(209)=180$ and $181 = 180\cdot 1 + 1$, and $208 \not\mid 209$ by Euler's theorem we have

$$208^{181} = 208^{180+1} = 208^{180} 208^1 \equiv 1 \cdot 208^1 \equiv 208 \pmod{209}.$$

Thus, the remainder is $208$.

Answer 2

You don't need Euler: $\ {\rm mod}\ 209\!:\ \color{#c00}{208\equiv -1}\,$ so $\,\color{#c00}{208}^{1+2k}\equiv (\color{#c00}{-1})^{1+2k}\equiv -1 (-1)^{2k}\equiv -1$