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}$.
Tell me more
×
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.
|
|
$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... |
|||||
|
|
|
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$. |
|||||
|
