305 -Algebra and induction (3)

Definition. is prime iff the only positive divisors of are and .

Proposition. A number is prime iff for all , either or else .  

Proposition. Let be prime, and let be integers. If then either or .

In the more general setting of rings, of which the integers are an example, it is customary to call a number prime when it satisfies the second proposition, and to call it irreducible when it satisfies the definition above. Both notions coincide for the integers, but there are examples of rings where there are irreducible elements that are not prime. We will introduce rings later on in the course.

Mathematical induction. Let . Let be a statement about integers, so for each integer , may or may not hold. Assume

1.   holds, and
   
2. if holds then holds

Then holds.

Strong induction. Let . Let be a statement about integers. Assume

• if with it is the case that holds, then also holds
  

Then holds.

Both induction and strong induction are consequences of the well-ordering principle. In fact, all three statements are equivalent. Most properties about the natural numbers are established by inductive arguments. Here are two examples:

Example 1. For all , .

We also have and . In fact, for all , there is a polynomial with rational coefficients, of degree and leading coefficient such that for all , .

Example 2. For all integers , if then for all , .

Advertisement