Number Theory : Prime Divisor Property Proof I'm going through Elements of Number Theory by Stillwell.
One of the exercises is confusing me a bit. Finding a different proof from the normal $b = mab + npb$.
It says it's attributed to Gauss:
Show a prime $p$ cannot divide $a_1b_1$ when $a_1$,$b_1 \lt p$ 
Suppose $p$ divides $a_1b_1$ and show $p$ divides $a_1b_2$
$b_2$ = remainder when $p$ is divided by $b_1$
which gives infinite descent, which I'm not as familar with. 
Then from that show if $p$ divides neither $a$ or $b$ then $p$ divides $a_1b_1$ where $a,b \lt p$
I've been trying to maybe factorise $a_1b_1 = np$
Maybe $n$ or $p = \frac{n(pq+(a_1b_1-pq)}{n}$
so $b_2 = (a_1b_1-pq)$
I'm getting lost though and going in the wrong direction I think any advice/solutions?
 A: If it fails then there is a minimal counterexample $\,n = ab\,$ with $\,p\mid ab,\ p\nmid a,b.\ $ Necessarily $\, b< p\,$ else $\,p\mid a(b\bmod p) = a(b-jp)\,$ would be a smaller counterexample. Then, similarly we deduce that  $\,p\mid a(p\bmod b) = a(p-kb)\,$ is a smaller counterexample, contradiction.
Remark $ $ The integers $n$ such that $\,p\mid an\,$ are closed under subtraction and contain $\,b,p\,$ so they contain $\,\gcd(b,p).\,$ The descent in the above proof corresponds to using the Euclidean algorithm to compute the gcd.
Essentially the same descent was employed by Gauss in Disq. Arith when he gave the first complete and rigorous proof of the Fundamental Theorem of Arithmetic, i.e. existence and uniqueness of factorizations into irreducibles (primes). As explained in the linked post, when interpreted constructively this yields an algorithm for computing inverses $\!\bmod p.\, $ See also below, from a deleted thread.

To compute inverses modulo a prime $\,p,\,$ rather than use the full-blown extended Euclidean algorithm, it is conceptually simpler to use a special case that goes back to Gauss (Disq. Arith. Art.5, 1801). The idea is so simple that it can be taught to bright grade school students. Namely, to compute the fraction $\ 1/b\pmod{\! p}\ $ we repeatedly scale the numerator and denominator in a way that reduces the value of the denominator $\!\bmod p,\,$ i.e. scale $\, a/b\to an/bn\ $ by the least $\,n\,$ such that $\,bn > p\,.\,$ For example, modulo $29$
$$ \frac{1}8\ \to\ \frac{4}{32}\ \equiv\ \frac{4}{3}\ \to\ \frac{40}{30}\ \equiv\ \frac{11}{1}\pmod{\!29}$$
Because each step reduces the denominator, eventually we must reach a denominator of $1$ (not $0$ else we would have $\,bn = p\,$ so $\,b>1\,$ would be a proper factor of the prime $\,p\,$). The algorithm has a vivid interpretation in terms of "clock arithmetic" on a clock face of $\,p\,$ minutes. Namely the reduction step is simply: starting at $\,0,\,$ take $\,n\,$ steps of size $\,b\,$ until you cycle, passing $0\,$ and landing in the interval $[0,b-1].\,$ You can't land on $0\,$ else $ b$ would properly divide $\,p.\,$ Now do the same to this smaller multiple of $\,b.\,$ Each loop around the clock face produces a smaller multiple of $\,b,\,$ so eventually it reaches the multiple $1$. This graphical formulation goes over quite well with bright grade-school students (esp. when enhanced  by visual aids, e.g. periodical curves such as Roulettes (Spirograph curves), Star Polygons - see here).
From this one quickly infers that irreducible integers $\,p\,$ are prime, i.e. $\,p\ |\ a\,b\ \Rightarrow\ p\ |\ a\ \ {\rm or}\ \ p\ |\ b\,.\,$ This is essentially the way that Gauss constructed the first known proof of the Fundamental Theorem of Arithmetic, i.e. unique factorization of integers.
Note that this iterates $\,(b,\,p)\to (p\bmod b,\,p)\,$ vs. $\,(b,\,p)\to (p\bmod b,\, b)\,$ in the Euclidean algorithm. It may fail for composite moduli.
As for uniqueness of inverses $\,a,\,a'\,$ of $\,b,\ $  hint: $\ a\ =\ a\,(b\,a') \ =\ (a\,b)\,a'\, =\ a'$
