Prove this modular congruency?

Question

Prove that $2^{2x} \equiv 1 \mod 3$ for any integer $x$?. I know this is true but is there a nice way to prove it?

score 4 · Answer 1 · answered Oct 23 '15 at 09:41

4

Its very simple. $$2^{2x}=4^x\equiv 1^x (\text{mod } 3)\equiv 1(\text{mod } 3).$$

answered Oct 23 '15 at 09:41

Ofir Schnabel

score 1 · Accepted Answer · answered Oct 23 '15 at 10:03

1

HINT:-

An approach which does not involve modular arithmetic.

R.T.P.

$2^{2x} \equiv 1 \mod 3$

or,$2^{2x}-1$ is divisible by $3$.

Now,$2^{2x}=4^x$

So,prove by induction now that $4^x-1$ is divisible by $3.$.'

answered Oct 23 '15 at 10:03

Soham

i feel silly... $4^{x+1} = 4(3n + 1)$ therefore $\frac{4^{x+1} - 1}{3} = 4n + 1$. and it works for x = 1. thanks for a simpler method – jg mr chapb Oct 23 '15 at 12:22
@gebra-Welcome....nice problem though... – Soham Oct 26 '15 at 12:57

2 Answers2