Find $r\in\Bbb Z$ for $4^{451}\equiv r\mod 7$ I guess I should start by saying that $4\equiv 11\mod 7$, but I don't know how to proceed from here.
Is it possible to do without using Fermat's theorem?
Thank you.
 A: As $\displaystyle4=2^2,4^{451}=(2^2)^{451}=2^{902}$
Now, $\displaystyle2^3=8\equiv1\pmod7$ and $902\equiv2\pmod3$
$\displaystyle\implies2^{902}=(2^3)^{300}\cdot2^2\equiv1^{300}\cdot2^2\pmod7$
A: $$4^{451}=2^{902}=4(2^{900})=4(7+1)^{300}$$
From binomial expansion, we can say that $7$ leaves a remainder of $1$ when it divides $(7+1)^{300}$.Hence:
$$4(7+1)^{300}=4(7k+1)=7l+4$$
So you can conclude that $r=4$.
A: Note $(4^0, 4^1, 4^2, 4^3) \mod 7 \equiv (1,4,16,64) \mod 7 \equiv (1,4,2,1)$ so there is a cycle of 3. Now $4^{451} = 4 \cdot 4^{3 \cdot 150}$ so you will make $150$ cycles from $1$ and come back to $4$. The remainder should be $4$.
A: Hint $\ {\rm mod}\ 7\!:\ 2^{\large 3}\equiv 1\,\Rightarrow\, 2^{\large 2(\color{#c00}{451})}\!\equiv 2^{\large \color{}2},\,$ by $\,{\rm mod}\ 3\!:\ \color{#c00}{451}\equiv 4\!+\!5\!+\!1\equiv \color{#c00}1,\,$ by $\,10\equiv 1.$
A: You can do this way too,
$4 \ \equiv -3 \ (mod \ 7)$
$4^2 \ \equiv \ 9$
$4^2 \ \equiv \ 2$
$4^6 \ \equiv \ 8$
$4^6 \ \equiv \ 1$
$4^{450} \ \equiv \ 1$ 
$4^{451} \ \equiv 4 \ (mod \ 7)$
If we can find congruent to $ \pm 1$  then the problem becomes easier.
UPDATE:
You can also do
$4^3 \ \equiv \ 1 \ (mod \ 7) $
$4^{450} \ \equiv \ 1 $
$4^{451} \ \equiv \ 4 \ (mod \ 7) $
