When does $\,n\mid q^3 \Rightarrow n\mid q\,$?

Question

I think this is true because of prime factorisations, i.e.

If $3$ a factor of the prime factorisation of $q^3$, then $3$ is a factor of the prime factorisation of $q$.

Therefore If $3$ divides $q^3$, then $3$ divides $q$.

Or for a general case, if $n$ divides $q^3$; then $n$ divides $q$. Is this correct?

Answer 1

The generalization is false: example: $n = 9$, and $q = 3$.

But the first claim is true.

Answer 2

This is an instance of Euclid's lemma: if a prime number divides a product then it divides one of the factors. Your second claim is only true if you additionally assume $n$ to be prime.

Euclid's lemma can be derived from prime factorization as you suggest, but usually it is used to prove prime factorization, an independent proof uses the Bezout identity http://en.wikipedia.org/wiki/Euclid's_lemma.

Answer 3

$\ n\mid q^3\,\Rightarrow\,n\mid q\ $ is true $\forall q\,$ iff $\,n\,$ is squarefree. Indeed, if so, $\,n\,$ is a product of distinct primes $p_i$ so by Euclid's Lemma $\,p_i\mid q^3\Rightarrow\,p_i\mid q,\,$ thus $\,n = {\rm lcm}(p_i)\mid q.\,$

Conversely, if $\,n\,$ is not squarefree then $\,n = ab^2,\ b>1,\,$ hence $\,n\mid (ab)^3\,$ but $\,n = ab^2\nmid ab.\ $

See this answer for a handful of characterizations of "squarefree".