If $3|n^3$, does $3|n$?

Question

If $3|n^3$, does $3|n$? I know that if $2|n^3$, does $2|n$ because $n$ has to be even, but can this apply to $3$ also?

Answer 1

Yes, it applies to all primes. Look up Euclid's lemma and use it twice. First to show $p|n^2$ or $p|n^2$ and in case $p|n$ then use it again to deduce $p|n$.

Answer 2

Yes. If a prime divides a product, then it must divide at least one of the factors.

Let $p$ be a prime such that $p$ divides $ab$ and $p$ does not divide $a$. That means that $mp =ab$ for some integer $m$ and that $a$ and $p$ are coprime, thus we can find integers $s$ and $t$ such that

$$1=sa + tp$$

Multiply both sides by $p$ to obtain

$$b = s(ab) + (tb)p = p(ms+tb),$$

so $p$ divides $b$.

By induction you can show that if $p$ divides a product $a_1\cdots a_{k}$, then $p$ divides one of the factors, so if $p$ divides $n^{k}$ for some positive integer $k$, then $p$ must divide $n$ too.

Answer 3

You can do the fundemental theorem of arithmetic OR you can use the contrapositive proof.
If 3 does not divide n then, $n=3k+1$ or $n=3k+2$
We have two cases now.
Case 1.
$n^2=(3k+1)^2=9k^2+6k+1=3(3k^2+2-1)+2$
since 3k^2+2-1 is an integer 3 does not divide n^2
Case 2.
$n^2=(3k+2)^2=9k^2+12k+4=3(3k^2+4k+1)+1$
since 3k^2+4k+1 is an integer 3 does not divide n^2.

PRoved by contrapositive.