View source for Divisor

{{short description|Integer that is a factor of another integer}}
{{more footnotes|date=June 2015}}
{{about|an integer that is a factor of another integer|a number used to divide another number in a division operation|Division (mathematics)|other uses|}}
{{redirect|Divisible|divisibility of groups|Divisible group}}
[[File:Cuisenaire ten.JPG|thumb|The divisors of 10 illustrated with [[Cuisenaire rods]]: 1, 2, 5, and 10]]

In [[mathematics]], a '''divisor''' of an integer <math>n,</math> also called a '''factor''' of <math>n,</math> is an [[integer]] <math>m</math> that may be multiplied by some integer to produce <math>n.</math>{{sfn|ps=|Tanton|2005|p=185}} In this case, one also says that <math>n</math> is a ''[[Multiple (mathematics)|multiple]]'' of <math>m.</math> An integer <math>n</math> is '''divisible''' or '''evenly divisible''' by another integer <math>m</math> if <math>m</math> is a divisor of <math>n</math>; this implies dividing <math>n</math> by <math>m</math> leaves no remainder.

== Definition ==
An [[integer]] <math>n</math> is divisible by a nonzero integer <math>m</math> if there exists an integer <math>k</math> such that <math>n=km.</math> This is written as
: <math>m\mid n.</math>
This may be read as that <math>m</math> divides <math>n,</math> <math>m</math> is a divisor of <math>n,</math> <math>m</math> is a factor of <math>n,</math> or <math>n</math> is a multiple of <math>m.</math> If <math>m</math> does not divide <math>n,</math> then the notation is <math>m\not\mid n.</math>{{sfn|ps=|Hardy|Wright|1960|p=1}}{{sfn|ps=|Niven|Zuckerman|Montgomery|1991|p=4}}

There are two conventions, distinguished by whether <math>m</math> is permitted to be zero:
* With the convention without an additional constraint on <math>m,</math> <math>m \mid 0</math> for every integer <math>m.</math>{{sfn|ps=|Hardy|Wright|1960|p=1}}{{sfn|ps=|Niven|Zuckerman|Montgomery|1991|p=4}}
* With the convention that <math>m</math> be nonzero, <math>m \mid 0</math> for every nonzero integer <math>m.</math>{{sfn|ps=|Sims|1984|p=42}}{{sfnp|ps=|Durbin|2009|p=57|loc=Chapter III Section 10}}

== General ==
Divisors can be [[negative number|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 odd numbers|even]], and integers not divisible by 2 are called [[even and odd numbers|odd]].

1, −1, <math>n</math> and <math>-n</math> are known as the '''trivial divisors''' of <math>n.</math> A divisor of <math>n</math> that is not a trivial divisor is known as a '''non-trivial divisor''' (or strict divisor{{refn|{{cite web| url = https://perso.crans.org/cauderlier/org/ITP17_draft.pdf| title = FoCaLiZe and Dedukti to the Rescue for Proof Interoperability by Raphael Cauderlier and Catherine Dubois}}}}). A nonzero integer with at least one non-trivial divisor is known as a [[composite number]], while the [[Unit (ring theory)|units]] −1 and 1 and [[prime number]]s have no non-trivial divisors.

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

== Examples ==
[[File:Highly composite numbers.svg|thumb|250px|Plot of the number of divisors of integers from 1 to 1000. [[Prime number]]s have exactly 2 divisors, and [[highly composite number]]s are in bold.]]
* 7 is a divisor of 42 because <math>7\times 6=42,</math> so we can say <math>7\mid 42.</math> It can also be said that 42 is divisible by 7, 42 is a [[multiple (mathematics)|multiple]] of 7, 7 divides 42, or 7 is a factor of 42.
* The non-trivial divisors of 6 are 2, &minus;2, 3, &minus;3.
* The positive divisors of 42 are 1, 2, 3, 6, 7, 14, 21, 42.
* The [[Set (mathematics)|set]] of all positive divisors of 60, <math>A=\{1,2,3,4,5,6,10,12,15,20,30,60\},</math> [[Partially ordered set|partially ordered]] by divisibility, has the [[Hasse diagram]]:

[[File:Lattice of the divisibility of 60; factors.svg|center|350px]]

== Further notions and facts <!-- Perfect number links here. --> ==
There are some elementary rules:
* If <math>a \mid b</math> and <math>b \mid c,</math> then <math>a \mid c;</math> that is, divisibility is a [[transitive relation]].
* If <math>a \mid b</math> and <math>b \mid a,</math> then <math>a = b</math> or <math>a = -b.</math> (That is, <math>a</math> and <math>b</math> are [[Divisibility (ring theory)|associates]].)
* If <math>a \mid b</math> and <math>a \mid c,</math> then <math> a \mid (b + c)</math> holds, as does <math> a \mid (b - c).</math>{{efn|<math>a \mid b,\, a \mid c</math> <math>\Rightarrow \exists j\colon ja=b,\, \exists k\colon ka=c</math> <math>\Rightarrow \exists j,k\colon (j+k)a=b+c</math> <math>\Rightarrow a \mid (b+c).</math> Similarly, <math>a \mid b,\, a \mid c</math> <math>\Rightarrow \exists j\colon ja=b,\, \exists k\colon ka=c</math> <math>\Rightarrow \exists j,k\colon (j-k)a=b-c</math> <math>\Rightarrow a \mid (b-c).</math>}} However, if <math>a \mid b</math> and <math>c \mid b,</math> then <math>(a + c) \mid b</math> does ''not'' always hold (for example, <math>2\mid6</math> and <math>3 \mid 6</math> but 5 does not divide 6).
* <math>a \mid b \iff ac \mid bc</math> for nonzero <math>c </math>. This follows immediately from writing <math>ka = b \iff kac = bc </math>.

If <math>a \mid bc,</math> and <math>\gcd(a, b) = 1,</math> then <math>a \mid c.</math>{{efn|<math>\gcd</math> refers to the [[greatest common divisor]].}} This is called [[Euclid's lemma]].

If <math>p</math> is a prime number and <math>p \mid ab</math> then <math>p \mid a</math> or <math>p \mid b.</math>

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

An integer <math>n > 1</math> 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 <math>n</math> is a product of [[prime factor|prime divisors]] of <math>n</math> raised to some power. This is a consequence of the [[fundamental theorem of arithmetic]].

A number <math>n</math> is said to be [[perfect number|perfect]] if it equals the sum of its proper divisors, [[deficient number|deficient]] if the sum of its proper divisors is less than <math>n,</math> and [[abundant number|abundant]] if this sum exceeds <math>n.</math>

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

{{anchor|number_of_divisors_formula}}If the [[prime factorization]] of <math>n</math> is given by
: <math> n = p_1^{\nu_1} \, p_2^{\nu_2} \cdots p_k^{\nu_k} </math>
then the number of positive divisors of <math>n</math> is
: <math> d(n) = (\nu_1 + 1) (\nu_2 + 1) \cdots (\nu_k + 1), </math>
and each of the divisors has the form
: <math> p_1^{\mu_1} \, p_2^{\mu_2} \cdots p_k^{\mu_k} </math>
where <math> 0 \le \mu_i \le \nu_i </math> for each <math>1 \le i \le k.</math>

For every natural <math>n,</math> <math>d(n) < 2 \sqrt{n}.</math>

Also,{{sfn|ps=|Hardy|Wright|1960|p=264|loc=Theorem 320}}
: <math>d(1)+d(2)+ \cdots +d(n) = n \ln n + (2 \gamma -1) n + O(\sqrt{n}),</math>
where <math> \gamma </math> 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 <math>\ln n.</math> However, this is a result from the contributions of [[highly composite number|numbers with "abnormally many" divisors]].

== In abstract algebra ==
=== Ring theory ===
{{Main|Divisibility (ring theory)}}

=== Division lattice ===
{{Main|Division lattice}}
In definitions that allow the divisor to be 0, the relation of divisibility turns the set <math>\mathbb{N}</math> of [[non-negative]] integers into a [[partially ordered set]] that is a [[lattice (order)|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 [[duality (order theory)|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]] &ndash; A table of prime and non-prime divisors for 1–1000
* [[Table of prime factors]] &ndash; A table of prime factors for 1–1000
* [[Unitary divisor]]

== Notes ==
{{notelist}}

== Citations ==
{{reflist}}

== References ==
{{refbegin}}
* {{cite book
  | last = Durbin | first = John R.
  | year = 2009
  | title = Modern Algebra: An Introduction
  | edition = 6th
  | location=New York | publisher = Wiley
  | url=https://books.google.com/books?id=dnDJDwAAQBAJ
  | isbn=978-0470-38443-5
  }}
* {{citation
  | last1 = Guy | first1 = Richard K. | author1-link = Richard K. Guy
  | year = 2004
  | title = Unsolved Problems in Number Theory
  | edition = 3rd
  | publisher = [[Springer Verlag]]
  | isbn = 0-387-20860-7
  }}; section B
* {{cite book
  | last1 = Hardy | first1 = G. H. | authorlink1 = G. H. Hardy
  | last2 = Wright | first2 = E. M.
  | year = 1960
  | title = An Introduction to the Theory of Numbers
  | publisher = Oxford University Press
  | edition = 4th
  | location = 
  | url = https://archive.org/details/introductiontoth00hard
  | doi = 
  | id = 
  | isbn = 
  }}
* {{citation
  | last = Herstein | first = I. N.
  | year = 1986
  | title = Abstract Algebra
  | place = New York | publisher = Macmillan Publishing Company
  | isbn = 0-02-353820-1
  }}
* {{cite book
  | last1 = Niven | first1 = Ivan |author1-link=Ivan M. Niven
  | last2 = Zuckerman |first2 = Herbert S.
  | last3 = Montgomery | first3=Hugh L. |author3-link=Hugh Lowell Montgomery
  | title=An Introduction to the Theory of Numbers
  | year=1991 |publisher=[[John Wiley & Sons]]
  | edition=5th
  | isbn=0-471-62546-9
  }}
* [[Øystein Ore]], Number Theory and its History, McGraw–Hill, NY, 1944 (and Dover reprints).
* {{citation
  |first=Charles C. |last=Sims
  |title=Abstract Algebra: A Computational Approach
  |year=1984
  |publisher=John Wiley & Sons |place=New York
  |isbn=0-471-09846-9
  }}
* {{cite book
  | url = https://www.worldcat.org/oclc/56057904
  | last1 = Tanton | first1 = James
  | year = 2005
  | title = Encyclopedia of mathematics
  | publication-place = New York |publisher = Facts on File
  | isbn = 0-8160-5124-0
  | oclc = 56057904
  }}
{{refend}}

{{Divisor classes}}
{{Fractions and ratios}}

[[Category:Elementary number theory]]
[[Category:Division (mathematics)]]