# Proving $4^{47}\equiv 4\pmod{12}$

I know this is a simple exercise, but I was wondering if I can make the following logical jump in my proof:

We see that $4\equiv 4\pmod{12}$ and $4^2\equiv 4\pmod{12}$. Then we can recursively multiply by $4$ to get $4^{47}\equiv 4\pmod{12}$.

-
@Caleb Jares You got the right idea, but how to prove it? I suggest generalizing to $4^n \equiv 4\pmod {12}$ for all $n\in \Bbb N$ and proving it by induction. It will follow that it is also true for $n=47$. –  Git Gud Feb 14 '13 at 19:30
Your proof is valid. Perhaps add a couple of sentences to detail the inductive step, but it should be straightforward. –  Thomas Feb 14 '13 at 19:46

$4^{47}$ and $4$ are divisible by $4$ thus $4^{47}-4$ is a multiple of $4$.

Also, since $4 \equiv 1 \pmod{3}$ we have $4^{46}\equiv 1^{46}\pmod{3}$ and then

$$4^{47} \equiv 4 \pmod 3 \,.$$

Thus $4^{47}-4$ is a multiple of $3$ and $4$, and hence of 12...

-
Thanks, this is a great way to prove it without induction! –  Caleb Jares Feb 14 '13 at 21:18
+1 Nice work N.S.! –  Fly by Night Feb 15 '13 at 18:10

The idea is absolutely correct. You just need to formalise it by using an inductive argument. I would try to prove that $4^n \equiv 4 \bmod 12$ for all $n$. This is a classic example of proof by induction.

Base Case

If $n=1$ then is $4^1 \equiv 4 \bmod 12$? Well, clearly $4^1 \equiv 4 \bmod 12$.

Induction Step

Assume that for $n=k$ we have $4^n \equiv 4 \bmod 12$, does this imply that $4^{n+1} \equiv 4 \bmod 12$?

Well, if $4^k \equiv 4 \bmod 12$ then $4^{k+1} = 4 \times 4^k \equiv 4 \times 4 \bmod 12 \equiv 4 \bmod 12$.

Conclusion

It follows that $4^n \equiv 4 \bmod 12$ for all $n \in \mathbb{Z}^+$.

-
$$4^{47}\equiv 4\pmod{12}$$
$$4^{47}-4=4 \cdot \left(4^{46}-1\right)=4 \cdot \left(4^{23}-1\right)\cdot \left(4^{23}+1\right)=$$ $$=4 \cdot \left(4-1\right)(4^{22}+4^{21}\cdot1+\ldots+1)\cdot \left(4^{23}+1\right)=4 \cdot3 \cdot \left(4^{22}+4^{21}\cdot1+\ldots+1\right)\cdot \left(4^{23}+1\right)=$$ $$=12 \cdot \left(4^{22}+4^{21}\cdot1+\ldots+1\right)\cdot \left(4^{23}+1\right)$$ which is divisible with $12$.
You seem to have lost the factor $4^{23}+1$. Also, $4^{23}-1=(4-1)(4^{22}+4^{21}+...+4+1)$ –  user60725 Feb 14 '13 at 20:09