Divisor

This article is about an integer that is a factor of another integer. For a number used to divide another number in a division operation, see Division (mathematics). For other uses, see Divisor (disambiguation).

"Divisible" redirects here. For divisibility of groups, see Divisible group.

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

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

Definition

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

${\displaystyle m\mid n.}$ 

Other ways of saying the same thing are that m divides n, m is a divisor of n, m is a factor of n, and n is a multiple of m. If m does not divide n, then the notation is ${\displaystyle m\not \mid n}$ .^[1][2]

Usually, m is required to be nonzero, but n is allowed to be zero. With this convention, ${\displaystyle m\mid 0}$  for every nonzero integer m.^[1][2] Some definitions omit the requirement that ${\displaystyle m}$  be nonzero.^[3]

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^[4]). 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 ${\displaystyle 7\times 6=42}$ , so we can say ${\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\}}$ , partially ordered by divisibility, has the Hasse diagram:

 

Further notions and facts

There are some elementary rules:

• If ${\displaystyle a\mid b}$  and ${\displaystyle b\mid c}$ , then ${\displaystyle a\mid c}$ , i.e. divisibility is a transitive relation.
• If ${\displaystyle a\mid b}$  and ${\displaystyle b\mid a}$ , then ${\displaystyle a=b}$  or ${\displaystyle a=-b}$ .
• If ${\displaystyle a\mid b}$  and ${\displaystyle a\mid c}$ , then ${\displaystyle a\mid (b+c)}$  holds, as does ${\displaystyle a\mid (b-c)}$ .^[5] However, if ${\displaystyle a\mid b}$  and ${\displaystyle c\mid b}$ , then ${\displaystyle (a+c)\mid b}$  does not always hold (e.g. ${\displaystyle 2\mid 6}$  and ${\displaystyle 3\mid 6}$  but 5 does not divide 6).

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

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

A positive divisor of ${\displaystyle n}$  which is different from ${\displaystyle n}$  is called a proper divisor or an aliquot part of ${\displaystyle n}$ . A number that does not evenly divide ${\displaystyle n}$  but leaves a remainder is sometimes called an aliquant part of ${\displaystyle n}$ .

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

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

The total number of positive divisors of ${\displaystyle n}$  is a multiplicative function ${\displaystyle d(n)}$ , meaning that when two numbers ${\displaystyle m}$  and ${\displaystyle n}$  are relatively prime, then ${\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)}$ ; 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}$  and ${\displaystyle n}$  share a common divisor, then it might not be true that ${\displaystyle d(mn)=d(m)\times d(n)}$ . The sum of the positive divisors of ${\displaystyle n}$  is another multiplicative function ${\displaystyle \sigma (n)}$  (e.g. ${\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}$  is given by

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

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

${\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}}}$ 

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

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

Also,^[6]

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

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

In abstract algebra

Ring theory

Main article: Divisibility (ring theory)

Division lattice

Main article: Division lattice

In definitions that include 0, the relation of divisibility turns the set ${\displaystyle \mathbb {N} }$  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 ${\displaystyle \mathbb {Z} }$ .

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

1. ${\displaystyle \gcd }$  refers to the greatest common divisor.

1. Hardy & Wright 1960, p. 1
2. Niven, Zuckerman & Montgomery 1991, p. 4
3. Durbin 2009, p. 57, Chapter III Section 10
4. "FoCaLiZe and Dedukti to the Rescue for Proof Interoperability by Raphael Cauderlier and Catherine Dubois" (PDF).
5. ${\displaystyle a\mid b,\,a\mid c\Rightarrow b=ja,\,c=ka\Rightarrow b+c=(j+k)a\Rightarrow a\mid (b+c)}$ . Similarly, ${\displaystyle a\mid b,\,a\mid c\Rightarrow b=ja,\,c=ka\Rightarrow b-c=(j-k)a\Rightarrow a\mid (b-c)}$ 
6. Hardy & Wright 1960, p. 264, Theorem 320

References

• Durbin, John R. (2009). Modern Algebra: An Introduction (6th ed.). New York: Wiley. ISBN 978-0470-38443-5.
• Richard K. Guy, Unsolved Problems in Number Theory (3rd ed), Springer Verlag, 2004 ISBN 0-387-20860-7; section B.
• Hardy, G. H.; Wright, E. M. (1960). An Introduction to the Theory of Numbers (4th ed.). Oxford University Press.
• Herstein, I. N. (1986), Abstract Algebra, New York: Macmillan Publishing Company, ISBN 0-02-353820-1
• Niven, Ivan; Zuckerman, Herbert S.; Montgomery, Hugh L. (1991). An Introduction to the Theory of Numbers (5th ed.). John Wiley & Sons. ISBN 0-471-62546-9.
• Øystein Ore, Number Theory and its History, McGraw–Hill, NY, 1944 (and Dover reprints).
• Sims, Charles C. (1984), Abstract Algebra: A Computational Approach, New York: John Wiley & Sons, ISBN 0-471-09846-9