# Prove that if $p\mid ab$ where $a$ and $b$ are positive integers and $a\lt p$ then $p\le b$

I have found an old textbook called "Real Variables by Claude W. Burrill and John R. Knudsen" in the first chapter this textbook uses 15 axioms to derive much of the well known and basic facts about the integers, i have been reading and solving all the exercise and so far so good until exercise 1-27 which asks the following: "Prove that if $$p$$ is prime and divides $$ab$$ where $$a$$ and $$b$$ are positive and $$a\lt p$$, then $$p\le b$$." this would be very easy if we assume Euclid's lemma but it hasn't been proven and the very next exercise asks for its proof so i believe that there is a way to prove it without Euclid's lemma but how? Is there even a way to prove this without Euclid's lemma? I also believe i'm not allowed to use Bézout's identity because its proof is exercise 1-29

I have been thinking about this problem since yesterday and i searched online for exercise solutions for this textbook but there was no results.

As another question:does the theorem above imply Euclid's lemma in a straightforward way?

• what did you try? – johnny09 May 26 '19 at 13:37
• Why the downvote? This seems like a very sensible question to me. The OP correctly remarks that this would follow directly from Euclid's Lemma (or other, more or less equivalent results) and is asking if there is a simpler way or if, conversely, this actually implies Euclid. (I have upvoted the question to cancel the mysterious downvote). – lulu May 26 '19 at 13:39
• To your question: every way I can think of to establish the result either starts with one of the (seemingly) deeper claims or it simply mimics one of the proofs of those other claims. I'm not seeing a direct way to bypass those results entirely. – lulu May 26 '19 at 13:41
• Well first it's obvious that $p$ doesn't divide $a$ because $a\lt p$ so using the division algorithm $a=pq+r$ for some unique $q$ and $r$ such that $0\lt r\lt p$ then I've tried substituting but i got stuck, i also tried using the well ordering but i got stuck too. – NACUN May 26 '19 at 13:46
• This amounts to first proving EL in the special case where $\,0<a,b < p$ then deriving the general result using $\,p\mid ab\iff p\mid a(b\bmod p)\,$ in the next exercise. This is one common method of proving EL and almost surely what is intended. – Bill Dubuque May 26 '19 at 14:02

## 2 Answers

We use induction on $$a$$ to prove the claim.

If $$a=1$$, then $$p \mid b$$ and clearly $$p \le b$$.

Now let $$a>1$$ and $$ab=cp$$. We can write $$p=ka+a'$$, where $$k$$ and $$a'$$ are integers and $$0 \le a' < a$$. Moreover, $$a' \ne 0$$ because $$p$$ is prime and $$1. Hence, $$a'b=(p-ka)b=(b-kc)p$$, i.e. $$p \mid a'b$$ and we can apply the induction hypothesis to $$a'.

With regard to your second question: yes, this result implies Euclid's lemma. If we assume that $$p \mid ab$$, but $$p \nmid a$$ and $$p \nmid b$$, then the same would be true if we replace $$a$$ and $$b$$ by $$a_1=a \pmod p$$ and $$b_1=b \pmod p$$ respectively. This contradicts the above result since $$1 \le a_1 and $$1 \le b_1.

• This is precisely Gauss's classical proof, which, interpreted constructively, yields Gauss's inversion algorithm (the 4th proof in the proofs I linked on the question). – Bill Dubuque May 26 '19 at 16:11
• @BillDubuque Unfortunately, Gauss died long ago, so he cannot answer here. lulu explained why the claim isn't true for Hilbert numbers (I wonder why no one mentioned prime ideals or something like that to discourage OP completely). You gave a bunch of links leading to the proof of Euclid's lemma, whereas it was explicitly asked to give a proof not relying on it because that exercise in the book preceded the exercise with Euclid's lemma. So I took the liberty of answering the question that was asked. – John McClane May 26 '19 at 16:46
• Not true. Three of the proofs I linked do not use Euclid's Lemma (one is essentially the same as in your answer, but in constructive fractional form). The other (by FTA) can be also be done directly by descent (e.g. a la Zermelo), though it is more traditional (and conceptual) to use Euclid's Lemma. And the link in my prior comment leads to a link to Gauss's classical proof in Disq. Arith. (same as in your answer). – Bill Dubuque May 26 '19 at 17:20

As a way to suggest that this is at least nearly equivalent to Euclid (or something like it), let's see how it does with the so-called Hilbert Numbers. These are just the naturals of the form $$4k+1$$. They are useful for thinking about things like unique factorization, since such basic properties do not hold for them. For instance, numbers like $$3\times 7=21$$ are "prime" here, since neither $$3$$ nor $$7$$ are Hilbert Numbers. Thus you can have something like $$21\times 209= 33\times 133$$ as two distinct "prime" factorizations of $$4389$$. (Note: Here, of course, $$209=11\times 19$$ and $$133=7\times 19$$ so, in the context of the natural numbers, all we've done is to 'reapportion' the various primes. As all those primes are of the form $$4k+3$$ none of them are Hilbert Numbers, of course).

How does your result fare in your context? Well, the largest "prime" in our example is $$209$$ so let that be $$p$$. Then, letting $$a=33,b=133$$ we see that both $$a,b but $$p\,|\,ab$$ nonetheless. So...whatever proof the authors had in mind, it has to fail for the Hilbert Numbers.

• Why was this downvoted? – Bill Dubuque May 26 '19 at 14:24
• @BillDubuque Thank you, I was wondering about that myself. At a guess, it's because I protested the anonymous user who downvoted the original post. – lulu May 26 '19 at 15:12
• @BillDubuque Because this doesn't answer the question. The claim has nothing to do with Hilbert Numbers. – John McClane May 26 '19 at 16:08
• @JohnMcClane Perhaps pointing that out would have been more useful than an anonymous downvote? In any case, I frequently get criticized for putting detailed remarks as comments instead of posting them as answers, so it is refreshing to be criticized in the opposite direction. Thanks! – lulu May 26 '19 at 16:11
• @lulu By the way, I think that the question was good in itself, so I don't know who downvoted it, it only regards your answer. – John McClane May 26 '19 at 16:14