Divisor

The divisors of 10 illustrated with Cuisenaire rods: 1, 2, 5, and 10

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.$Template:Sfn 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 $n$ is divisible by a nonzero integer $m$ if there exists an integer $k$ such that $n=km.$ This is written as

$m\mid n.$

This may be read as that $m$ divides $n,$ $m$ is a divisor of $n,$ $m$ is a factor of $n,$ or $n$ is a multiple of $m.$ If $m$ does not divide $n,$ then the notation is $m\mid ̸n.$Template:SfnTemplate:Sfn

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

• With the convention without an additional constraint on $m,$ $m\mid 0$ for every integer $m.$Template:SfnTemplate:Sfn
• With the convention that $m$ be nonzero, $m\mid 0$ for every nonzero integer $m.$Template:SfnTemplate:Sfnp

General

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, $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 divisorTemplate:Refn). 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

Plot of the number of divisors of integers from 1 to 1000. Prime numbers have exactly 2 divisors, and highly composite numbers are in bold.

• 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=\{1,2,3,4,5,6,10,12,15,20,30,60\},$ 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;$ that is, divisibility is a transitive relation.
• If $a\mid b$ and $b\mid a,$ then $a=b$ or $a=-b.$ (That is, $a$ and $b$ are associates.)
• If $a\mid b$ and $a\mid c,$ then $a\mid (b+c)$ holds, as does $a\mid (b-c).$Template:Efn However, if $a\mid b$ and $c\mid b,$ then $(a+c)\mid b$ does not always hold (for example, $2\mid 6$ and $3\mid 6$ but 5 does not divide 6).
• $a\mid b⟺ac\mid bc$ for nonzero $c$. This follows immediately from writing $ka=b⟺kac=bc$.

If $a\mid bc,$ and $\gcd (a,b)=1,$ then $a\mid c.$Template:Efn 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$ that is different from $n$ is called a Template:Vanchor or an Template:Vanchor of $n$ (for example, the proper divisors of 6 are 1, 2, and 3). A number that does not evenly divide $n$ but leaves a remainder is sometimes called an Template:Vanchor 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)$ (for example, $\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.

Template:AnchorIf the prime factorization of $n$ is given by

$n=p_1^{{\nu }_1}{p}_2^{{\nu }_2}\cdots p_k^{{\nu }_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^{{\mu }_1}{p}_2^{{\mu }_2}\cdots p_k^{{\mu }_k}$

where $0\le {\mu }_i\le {\nu }_i$ for each $1\le i\le k.$

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

Also,Template:Sfn

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

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

Division lattice

Template:Main In definitions that allow the divisor to be 0, the relation of divisibility turns the set $\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.

See also

• 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

References

• Template:Cite book
• Template:Citation; section B
• Template:Cite book
• Template:Citation
• Template:Cite book
• Øystein Ore, Number Theory and its History, McGraw–Hill, NY, 1944 (and Dover reprints).
• Template:Citation
• Template:Cite book