305 -Algebra and induction (3)

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

Proposition. A number p>1 is prime iff for all m, either p\mid m or else (p,m)=1. \Box 

Proposition. Let p be prime, and let m,n be integers. If p\mid mn then either p\mid m or p\mid n. \Box

In the more general setting of rings, of which the integers are an example, it is customary to call a number p 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 N\in{\mathbb Z}. Let P(\cdot) be a statement about integers, so for each integer m, P(m) may or may not hold. Assume

  1.  P(N) holds, and
  2. \forall k\ge N,( if P(k) holds then P(k+1) holds).

Then \forall k\ge N,(P(k) holds).

Strong induction. Let N\in{\mathbb Z}. Let P(\cdot) be a statement about integers. Assume

  • \forall k\ge N,( if \forall m with N\le m<k it is the case that P(m) holds, then also P(k) holds).

Then \forall k\ge N,(P(k) 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 n\ge1, \displaystyle \sum_{ i=1}^n i=\frac {n(n+1)}2.

We also have \displaystyle \sum_{ i=1}^n i^2=\frac {n(n+1)(2n+1)}6 and \displaystyle \sum_{ i=1}^n i^3=\left(\frac {n(n+1)}2\right)^2. In fact, for all k\ge 1, there is a polynomial q(x) with rational coefficients, of degree k+1 and leading coefficient \displaystyle \frac1{k+1} such that for all n\ge1\displaystyle \sum_{ i=1}^n i^k=q(n).

Example 2. For all integers a,b, if (a,b)=1 then for all n\ge1, (a^n,b)=1.


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: