I would like to know if there is an elementary proof of the statement in the title --

in particular, a proof which does not use Bezout's lemma or

the generalization of Euclid's lemma$\;$ [If $a\mid bc$ and $(a,b)=1$, then $a\mid c$]

or properties of the GCD (or even the division algorithm).

A similar question has been asked before, such as

If $p$ is a prime and $p \mid ab$, then $p \mid a$ or $p \mid b$. and

A short or elegant proof for if $p \mid n^2$ then $p \mid n$ when $p$ is prime?,

but all of the answers given seem to use these ideas.

  • 3
    $\begingroup$ This is Euclid's Lemma. $\endgroup$ – user236182 Oct 9 '15 at 4:29
  • $\begingroup$ @user236182 You're right - thanks for pointing this out. (Unfortunately, the terminology isn't completely standard; see, for example, the second link given above.) $\endgroup$ – user84413 Oct 9 '15 at 17:38
  • 2
    $\begingroup$ This is a special case of the fact that in any UFD, irreducibles are prime. $\endgroup$ – goblin GONE Oct 10 '15 at 15:33

There is a very elementary proof, which uses only the fact that $\mathbf N$ is a well-ordered set:

Suppose $p$ divides $ab$ and $p$ does not divide $a$. We must show $p$ divides $b$.

Consider the set $\;E=\bigl\{x\in\mathbf N^*\mid p\enspace\text{divides}\enspace xb\bigr\}$: $E\neq\varnothing$ since it contains at least $a$ and $p$. Hence it has a smallest element $x_0$.

Claim: $x_0$ divides all elements in $E$.

Indeed, let $x\in E$. We have $x=qx_0+r$ for a unique pair $(q,r)\enspace (0\le r<x_0)$. As $p$ divides $xb$ and $x_ob$, $p$ divides $xb-qx_0b=rb$. Thus $r$, if not $0$ lies in $E$, which contradicts the minimality of $x_0$. So $r=0$; in other words, $x_0$ divides $x$.

In particular $x_0$ divides $p$ and $a$. As $p$ doesn't divides $a$, this implies $x_0=1$, and $1\in E$, so $p$ divides $1\cdot b=b$.

Added: A slight modification of this proof allows to prove Gauß's lemma: if $n$ (not necessarily prime) divides $ab$, and $n$ and $a$ are coprime, then $n$ divides $b$.

  • $\begingroup$ Neat proof. It's really just the usual proof in disguise, though: instead of proving that $1$ is a linear combination of $p$ and $a$, you just directly prove the weaker statement that $1\in E$ by the same argument, because that weaker statement is all you actually need. $\endgroup$ – Eric Wofsey Oct 8 '15 at 23:22
  • $\begingroup$ Well this proof (I think it's Cauchy's) requites only well order and Euclid's division, really. Anyway Bézoout's relation also stems from that. $\endgroup$ – Bernard Oct 8 '15 at 23:30
  • $\begingroup$ Thank you for this nice answer. $\endgroup$ – user84413 Oct 17 '15 at 17:19

Hilbert famously argued that such a proof can't be too simple...in particular, it can't just depend on properties of multiplication. The example he used was the set of integers congruent to $1$ mod$(4)$. That set is closed under standard multiplication and it contains the identity element $1$. You can speak of a prime element of that set...these primes include usual primes (at least those congruent to $1$ mod$(4)$) but they also include things like $21$ which can not be factored without leaving the set. But then we note that $$21\vert (33)(77)$$ though it divides neither term on its own.

So whatever elementary proof you could come up with would have to fail in this context.

Of course, this doesn't rule out an easy or straightforward argument, but it does set a rather high bar for one.

  • $\begingroup$ Can you give a source for Hilbert's argument? I'd be interested in reading more. $\endgroup$ – Semiclassical Oct 8 '15 at 23:03
  • $\begingroup$ @Semiclassical Just did an internet search, not finding much. Well, plenty of discussions of "Hilbert Numbers", but nothing substantive. I got it via anecdote, from a number theory class too many years ago. I'll go through my books and post if I find anything. $\endgroup$ – lulu Oct 8 '15 at 23:08

This is a very elementary proof (which is due to Dean Hickerson):

Call a triple $(p, a, b)$ of positive integers "bad" if $p$ is prime and $p\mid ab$, but $p\nmid a$ and $p\nmid b$.

Suppose that a bad triple exists. Among all bad triples, consider those in which $p$ is minimal. Among all such triples, choose one in which $a$ is minimal.

Note that $a<p$, since otherwise $(p,a-p,b)$ would also be bad, violating the minimality of $a$. Also, $a>1$, since otherwise $p$ would divide $ab=b$.

Let $q$ be the smallest divisor of $a$ such that $q>1$. (Notice that $a$ is such a divisor, so $q$ exists.) Clearly $q$ is prime, since otherwise it would have a divisor $r$ with $1<r<q$ and then $r$ would be a smaller divisor of $a$.

Let $a=qt.\;$ Since $p\mid ab$, $\;pc=ab=qtb$ for some positive integer $c$.

We now consider two cases:

1) If $q\mid c$, so $c=sq$ for some positive integer $s$, then $ps=tb$.

$\hspace{.2 in}$Since $t\mid a, \;p\nmid t$; so $(p,t,b)$ is bad, violating the minimality of $a$.

2) If $q\nmid c$, then $(q,p,c)$ is bad, violating the minimality of $p$.

In either case, we have a contradiction. Hence there are no bad triples.

  • $\begingroup$ Thanks - this is a very nice proof! $\endgroup$ – user84413 Oct 11 '15 at 17:26

Theorem: If a number $p$ is prime, then whenever $p\mid ab$, $(p\mid a)\lor (p\mid b)$.

Proof: By contradiction. Assume that $p\mid ab$, but $p$ does not divide neither $a$ nor $b$. $a$ is either a prime or a product of primes. Therefore, $a$ can be expressed as: $a = a_1\cdot a_2 \cdot \ldots \cdot a_n$. Analogously for $b$: $b = b_1 \cdot b_2 \cdot \ldots \cdot b_m$. Hence, $ab=a_1 \cdot \ldots \cdot a_n \cdot b_1 \cdot \ldots \cdot b_m$. We also know that $p \mid ab$, so $ab$ can also be expressed as: $ab = p_1 \cdot p_2 \cdot \ldots \cdot p_w$, where $[p_1,\ldots,p_w]$ is a set of $w$ prime numbers in which $p$ is included. Then follows that: $ab = a_1 \cdot \ldots \cdot a_n \cdot b_1 \cdot \ldots \cdot b_m = p_1 \cdot p_2 \cdot \ldots \cdot p_w$. Considering that the prime decomposition of $ab$ is unique, the set $[a_1,\ldots ,a_n,b_1\ldots b_m]$ must contain the same elements as $[p_1,\ldots,p_w]$. But $p$ is included in $[p_1,\ldots,p_w]$. Therefore, $[a_1,\ldots,a_n]$ contains $p$, or $[b_1,\ldots,b_m]$ contains $p$, or both of them do. But if $p$ is included in any of those sets, then $p$ can divide $a$ or $b$ or both, which contradicts the initial assumption. Hence, it is proved that if $p\mid ab$, $(p\mid a)\lor (p\mid b)$.


Elementary proof ?

Well, it's possible at least using the unic factorization theorem (UFT) ? The UFT can be prouved even without Euclide algoritm, so ...

In such case if p | ab the prime p must be a factor of ab wich has ONE UNIC factorization that must be equal to the factorization of a * factorization of b

So p must appear in factorization of a OR in b OR in both So p | a*b => p | a or p |b

Ok ?


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.