Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
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
add comment

3 Answers 3

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|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
add comment

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

share|improve this answer
add comment

$$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|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
add comment

Your Answer

 
discard

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.