Algorithmic Problem Solving

Number theory aims to catalogue the properties of numbers (natural numbers, integers, rational and real numbers), usually in a way that promotes effective calculation. As such, it has always been a central pillar of algorithmic mathematics. The theory is too extensive for us to cover in any detail here. The chapter is therefore about a few core elements of the theory. Sections 15.1 and 15.2 are about reasoning with the standard ordering of numbers. Sections 15.3 and 15.4 are about a different (partial) ordering on natural numbers, the divides relation.

15.1 INEQUALITIES

Expressions involving the at-most relation (denoted by “≤”) or the less-than relation (denoted by “<”) on numbers are traditionally called inequalities. The at-most relation is a so-called total ordering; that is, it is an ordering relation (i.e. reflexive, transitive and anti-symmetric) that is total:

Often it is pronounced “less than or equal to” which stresses the fact that it is the reflexive closure of the less-than relation:

The rule is used when a case analysis on “less than” or “equal to” becomes necessary.

The anti-symmetry of the at-most relation,

is commonly used to establish equalities (everywhere) between ...