Find $r\in\Bbb Z$ for $4^{451}\equiv r\mod 7$

Question

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.

Answer 1

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$

Answer 2

$$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$.

Answer 3

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$.

Answer 4

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.$

Answer 5

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) $