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}$


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.


$$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?



$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$


  • 3
    $\begingroup$ What's the meaning of "$p|n\wedge$ b" ??? $\endgroup$ – Yves Daoust May 6 '18 at 18:17
  • $\begingroup$ @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$. $\endgroup$ – K. Claesson May 6 '18 at 18:21
  • 1
    $\begingroup$ And what's the meaning of "$p$ is a divisor to $m$ and/or $m$" ??? $\endgroup$ – Yves Daoust May 6 '18 at 18:23
  • 1
    $\begingroup$ It should be $p|m \lor p|n.$ $\endgroup$ – coffeemath May 6 '18 at 18:24
  • $\begingroup$ Note you cannot assume $m,n$ each a product of distinct primes. $\endgroup$ – 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.