Prove $2^{2m}-2^m+1 \equiv 3 \pmod 9$.

Question

How can I get $2^{2m}-2^m+1 \equiv 3 \pmod 9$ when $m$ is an odd integer?

Answer 1

Let $x= 2^m$ and $m=2n+1$.

$$2^{2m}-2^m-2 = x^2-x-2 = (x-2)(x+1) = (2^m+1)(2^m-2)$$

Since $$2^m+1 = (2+1)(2^{m-1}+...+2^2+2+1) =3a$$

and $$2^m-2= 2(4^n-1) = 2(4-1)(4^{n-1}+...+4^2+4+1) =3b$$

we are done.

Answer 2

If $m$ is an odd integer then $2^m = 2, 5 \text{ or } 8 \mod 9$ so you only need to check 3 cases.