Divisor

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

An integer ${\displaystyle n}${\displaystyle n} is divisible by a nonzero integer ${\displaystyle m}${\displaystyle m} if there exists an integer ${\displaystyle k}${\displaystyle k} such that ${\displaystyle n=km.}${\displaystyle n=km.} This is written as

${\displaystyle m\mid n.}${\displaystyle m\mid n.}

This may be read as that ${\displaystyle m}${\displaystyle m} divides ${\displaystyle n,}${\displaystyle n,} ${\displaystyle m}${\displaystyle m} is a divisor of ${\displaystyle n,}${\displaystyle n,} ${\displaystyle m}${\displaystyle m} is a factor of ${\displaystyle n,}${\displaystyle n,} or ${\displaystyle n}${\displaystyle n} is a multiple of ${\displaystyle m.}${\displaystyle m.} If ${\displaystyle m}${\displaystyle m} does not divide ${\displaystyle n,}${\displaystyle n,} then the notation is ${\displaystyle m\not \mid n.}${\displaystyle m\not \mid n.}^{[2] [3]}

There are two conventions, distinguished by whether ${\displaystyle m}${\displaystyle m} is permitted to be zero:

• With the convention without an additional constraint on ${\displaystyle m,}${\displaystyle m,} ${\displaystyle m\mid 0}${\displaystyle m\mid 0} for every integer ${\displaystyle m.}${\displaystyle m.}^{[2] [3]}
• With the convention that ${\displaystyle m}${\displaystyle m} be nonzero, ${\displaystyle m\mid 0}${\displaystyle m\mid 0} for every nonzero integer ${\displaystyle m.}${\displaystyle m.}^{[4] [5]}

Divisors can be negative as well as positive, although often 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, ${\displaystyle n}${\displaystyle n} and ${\displaystyle -n}${\displaystyle -n} are known as the trivial divisors of ${\displaystyle n.}${\displaystyle n.} A divisor of ${\displaystyle n}${\displaystyle n} that is not a trivial divisor is known as a non-trivial divisor (or strict divisor^[6] ). 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.

• 7 is a divisor of 42 because ${\displaystyle 7\times 6=42,}${\displaystyle 7\times 6=42,} so we can say ${\displaystyle 7\mid 42.}${\displaystyle 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, ${\displaystyle A=\{1,2,3,4,5,6,10,12,15,20,30,60\},}${\displaystyle A=\{1,2,3,4,5,6,10,12,15,20,30,60\},} partially ordered by divisibility, has the Hasse diagram:

There are some elementary rules:

• If ${\displaystyle a\mid b}${\displaystyle a\mid b} and ${\displaystyle b\mid c,}${\displaystyle b\mid c,} then ${\displaystyle a\mid c;}${\displaystyle a\mid c;} that is, divisibility is a transitive relation.
• If ${\displaystyle a\mid b}${\displaystyle a\mid b} and ${\displaystyle b\mid a,}${\displaystyle b\mid a,} then ${\displaystyle a=b}${\displaystyle a=b} or ${\displaystyle a=-b.}${\displaystyle a=-b.} (That is, ${\displaystyle a}${\displaystyle a} and ${\displaystyle b}${\displaystyle b} are associates.)
• If ${\displaystyle a\mid b}${\displaystyle a\mid b} and ${\displaystyle a\mid c,}${\displaystyle a\mid c,} then ${\displaystyle a\mid (b+c)}${\displaystyle a\mid (b+c)} holds, as does ${\displaystyle a\mid (b-c).}${\displaystyle a\mid (b-c).}^[a] However, if ${\displaystyle a\mid b}${\displaystyle a\mid b} and ${\displaystyle c\mid b,}${\displaystyle c\mid b,} then ${\displaystyle (a+c)\mid b}${\displaystyle (a+c)\mid b} does not always hold (for example, ${\displaystyle 2\mid 6}${\displaystyle 2\mid 6} and ${\displaystyle 3\mid 6}${\displaystyle 3\mid 6} but 5 does not divide 6).
• ${\displaystyle a\mid b\iff ac\mid bc}${\displaystyle a\mid b\iff ac\mid bc} for nonzero ${\displaystyle c}${\displaystyle c}. This follows immediately from writing ${\displaystyle ka=b\iff kac=bc}${\displaystyle ka=b\iff kac=bc}.

If ${\displaystyle a\mid bc,}${\displaystyle a\mid bc,} and ${\displaystyle \gcd(a,b)=1,}${\displaystyle \gcd(a,b)=1,} then ${\displaystyle a\mid c.}${\displaystyle a\mid c.}^[b] This is called Euclid's lemma.

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

A positive divisor of ${\displaystyle n}${\displaystyle n} that is different from ${\displaystyle n}${\displaystyle n} is called a proper divisor or an aliquot part of ${\displaystyle n}${\displaystyle n} (for example, the proper divisors of 6 are 1, 2, and 3). A number that does not evenly divide ${\displaystyle n}${\displaystyle n} but leaves a remainder is sometimes called an aliquant part of ${\displaystyle n.}${\displaystyle n.}

An integer ${\displaystyle n>1}${\displaystyle 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 ${\displaystyle n}${\displaystyle n} is a product of prime divisors of ${\displaystyle n}${\displaystyle n} raised to some power. This is a consequence of the fundamental theorem of arithmetic.

A number ${\displaystyle n}${\displaystyle 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 ${\displaystyle n,}${\displaystyle n,} and abundant if this sum exceeds ${\displaystyle n.}${\displaystyle n.}

The total number of positive divisors of ${\displaystyle n}${\displaystyle n} is a multiplicative function ${\displaystyle d(n),}${\displaystyle d(n),} meaning that when two numbers ${\displaystyle m}${\displaystyle m} and ${\displaystyle n}${\displaystyle n} are relatively prime, then ${\displaystyle d(mn)=d(m)\times d(n).}${\displaystyle d(mn)=d(m)\times d(n).} For instance, ${\displaystyle d(42)=8=2\times 2\times 2=d(2)\times d(3)\times d(7)}${\displaystyle 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 ${\displaystyle m}${\displaystyle m} and ${\displaystyle n}${\displaystyle n} share a common divisor, then it might not be true that ${\displaystyle d(mn)=d(m)\times d(n).}${\displaystyle d(mn)=d(m)\times d(n).} The sum of the positive divisors of ${\displaystyle n}${\displaystyle n} is another multiplicative function ${\displaystyle \sigma (n)}${\displaystyle \sigma (n)} (for example, ${\displaystyle \sigma (42)=96=3\times 4\times 8=\sigma (2)\times \sigma (3)\times \sigma (7)=1+2+3+6+7+14+21+42}${\displaystyle \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 ${\displaystyle n}${\displaystyle n} is given by

${\displaystyle n=p_{1}^{\nu _{1}},円p_{2}^{\nu _{2}}\cdots p_{k}^{\nu _{k}}}${\displaystyle n=p_{1}^{\nu _{1}},円p_{2}^{\nu _{2}}\cdots p_{k}^{\nu _{k}}}

then the number of positive divisors of ${\displaystyle n}${\displaystyle n} is

${\displaystyle d(n)=(\nu _{1}+1)(\nu _{2}+1)\cdots (\nu _{k}+1),}${\displaystyle d(n)=(\nu _{1}+1)(\nu _{2}+1)\cdots (\nu _{k}+1),}

and each of the divisors has the form

${\displaystyle p_{1}^{\mu _{1}},円p_{2}^{\mu _{2}}\cdots p_{k}^{\mu _{k}}}${\displaystyle p_{1}^{\mu _{1}},円p_{2}^{\mu _{2}}\cdots p_{k}^{\mu _{k}}}

where ${\displaystyle 0\leq \mu _{i}\leq \nu _{i}}${\displaystyle 0\leq \mu _{i}\leq \nu _{i}} for each ${\displaystyle 1\leq i\leq k.}${\displaystyle 1\leq i\leq k.}

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

Also,^[7]

${\displaystyle d(1)+d(2)+\cdots +d(n)=n\ln n+(2\gamma -1)n+O({\sqrt {n}}),}${\displaystyle d(1)+d(2)+\cdots +d(n)=n\ln n+(2\gamma -1)n+O({\sqrt {n}}),}

where ${\displaystyle \gamma }${\displaystyle \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 ${\displaystyle \ln n.}${\displaystyle \ln n.} However, this is a result from the contributions of numbers with "abnormally many" divisors.

In definitions that allow the divisor to be 0, the relation of divisibility turns the set ${\displaystyle \mathbb {N} }${\displaystyle \mathbb {N} } of non-negative integers into a partially ordered set that is 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 Z.

• Arithmetic functions
• Euclidean algorithm
• Fraction (mathematics)
• Integer factorization
• 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

• Elementary number theory
• Division (mathematics)

• Articles with short description
• Short description is different from Wikidata
• Articles lacking in-text citations from June 2015
• All articles lacking in-text citations