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:

1. a is a divisor of a,
2. if a is a divisor of b, and b is a divisor of a, then a equals b,
3. if a is divides b, and b divides c, then a divides c,
4. 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

$a\mid b$

Using this notation, and

$a,b,c,d,k,l,n,p\in \mathbb {N} ,p\ {\textrm {prime}}$

the definition of is divisor of is

$d\mid n:\Leftrightarrow (\exists k)dk=n$

and the properties listed are written as

1. $a\mid a$
2. $a\mid b\;,\ b\mid a\Rightarrow a=a$
3. $a\mid b\;,\ b\mid c\Rightarrow a\mid c$
4. $a\mid b\;,\ a\mid c\Rightarrow a\mid (kb+lc)$

The Fundamental Lemma is

• $p\mid ab\;,\ p\not \;\mid a\Rightarrow p\mid b$

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

$a\leq b:\Leftrightarrow a\mid b$