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?
 A: 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<a<p$. Hence, $a'b=(p-ka)b=(b-kc)p$, i.e. $p \mid a'b$ and we can apply the induction hypothesis to $a'<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<p$ and $1 \le b_1<p$.
A: 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<p$ but $p\,|\,ab$ nonetheless.  So...whatever proof the authors had in mind, it has to fail for the Hilbert Numbers.
