# Prove that $p|nm \Rightarrow p|n \lor p|m, \hspace{0,1 cm} p$ is a prime; $n,m \in \mathbb{Z}$

Is the below proof rigorous and formally correct?

To Prove: $p|nm \Rightarrow p|n \lor p|m, \hspace{0,1 cm} p$ is a prime; $n,m \in \mathbb{Z}$

Proof:

Let $$p|nm \Leftrightarrow \frac {nm} {p} \in \mathbb{Z}, \\ p \, \text{is a prime}; n,m \in \mathbb{Z}$$

Assume that every integer greater than 1 is either prime or a product of primes.

Then,

$$n = a_1 a_2...a_j, \hspace{0.1 cm} a_1, a_2, ..., a_j \hspace{0.1 cm}\text{are prime}$$

$$m = b_1 b_2...b_k, \hspace{0.1 cm} b_1, b_2, ..., b_k \hspace{0.1 cm}\text{are prime}$$

$$\frac {nm} {p} \in \mathbb{Z} \Leftrightarrow \frac {a_1 a_2...a_j \times b_1 b_2...b_k} {p} \in \mathbb{Z}$$

$$\therefore \text{At least one of the primes} \hspace{0.1 cm} a_1, a_2, ..., a_j, b_1, b_2, ..., b_k \hspace{0.1 cm} \text{are equal to} \hspace{0.1 cm} p \Leftrightarrow p|n \lor p|m$$

$$\therefore p|nm \Rightarrow p|n \lor p|m$$

However, the above conclusion only holds true if our assumption, "every integer greater than 1 is either prime or a product of primes", is true. Below, this is proved by strong induction.

Base case: 2 is a prime.

Induction hypothesis: $\forall x \in \{x|2 \leq x \leq n \}, x$ is either prime or a product of primes.

If $n + 1$ is prime, there is nothing more to prove.

If $n + 1$ is not prime, it is divisible by at least one integer that is not $1$ or $n+1$. Thus,
$$n + 1 = cd, \hspace{0.1 cm} 2 \leq c \leq d \leq n$$

By the induction hypothesis, $c = c_1 c_2 ... c_l$ and $d = d_1 d_2 ... d_i$, $\hspace{0.1 cm} c_1, c_2, ..., c_l, d_1, d_2, ..., d_i$ are prime.

$$\therefore n + 1 = c_1 c_2 ... c_l \times d_1 d_2 ... d_i$$

$$\therefore \hspace{0.1 cm} \text{Every integer greater than 1 is either prime or a product of primes.}$$

With this it can be concluded that the assumption in the first proof was true and, hence, $p|nm \Rightarrow p|n \lor p|m, \hspace{0,1 cm} p$ is a prime, $n,m \in \mathbb{Z}$

Initial Version of Question

Below you will find the initial version of this question. This initial version contains two notation errors and one logical error. Use this version as a reference for understanding the answer and comments that were published before 03/06/2018. In the above version of this question all errors that were brought to light before 03/06/2018 have been resolved.

Original Question Title: Prove that $p|n\wedge b$ given that $p$ is a prime and $n,m$ are integers.

Let $p$ be a prime number. Let $n$ and $m$ be integers such that $p|nm$. Prove that $p|n\wedge m$.

Is the below proof rigorous and formally correct?

Proof:

Let

$p|nm \Leftrightarrow \frac{nm}{p}=k\in\mathbb{Z}$

$n=ab...c, ab...c$ are distinct prime numbers.

$m=de..f, de..f$ are distinct prime numbers.

$\frac{nm}{p}=\frac{ab...c\times de..f}{p}=k\in\mathbb{Z}$

The quotient of a prime number and any other number that is not itself or 1 is not an integer.

$\therefore$ at least one of the primes $a,b,...,c,d,e,...f$ must be $p$.

$\therefore p|n\wedge b$

Q.E.D

• What's the meaning of "$p|n\wedge$ b" ??? – Yves Daoust May 6 '18 at 18:17
• @Yves As far as I've understood $p|n \wedge m$ means that $p$ is a divisor to $m$ and/or $m$. I've mistakenly written $b$ instead of $m$. – K. Claesson May 6 '18 at 18:21
• And what's the meaning of "$p$ is a divisor to $m$ and/or $m$" ??? – Yves Daoust May 6 '18 at 18:23
• It should be $p|m \lor p|n.$ – coffeemath May 6 '18 at 18:24
• Note you cannot assume $m,n$ each a product of distinct primes. – coffeemath May 6 '18 at 18:26

The usual proof of this does not use the prime factorizations of $m,n.$ Perhaps because the result, $p \mid mn \implies p \mid m \lor p \mid n,$ ["Euclid's Lemma"] is used during the proof of unique prime factorization in the first place.
That said, one often seen proof is to start by assuming not $p \mid m$ and showing that then $p \mid n.$ Since $p$ does not divide $m$ we have $\gcd(p,m)=1.$ [the only divisors of $p$ are $\pm 1, \pm p$ so a positive common divisor of $p,m$ cannot be $p$ and thus is $1.$
Then there are integers $x,y$ with $px+my=1.$ multiply this by $n$ to get $pnx+mny=n.$ On the left side, p divides both terms (recall we are assuming $p \mid mn.$ Hence $p \mid n$ to finish.