Prove that if $3|mn$, then $3|m$ or $3|n$

Question

I am trying to prove this for integers $m$ and $n$.

I tried to reach prove that $3|m$ by assuming that 3 does not divide $n$, but this is such a basic assumption of mine already that it is hard for me to prove. Could someone help me? Perhaps give me some hints to get me going?

EDIT: Note that this question was an exercise that came before the paragraph on prime factorization (and primes in general).

Answer 1

Try to decompose m and n into their prime factorization.

Answer 2

Hint: Use the (uniqueness of the) prime factorization of $n$, $m$ and $nm$.

Answer 3

Here is a sketch of a contraposition argument. Suppose that $3$ is not a factor of $m$ or of $n$. Then each is either one greater or one less than a multiple of $3$, i.e., there exist integers $j$ and $k$ such that $m=3j\pm1$ and $n=3k\pm1$ (with independent sign choices). Multiply these together and you will have $3(\text{stuff})\pm 1$, so $mn$ is not a multiple of $3$.

Answer 4

Since $\,3\mid k\iff 3\mid -k,\ $ wlog we may assume $\,n\ge 0.\,$ We use (strong) induction on $\,n.\,$

Our bases cases $\,n = 0,1,2\,$ are true: $\ 3\mid 0\cdot m\,\Rightarrow\, 3\mid 0,\ $ and $\ 3\mid 1\cdot m\,\Rightarrow\, 3\mid m,\,$ and $\,3\mid\color{#0a0}{2 m}\,\Rightarrow\, 3\mid m = 3m-\color{#0a0}{2m}.\,$
Else $\ \color{#c00}{n\ge 3}\ $ and $\,3\mid nm\,\Rightarrow\,3\mid \overbrace{(n\!-\!3)}^{\large \color{#c00}{\ge\, 0}}m\,\overset{\rm induct}\Rightarrow\,3\mid n\!-\!3\, (\Rightarrow 3\mid n)\ $ or $\ 3\mid m\ \ \ $ QED

Remark $\ $ The same proof works for any fixed prime $\,p\,$ (with $\,p\,$ base cases to check). But this method does not suffice to give a uniform proof for all primes. That requires a new idea idea, e.g. the Division Algorithm, Euclidean Algorithm, gcds or lcms, or ideals, e.g. see this proof.