if $n>1$ odd number,find $$2^n\equiv ?\pmod {12}$$
it seem the answer is $8$,because $$2^3=8\equiv 8\pmod{12}$$ $$2^5=32\equiv 8\pmod {12}$$ $$2^7=128\equiv 8\pmod {12}$$ $$2^9=512\equiv 8\pmod {12}$$ $$\cdots $$ But How to prove it for all postive integers $n$?
On
You can prove it with the Chinese remainder theorem: $12=2^2\cdot3$.
We have $2^n\cong0\pmod{2^2}$, and$2^n\cong2\pmod3$ ( since by Fermat's little theorem, $2^2\cong1\pmod3$).
Using Bezout's identity, $1\cdot2^2-1\cdot 3=1$, we get $2\cdot1\cdot2^2+0\cdot1\cdot 3=8$, as our solution.
On
We first calculate $$2^n \mod{3}, 2^n \mod{4}$$ and then combine the results with Chinese Remainder Theorem.
Both should be easy to calculate. Writing n=2k+1, $$2^{2k+1} \equiv {-1}^{2k+1} \equiv ({-1}^{2})^{k} \times {-1}^1 \equiv 1 \times -1 \equiv -1 \equiv 2 \mod{3}$$ $$2^{2k+1} \equiv 4^k\times2\equiv0\mod{4}$$ Therefore by CRT, $$2^{2k+1} \equiv 8 \mod{12}$$
To be precise, we want to prove that if $n$ is an odd number $\geq 3$, then $$2^n\equiv 8\pmod{12}.$$ Since you've verify the initial case $n=3$, we assume if $k\geq3$ is an odd number and $2^k\equiv 8\pmod{12}$ holds, then $$2^{k+2}\equiv 8\times 4\equiv 32\equiv 8\pmod{12}$$ holds as well. Hence we completed the proof by induction.