0
$\begingroup$

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!

$\endgroup$
4
  • 4
    $\begingroup$ Use that $3$ is prime, that is $3\mid ab$ implies $3\mid a$ or $3\mid b$ $\endgroup$ May 19 '14 at 18:40
  • 6
    $\begingroup$ Prove is the verb, proof is the noun. $\endgroup$
    – Pedro Tamaroff
    May 19 '14 at 18:46
  • 5
    $\begingroup$ $4^n$ is all $4$s and there ain't no $3$ in $4$. $\endgroup$
    – Neal
    May 19 '14 at 19:07
  • $\begingroup$ 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. $\endgroup$ May 19 '14 at 19:12
12
$\begingroup$

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

$\endgroup$
11
$\begingroup$

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

$\endgroup$
2
  • 5
    $\begingroup$ Another classical Jasper Loy LHF :) $\endgroup$
    – Emily
    May 19 '14 at 18:51
  • 1
    $\begingroup$ @Arkamis It annoys me how much votes he gets for just these one-liners! $\endgroup$
    – Sawarnik
    May 20 '14 at 20:26
5
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.