Remainder using Modular Arithmetic

Question

The question is to find out $2005^{2007^{2009}}\bmod 7$ or the remainder when $2005^{2007^{2009}}$ is divided by $7$. My steps $: \\ 2005\equiv3\pmod 7\\ 2005^3\equiv3^3\equiv-1\pmod7\\ 2005^{2007}\equiv-1^{669}\equiv-1\pmod7$

How do I proceed? Please help!!!

Answer 1

As $2005$ is not divisible by $7$ – more precisely, $2005\equiv 3\bmod 7$, you can use lil' Fermat: $$2005^{2007^{2009}}\equiv 3^{2007^{2009}}\equiv 3^{2007^{2009}\bmod 6}\mod 7.$$ Now $\;2007\equiv 3\mod 6$, and it happens that, for all $n$, $3^n\equiv 3\mod 6$, so that $$2005^{2007^{2009}}\equiv 3^3\mod 7.$$

Answer 2

Your beginning was promising

$$2005=3\pmod 7\;,\;\;\text{and}\;\;3^3=-1\pmod 7\,,\,\,3^6=1\pmod 7$$

Now, $\;2007^{2009}=0\pmod 3\;$ and also odd , so ... (Try to complete the argument)

Answer 3

Note that $A^{\large B^{\Large N}}\!$ means $A^{\large (B^{\Large N})}$ not $(A^{\large B})^{\large N}$ so we cannot proceed bottom-up as you did. Instead we need to work top-down: we can use $\,3^{\large 6}\equiv 1\pmod{\!7}\,$ to do modular exponent reduction, i.e.

$\!\bmod 7\!:\,\ 3^{\large 6}\!\equiv 1\,\Rightarrow\, 3^{\large N}\!\equiv 3^{\large N\bmod 6}\! \equiv 3^{\large\color{#c00}3}\!\equiv 6\ $ since, by CPR = Congruence Power Rule

$$\begin{align} N\bmod 6\, &=\, 2007^{\large 2009}\!\bmod 6 \\[.2em] &=\ \ \ \ \ \ 3^{\large 2009}\bmod 6\ \ \ \ \ {\rm by}\ \ 2007\equiv 3\!\!\!\pmod{\!6}\ \ \&\ \ \rm CPR\\[.2em] &=\ \ 3(3^{\large 2008}\bmod 2)\ \ \ \ \text{by mod Distributive Law (below)} \\[.2em] &=\ \ 3(1^{\large 2008} \bmod 2)\ \ \ {\,\rm by}\ \ 3\equiv 1\!\!\!\pmod{\!2}\ \ \&\ \ \rm CPR\\[.2em] &= \ \ \color{#c00}3 \end{align}$$

where above we have applied $\ ab\bmod ac = a(b\bmod c) =$ mod Distributive Law, in order to simplify by factoring $\,3\,$ out of the $\!\bmod\!.\,$ This law is equivalent an of CRT = Chinese Remainder Theorem, but its operational form makes it more convenient in many applications such as above.