Fermat's little theorem confusion

Question

Problem, What is the remainder when $3^{50}$ is divided by $7$

I know I have to use Fermat's little theorem, but I'm confused at a certain point.

I have that $3^{6}\equiv1 \bmod7$ Now I'm not sure what to do, although I know that the remainder is 2.

Answer 1

$\begin{eqnarray}{\bf Hint}\qquad &&3^{50}\! &=&\, 3^{\color{#C00}6\cdot 8+2} &=& (3^\color{#C00}6)^8\,\ 3^2 \equiv \,1^8\ 3^2 \equiv\, 2\ \ \ \rm by\ \ \ 3^\color{#C00}6\equiv 1\,\ (mod\ 7) \\ \rm Generally &&\rm 3^N &=&\,\rm 3^{\color{#C00}6Q+R} &=&\rm (3^\color{#C00}6)^Q\, 3^R \equiv 1^Q\, 3^R\equiv 3^R\\ \rm \Rightarrow\ &&\rm 3^N &\equiv&\,\rm 3^{R}\ \: for\!\!\! &&\rm\!\!\! R = (N\,\ mod\ \color{#C00}6)\\ \rm e.g.\ &&3^{50}\!&\equiv&\, 3^2\ \ \ \rm by &&\!\!\rm 2 = (50\ mod\ \color{#C00}6)\\ \end{eqnarray}$

Answer 2

Since $3^6\equiv1\pmod7$ and $50=6\cdot8 +2\Rightarrow 3^{50}\equiv3^{6\cdot8 +2}\equiv3^{6\cdot8}3^2\equiv(3^6)^83^2\equiv3^2\equiv9\equiv2\pmod7.$

Answer 3

$3^{50} = (3^6)^8 \times3^2 \equiv 1^8 \times 2 \;(\text{mod }7).$

Answer 4

An alternative approach I much prefer (as it's easier to grasp) but that's a bit longer:

$ 3^{50} = (3^2)^{25} = 9^{25} \equiv 2^{25} $ mod $7$

Just keep removing squares from the even exponents, and then computing a smaller equivalent mod $7$:

$ 2^{25} = 2 \cdot 2^{24} = 2 \cdot 4^{12} = 2 \cdot 16^6 \equiv 2 \cdot 2^{6} $ mod $7$

Nearly there.. When the exponent is odd, take out 1 factor to make it even again

$ 2 \cdot 2^{6} = 2 \cdot 4^{3} = 2 \cdot 4 \cdot 4^2 = 8 \cdot 16 \equiv 1 \cdot 2 \equiv 2 $ mod $7$

Done.