{{Short description|Integer that divides another integer}} {{about|divisibility of integers|the second operand of a division|division (mathematics)|divisibility in rings|Divisibility (ring theory)|other uses|}} {{redirect|Divisible|divisibility of groups|Divisible group}} {{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>{{sfn|ps=|Tanton|2005|p=185}} In this case, one also says that <math>n</math> is a ''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.
The concept of a divisor is extended, with the same definition, to elements of any ring; see Divisibility (ring theory).
== 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 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, <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 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 == [[File:Highly composite numbers.svg|thumb|250px|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 <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 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, <math>A=\{1,2,3,4,5,6,10,12,15,20,30,60\},</math> partially ordered by divisibility, has the Hasse diagram:
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 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 divisors of <math>n</math>, each raised to some power. This is a consequence of the fundamental theorem of arithmetic.
A number <math>n</math> 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 <math>n,</math> and 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 functions.
{{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 numbers with "abnormally many" divisors.
== 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 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
== 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 | 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)