Divisibility

In mathematics, a divisor of an integer $n$, also called a factor of $n$, is an integer $m$ that may be multiplied by some integer to produce $n$. In this case, one also says that $n$ is a multiple of $m.$ An integer $n$ is divisible or evenly divisible by another integer $m$ if $m$ is a divisor of $n$; this implies dividing $n$ by $m$ leaves no remainder.

Definition

An integer is divisible by a nonzero integer if there exists an integer such that $n=km$. This is written as
:$m\mid n.$
Other ways of saying the same thing are that divides , is a divisor of , is a factor of , and is a multiple of . If does not divide , then the notation is $m\not\mid n$.

Usually, is required to be nonzero, but is allowed to be zero. With this convention, $m \mid 0$ for every nonzero integer . Some definitions omit the requirement that $m$ be nonzero.

General

Divisors can be negative as well as positive, although sometimes the term is restricted to positive divisors. For example, there are six divisors of 4; they are 1, 2, 4, −1, −2, and −4, but only the positive ones (1, 2, and 4) would usually be mentioned.

1 and −1 divide (are divisors of) every integer. Every integer (and its negation) is a divisor of itself. Integers divisible by 2 are called even, and integers not divisible by 2 are called odd.

1, −1, ''n'' and −''n'' are known as the trivial divisors of ''n''. A divisor of ''n'' that is not a trivial divisor is known as a non-trivial divisor (or strict divisor). A nonzero integer with at least one non-trivial divisor is known as a composite number, while the units −1 and 1 and prime numbers have no non-trivial divisors.

There are divisibility rules that allow one to recognize certain divisors of a number from the number's digits.

Examples

*7 is a divisor of 42 because $7\times 6=42$, so we can say $7\mid 42$. It can also be said that 42 is divisible by 7, 42 is a multiple of 7, 7 divides 42, or 7 is a factor of 42.
*The non-trivial divisors of 6 are 2, −2, 3, −3.
*The positive divisors of 42 are 1, 2, 3, 6, 7, 14, 21, 42.
*The set of all positive divisors of 60, $A=\$, partially ordered by divisibility, has the Hasse diagram:

Further notions and facts

There are some elementary rules:
* If $a \mid b$ and $b \mid c$, then $a \mid c$, i.e. divisibility is a transitive relation.
* If $a \mid b$ and $b \mid a$, then $a = b$ or $a = -b$.
* If $a \mid b$ and $a \mid c$, then $a \mid (b + c)$ holds, as does $a \mid (b - c)$. However, if $a \mid b$ and $c \mid b$, then $(a + c) \mid b$ does ''not'' always hold (e.g. $2\mid6$ and $3 \mid 6$ but 5 does not divide 6).

If $a \mid bc$, and $\gcd(a, b) = 1$, then $a \mid c$.$\gcd$ refers to the greatest common divisor. This is called Euclid's lemma.

If $p$ is a prime number and $p \mid ab$ then $p \mid a$ or $p \mid b$.

A positive divisor of $n$ which is different from $n$ is called a or an of $n$. A number that does not evenly divide $n$ but leaves a remainder is sometimes called an of $n$.

An integer $n > 1$ whose only proper divisor is 1 is called a prime number. Equivalently, a prime number is a positive integer that has exactly two positive factors: 1 and itself.

Any positive divisor of $n$ is a product of prime divisors of $n$ raised to some power. This is a consequence of the fundamental theorem of arithmetic.

A number $n$ is said to be perfect if it equals the sum of its proper divisors, deficient if the sum of its proper divisors is less than $n$, and abundant if this sum exceeds $n$.

The total number of positive divisors of $n$ is a multiplicative function $d(n)$, meaning that when two numbers $m$ and $n$ are relatively prime, then $d(mn)=d(m)\times d(n)$. For instance, $d(42) = 8 = 2 \times 2 \times 2 = d(2) \times d(3) \times d(7)$; the eight divisors of 42 are 1, 2, 3, 6, 7, 14, 21 and 42. However, the number of positive divisors is not a totally multiplicative function: if the two numbers $m$ and $n$ share a common divisor, then it might not be true that $d(mn)=d(m)\times d(n)$. The sum of the positive divisors of $n$ is another multiplicative function $\sigma (n)$ (e.g. $\sigma (42) = 96 = 3 \times 4 \times 8 = \sigma (2) \times \sigma (3) \times \sigma (7) = 1+2+3+6+7+14+21+42$). Both of these functions are examples of divisor functions.

If the prime factorization of $n$ is given by

:$n = p_1^ \, p_2^ \cdots p_k^$

then the number of positive divisors of $n$ is

:$d(n) = (\nu_1 + 1) (\nu_2 + 1) \cdots (\nu_k + 1),$
and each of the divisors has the form

:$p_1^ \, p_2^ \cdots p_k^$

where $0 \le \mu_i \le \nu_i$ for each $1 \le i \le k.$

For every natural $n$, $d(n) < 2 \sqrt$.

Also,
:$d(1)+d(2)+ \cdots +d(n) = n \ln n + (2 \gamma -1) n + O(\sqrt).$

where $\gamma$ is Euler–Mascheroni constant.
One interpretation of this result is that a randomly chosen positive integer ''n'' has an average
number of divisors of about $\ln n$. However, this is a result from the contributions of numbers with "abnormally many" divisors.

In abstract algebra

Ring theory

Division lattice

In definitions that include 0, the relation of divisibility turns the set $\mathbb$ of non-negative integers into a partially ordered set: a complete distributive lattice. The largest element of this lattice is 0 and the smallest is 1. The meet operation ∧ is given by the greatest common divisor and the join operation ∨ by the least common multiple. This lattice is isomorphic to the dual of the lattice of subgroups of the infinite cyclic group $\mathbb$.

See also

* Arithmetic functions
* Euclidean algorithm
* Fraction (mathematics)
* Table of divisors — A table of prime and non-prime divisors for 1–1000
* Table of prime factors — A table of prime factors for 1–1000
* Unitary divisor

Notes

References

*
* Richard K. Guy, ''Unsolved Problems in Number Theory'' (3rd ed), Springer Verlag, 2004 ; section B.
*
*
*
* Øystein Ore, Number Theory and its History, McGraw–Hill, NY, 1944 (and Dover reprints).
*

{{Fractions and ratios

Elementary number theory
Division (mathematics)