Questions about Divisibility of $2^n$ by $3$

Question

Why is it that $\forall n \in N$, $2^n$ is not divisible by $3$?

I can prove it easily by induction, but I don't understand the intuition of why this is true. Could anyone please supply the intuition? [This has been answered.]

Moreover, I understand that there's also a proof of this fact that uses modular arithmetic. How does this proof go? [Also answered - it follows immediately from the definition of the modulus operation.]

Answer 1

$2^n$ has a prime factorization containing only $2$s. So it can never have 3 has one of its prime factors by the Unique Factorization Theorem.

I can think of the proof using this.

Suppose for a contradiction that $2^n$ is divisible by 3. Then $$2^n\equiv 0\mod3$$

That means $3$ divides $2^n$. Now $2^n =3k$ for some $k\in \mathbb{Z}$.

Use the first statement I mentioned above to arrive at a contradiction.

Answer 2

$$2^n=\underbrace{2\times2\times\cdots\times2}_{\text{$n$ times}}$$

But for a number to be divisible by $3$ it requires that one of its prime factors is $3$, whereas in the prime factorization of $2^n$ only $2$ appears. Therefore, $2^n$ is not divisible by $3$ for $\forall n\in\mathbb N$.

In the same sense we can generalize this result: If $p$ is a prime number and $n\in\mathbb N$ then $p^n$ cannot have another prime factor other than $p$, it is therefore divisible only by $p$ or $p$ to some power. Example: $5^4$ is not divisible by $2$ nor $3$ for instance but it is divisible by $5$ and $25=5^2$.

Answer 3

If $p$ is prime then $p\mid k\times m$ implies that $p\mid k$ or $p\mid m$. Applying that (eventually more times) on $3\mid 2^n$ leads to $3\mid 2$ wich is not true.

Answer 4

While $\,3\nmid 2^n\,$ follows by FTA = existence & uniqueness of prime factorizations, we can give a much simpler modular arithmetic proof that $\rm \ a\nmid (a\!-\!1)^n =: \color{#0a0}b,\,$ for all integers $\rm\ \color{brown}{a\ne \pm1},\ $namely

$\rm mod\,\ a\!:\,\ \color{#c00}{a\equiv 0}\ \Rightarrow \color{#0a0}b = (\color{#c00}{a}\!-\!1)^n\equiv (\color{#c00}{0}\!-\!1)^n \equiv \pm1 \color{#0a0}{\not\equiv 0}\ \ (else\ \ \color{brown}{a\mid\pm1})\,$ by Congruence Laws

So we have shown $\rm\ \color{#0a0}{b\not\equiv 0}\pmod a,\:$ i.e. $\rm\,\ a\nmid b.\ \ \bf\small QED$

Alternatively, if modular arithmetic is unfamiliar, we can prove it by induction, with the inductive step being $\rm\ a\mid \color{brown}{(a\!-\!1)n}\ \Rightarrow\ a\mid n = an-\color{brown}{(a\!-\!1)n}\ $ [which is a special case of Euclid's Lemma, i.e. $\rm\, (a,m)=1,\ a\mid mn\,\Rightarrow\, a\mid n\,$]. $ $ So $\rm\ a\mid (a\!-\!1)^n \Rightarrow\ a\mid (a\!-\!1)^{n-1} \Rightarrow \cdots \Rightarrow\ a\mid 1.$

Or we can use the Binomial Theorem to write $\rm\, (a-1)^n = (\cdots)a + (-1)^n,\,$ which is essentially equivalent to the first proof using congruence arithmetic.

Answer 5

Hint:

$\forall n, 2^n \equiv (-1)^n $ (mod 3)