Why doesn't one see more *induction on the number of primes* arguments?

Question

I've used this proof technique to examine what happens when $ax = by$ for example. The proof worked out nicely by introducing the $n$th prime $p$.

Here's exactly where I used it before

What I want from you is either an example where such prime induction proof has also been used, or to explain why you do not see it (at all!).

---

To motivate this, the application is proving that $U_{a} = \{ ax + k : x \in \Bbb{Z}\}$ forms a basis for a topology on $\Bbb{Z}$, given some fixed $k$. Since then if $U_a \cap U_b \ni z \implies w = ax = by$. Hence the need for the proposition. But also apply it to $V_a = \{ ax^r + k : x \in \Bbb{Z}\}$ such that $r\geq 2$, $k \in \Bbb{Z}$ are fixed.

Answer 1

A couple reasons. First, many proofs do induct on the number of primes but only implicitly do so, because they (implicitly) invoke the fact that two naturals $> 1$ are equal iff they have the same prime factors to the same power - whose (rigorous) inductive proof typically involves such an induction.

Second, other proofs may instead use properties of gcds and lcms, which need not depend on prime factorization (they work in any gcd domain, which may not have any primes at all, e.g. the ring of all algebraic integers). For example, see the three proofs below of the result that you linked.

Theorem $\,\ ax = by = m \,\Rightarrow\, m = \ell\, (x,y),\, $ for $\,\ell := {\rm lcm}(a,b)\ \ $ [recall $\,a,b\mid n\iff\ell \mid n$]

Proof $\,\ (x,y) = (m/a,m/b) = m/\ell\, (\ell/a,\ell/b) = m/\ell\ $ by here. $ $ Below are $2$ more proofs.

Or$\ \ (b,a)m = (bax,aby) = ab(x,y),\ $ so $\,\ m = (ab/(a,b))\,(x,y) = \ell\,(x,y)$

Or $\ \ \ell\mid n\!\iff\! a,b\mid n\!\iff\! m\mid nx,ny\!\iff\! m\mid (nx,ny)\!=\!n(x,y)\!\iff\! m/(x,y)\mid n$

Answer 2

My answer I am about to give has little to do with algebra, and nothing to do with primes.

The proof technique you are describing is induction on well-ordered sets. More generally and more fundamental, there is induction on well-founded relations. I say more fundamental because one usually comes across this technique when studying Logic or Set Theory or even Computer Science.

Unless an ordering can be described by operations, such as lattices, there is little algebra going on, and may very well be the reason you, with an interest in Algebra, do not see it often in the written material you come across.