TITLE: Fermat's little theorem confusion
QUESTION [3 upvotes]: 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.

REPLY [2 votes]: $\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}$
{"set_name": "stack_exchange", "score": 3, "question_id": 251780}