Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
@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
up vote 3 down vote accepted

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

share|cite|improve this answer
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$.


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

share|cite|improve this answer

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

share|cite|improve this answer
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
yes, I fixed it. Thanks :) – Iuli Feb 14 '13 at 20:12

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.