2

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
  • 603
  • 1
    @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

3 Answers3

3

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}^+$.

Fly by Night
  • 32,272
3

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

Caleb Jares
  • 603
N. S.
  • 132,525
2

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

Iuli
  • 6,790