If $3\mid mn$, then $3\mid m$ or $3\mid n$

Question

I'm currently studying proofs and fundamentals, I'm reading a book by my own and I saw this problem.

Theorem Let $m$ and $n$ be integers. If $3\mid mn$, then $3\mid m$ or $3\mid n$.

My proof was the following:

Proof Suppose that$m$ and $n$ are integers such that $3$ does not divide $m$ and $n$. For that, we know that $3$ is not a factor of $m$ and $3$ is not a factor of $n$. We observe that $mn$ is the factors of $m$ times the factors of $n$. So $3$ is not a factor of $mn$. Hence, $3$ does not divide $mn$. Therefore, by the contrapositive, we deduce that if $3$ divides $mn$, then $3$ divides $m$ or $3$ divides $n$.

Is this proof enough? It doesn't sound formally enough to me? Any suggestions? Thank you!

PS I'm not assuming the Euclid's lemma, so I am focusing on a proof without using this result

Answer 1

Even after the edit, I think your proof is not quite right. In essence you are trying to prove a consequence of Euclid's lemma by arguing that when $3$ does not divide both $m$ and $n$ then it cannot divide $mn$. That conclusion depends on $3$ being a prime number, and implicit in your logic is that $mn$ can be decomposed into a factorisation of primes. These ideas usually follow rather than precede Euclid's lemma. What is missing is the greatest common divisor rule, Bezout's identity.

The normal approach is

1. Establish Bezout's identity: for any two integers $a,b$ not both zero, there is a common factor $d$ and integers $x,y$ such that $d=ax+by $ and for every common divisor of $a,b$ divides $d$. This is proved by induction on $n = a+b$.

2. Establish $d$ is unique up to its sign and define define the greatest common divisor as the unique $d > 0$.

3. Prove Euclid's lemma: If $a$ and $b$ have no common factors and $a| bc$ then $a | c$.

4. Define primes as the positive integers $p > 1$ that only have positive divisors $1$ and $p$. Prove that for any $a$ if the prime $p$ does not divide $a$ then the highest common factor of $a$ and $p$ is $1$.

5. The last step is to prove your result: if the prime number $p|ab$ then $p|a$ or $p|b$. The proof is an immediate consequence of Euclid's lemma $(3)$ but can also be proved without explicitly using it by mimicking its proof, as follows,

Suppose $p \not | ~a$. Then by $(4)$ the highest common factor is $1$ and by $(1)$ there exist $x$ and $y$ such that $$1 = ax+py.$$ Then $$b=axb+pby$$ and $p$ divides both terms on the right because $p|ab$ and $p|pby$. Hence $p|b$.

Answer 2

Generally, if a prime $p$ divides a product $mn$, then $p$ divides one factor $m$ or $n$.

Suppose $p$ doesn't divide $n$. Then $gcd(p,n)=1$ and so $1 = ap + bn$. Thus $m = amp + bmn$. Since $p$ divides the right hand side (since $p$ divides $mn$), it divides the left hand side $m$.