# Prove that $4^n$ is not divisible by 3.

How can one prove that $4^n$ is not divisible by 3, for any $n \ge 0$?

One way I found is to proof that $4^n - 1$ is always divisible by 3 (as demonstrated in a question here), thus $4^n$ could never be divisible by 3.

Can you suggest a better way to prove this?

Thanks!

• Use that $3$ is prime, that is $3\mid ab$ implies $3\mid a$ or $3\mid b$ May 19 '14 at 18:40
• Prove is the verb, proof is the noun. May 19 '14 at 18:46
• $4^n$ is all $4$s and there ain't no $3$ in $4$.
– Neal
May 19 '14 at 19:07
• I am guessing you want a proof without the Fundamental Theorem of Arithmetic which would make this proof trivial, as some of the answers below implicitly assume it. If that's the case, orion's answer is probably along the lines of what you are looking for. May 19 '14 at 19:12

$$4=1\mod 3$$ and therefore $$4^n=1\mod 3$$ That's it.

If $3$ divides $4^n=2^{2n}$ it would appear in the latter's factorisation into primes.

• Another classical Jasper Loy LHF :) May 19 '14 at 18:51
• @Arkamis It annoys me how much votes he gets for just these one-liners! May 20 '14 at 20:26

Use the fact that if a prime divides a product, then it must divide a single term in the product.

Notice that $4^n=(2^2)^n=2^{2n}$ and $3$ is not a factor of $2^{2n}$.

The prime factors of $4^n$ is the multiset $\{(2, 2n)\}$ and $3 \not \in \{(2, 2n)\}$.

• The prime factor of $4^n$ is $2$. Multiset...? May 19 '14 at 20:19
• Prime factorization is usually best thought of as a multiset of primes. May 19 '14 at 20:29
• Oh, you mean $2$ with multiplicty $2n$. Well, that things is just a set. =P May 19 '14 at 20:31
• A set has unique elements. You need a multiset to keep multiple copies of the same element. May 20 '14 at 6:31