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.
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.
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.
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.$
$3^{50} = (3^6)^8 \times3^2 \equiv 1^8 \times 2 \;(\text{mod }7).$
$\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}$