# Divisibility

In elementary mathematics, **divisibility** is a relation between two natural numbers:
a number *d* **divides** a number *n*, if *n* is the product of *d* and another natural number *k*.
Since this is a very common notion there are many equivalent expressions:
*d* divides *n* wholly or evenly (if one wants to put emphasis on it),
*d* is a **divisor** or **factor** of *n*,
*n* is **divisible** by *d*, or (conversely) *n* is a **multiple** of *d*.

Every natural number *n* has two divisors, 1 and *n*,
which therefore are called *trivial* divisors.
Any other divisor is called a *proper* divisor.
A natural number (except 1) which has no proper divisor is called *prime*,
a number with proper divisors is called *composite*.

The concept of divisibility can obviously be extended to the integers.
In the integers, every integer *n* has four trivial divisors: 1, -1, *n*, -*n*.
Because of 0 = 0.*n*, any *n* is divisor of 0, and 0 divides only 0.

Further generalizations are to algebraic integers, polynom rings. and rings in general.
(However, divisibility is useless for rational or real numbers:
Because of *ad* = *b* for *d*=*b/a* every rational or real number divides every other rational or real number.)

Some properties:

*a*is a divisor of*a*,- if
*a*is a divisor of*b*, and*b*is a divisor of*a*, then*a*equals*b*, - if
*a*is divides*b*, and*b*divides*c*, then*a*divides*c*, - if
*a*divides*b*and*c*then it also divides*b*+*c*(or, more generally,*kb*+*lc*for arbitrary integers*k*and*l*).

The following property is important and frequently used in number theory.
Therefore it is also called

**Fundamental lemma of number theory**.

- If a prime number divides a product
*ab*, and it does not divide*a*, then it divides*b*.

Properties (1-3) show that "is divisor of" can be seen as a partial order on the natural numbers. In this order,

- 1 is the minimal element since it divides all numbers, and
- 0 is the maximal element since it is a multiple of every number,
- the greatest common divisor is the greatest lower bound (or infimum), and
- the least common multiple is the smallest upper bound (or supremum).

In mathematical notation, "*a* divides *b*" is written as

Using this notation, and

the definition of *is divisor of* is

and the properties listed are written as

The Fundamental Lemma is

and the definition of the order — if one wants to avoid the vertical bar — is given by