View source for Divisor

{{redirect|Divisible|divisibility of groups|Divisible group}}
{{about|an integer that divides another integer|}}
{{more footnotes|date=June 2015}}
[[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>. In this case, one also says that <math>n</math> is a '''multiple''' of <math>m.</math> An integer <math>n</math> is '''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==
If <math>m</math> and <math>n</math> are nonzero integers, and more generally, nonzero elements of an [[integral domain]], it is said that <math>m</math> '''divides''' <math>n</math>, <math>m</math> is a '''divisor''' of <math>n,</math> or <math>n</math> is a '''multiple''' of <math>m,</math> and this is written as
:<math>m \mid n,</math>
if there exists an integer <math>k</math>, or an element <math>k</math> of the integral domain, such that <math>mk = n</math>.<ref>for instance, {{harvnb|Sims|1984|loc=p. 42}} or {{harvnb|Durbin|1992|loc=p. 61}}</ref> 

This definition is sometimes extended to include zero.<ref>{{harvnb|Herstein|1986|loc=p. 26}}</ref> This does not add much to the theory, as 0 does not divide any other number, and every number divides 0. On the other hand, excluding zero from the definition simplifies many statements. Also, in [[ring theory]], an element {{mvar|a}} is called a "[[zero divisor]]" only if it is ''nonzero'' and {{math|1=''ab'' = 0}} for a ''nonzero'' element {{mvar|b}}. Thus, there are no zero divisors among the integers (and by definition no zero divisors in an integral domain).

==General==
Divisors can be [[negative number|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 odd numbers|even]], and integers not divisible by 2 are called [[even and odd numbers|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 <ref>[https://perso.crans.org/cauderlier/org/ITP17_draft.pdf FoCaLiZe and Dedukti to the Rescue for Proof Interoperability by  Raphael Cauderlier and Catherine Dubois]</ref>) . A non-zero 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==
There are some elementary rules:
* If <math>a \mid b</math> and <math>b \mid c</math>, then <math>a \mid c</math>, i.e. 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>.
* 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>.<ref><math>a \mid b,\, a \mid c \Rightarrow b=ja,\, c=ka \Rightarrow b+c=(j+k)a \Rightarrow a \mid (b+c)</math>. Similarly, <math>a \mid b,\, a \mid c \Rightarrow b=ja,\, c=ka \Rightarrow b-c=(j-k)a \Rightarrow a \mid (b-c)</math></ref> However, if <math>a \mid b</math> and <math>c \mid b</math>, then <math>(a + c) \mid b</math> does ''not'' always hold (e.g. <math>2\mid6</math> and <math>3 \mid 6</math> but 5 does not divide 6).

If <math>a \mid bc</math>, and [[greatest common divisor|gcd]]<math>(a, b) = 1</math>, then <math>a \mid c</math>. 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> which is different from <math>n</math> is called a '''proper divisor''' or an '''aliquot part''' of <math>n</math>. A number that does not evenly divide <math>n</math> but leaves a remainder is called an '''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 divisor]]s 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> (e.g. <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,<ref>
{{cite book
  | last1 = Hardy
  | first1 = G. H.
  | authorlink1 = G. H. Hardy
  | last2 = Wright
  | first2 = E. M.
  | title = An Introduction to the Theory of Numbers
  | publisher = Oxford University Press
  | date = April 17, 1980
  | location =
  | page = 264
  | url = https://archive.org/stream/AnIntroductionToTheTheoryOfNumbers-4thEd-G.h.HardyE.m.Wright#page/n279/mode/2up
  | doi =
  | id = 
  | isbn = 0-19-853171-0}}
</ref>
:<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 small and "abnormally large" divisors.

==In abstract algebra==
In definitions that include 0, the relation of divisibility turns the set <math>\mathbb{N}</math> of [[non-negative]] integers into a [[partially ordered set]]: 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]] [[integer|<math>\mathbb{Z}</math>]].

==See also==
* [[Arithmetic functions]]
* [[Divisibility rule]]
* [[Divisor function]]
* [[Euclid's algorithm]]
* [[Fraction (mathematics)]]
* [[Table of divisors]] &mdash; A table of prime and non-prime divisors for 1–1000
* [[Table of prime factors]] &mdash; A table of prime factors for 1–1000
* [[Unitary divisor]]

==Notes==
{{reflist}}

== References ==
*{{cite book |last=Durbin |first=John R. |title=Modern Algebra: An Introduction |edition=3rd |year=1992 |publisher=Wiley |location=New York |isbn=0-471-51001-7 |url=http://www.wiley.com/WileyCDA/WileyTitle/productCd-EHEP000258.html|ref=harv}}
*[[Richard K. Guy]], ''Unsolved Problems in Number Theory'' (3rd ed), [[Springer Verlag]], 2004 {{ISBN|0-387-20860-7}}; section B.
*{{citation |first=I. N. |last=Herstein |title=Abstract Algebra |year=1986 |publisher=Macmillan Publishing Company |place=New York |isbn=0-02-353820-1}}
*[[Ø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}}

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

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