This principle just says that any nonempty set of positive integers has a least/smallest element. We can use it to prove that the induction proof technique works, but will not do so here. Instead, we use it as an example to prove the following fact.

Remember, this was a way to prove a statement for all integers \(n\) after a certain point, for instance \(n=1\). There are (usually) two steps in a typical "simple" induction.

• First we prove the base case (often \(n=1\) or \(n=0\)).
• Then we prove the "induction step", that the case \(n=k\) implies case \(n=k+1\))

If an integer \(n\) can be written as a product \(kd=n\) of two integers \(k,d\), then we say that \(d\) divides \(n\), or that \(n\) is divisible by \(d\); we write \(d\mid n\) for this concept.

Examples:

• For instance, \(n\) even just means \(2\mid n\). You should know another name for this.
• Or, the divisors of 6 are ... \(\pm 1, 2, 3, 6\)! (Don't forget negative divisors.)

There are lots of interesting things to say about divisibility. We can prove a somewhat unexpected statement using induction and just what we already know.

There are lots of other propositions about divisibility you are probably familiar with from previous courses. Here is a sampler.

1. If \(a|b\) and \(b|c\) then \(a|c\).
2. If \(a|b\) then \(ca|cb\).
3. If \(c|a\) and \(c|b\) then \(c|au+bv\) for any integers \(u,v\).
4. All divisors of \(n\) are less than or equal to \(n\), unless \(n=0\).