Divisor

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\backslash 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\backslash not\backslash mid\; n.${{sfn|ps=|Hardy|Wright|1960|p=1}}{{sfn|ps=|Niven|Zuckerman|Montgomery|1991|p=4}}

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

• With the convention without an additional constraint on $m,$ $m\; \backslash mid\; 0$ for every integer $m.${{sfn|ps=|Hardy|Wright|1960|p=1}}{{sfn|ps=|Niven|Zuckerman|Montgomery|1991|p=4}}
• With the convention that $m$ be nonzero, $m\; \backslash mid\; 0$ for every nonzero integer $m.${{sfn|ps=|Sims|1984|p=42}}{{sfnp|ps=|Durbin|2009|p=57|loc=Chapter III Section 10}}

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 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.

File:Highly composite numbers.svgs have exactly 2 divisors, and highly composite numbers are in bold.]]

• 7 is a divisor of 42 because $7\backslash times\; 6=42,$ so we can say $7\backslash 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=\backslash \{1,2,3,4,5,6,10,12,15,20,30,60\backslash \},$ partially ordered by divisibility, has the Hasse diagram:

File:Lattice of the divisibility of 60; factors.svg

There are some elementary rules:

• If $a\; \backslash mid\; b$ and $b\; \backslash mid\; c,$ then $a\; \backslash mid\; c;$ that is, divisibility is a transitive relation.
• If $a\; \backslash mid\; b$ and $b\; \backslash mid\; a,$ then $a\; =\; b$ or $a\; =\; -b.$ (That is, $a$ and $b$ are associates.)
• If $a\; \backslash mid\; b$ and $a\; \backslash mid\; c,$ then $a\; \backslash mid\; (b\; +\; c)$ holds, as does $a\; \backslash mid\; (b\; -\; c).${{efn|$a\; \backslash mid\; b,\backslash ,\; a\; \backslash mid\; c$ $\backslash Rightarrow\; \backslash exists\; j\backslash colon\; ja=b,\backslash ,\; \backslash exists\; k\backslash colon\; ka=c$ $\backslash Rightarrow\; \backslash exists\; j,k\backslash colon\; (j+k)a=b+c$ $\backslash Rightarrow\; a\; \backslash mid\; (b+c).$ Similarly, $a\; \backslash mid\; b,\backslash ,\; a\; \backslash mid\; c$ $\backslash Rightarrow\; \backslash exists\; j\backslash colon\; ja=b,\backslash ,\; \backslash exists\; k\backslash colon\; ka=c$ $\backslash Rightarrow\; \backslash exists\; j,k\backslash colon\; (j-k)a=b-c$ $\backslash Rightarrow\; a\; \backslash mid\; (b-c).$}} However, if $a\; \backslash mid\; b$ and $c\; \backslash mid\; b,$ then $(a\; +\; c)\; \backslash mid\; b$ does not always hold (for example, $2\backslash mid6$ and $3\; \backslash mid\; 6$ but 5 does not divide 6).
• $a\; \backslash mid\; b\; \backslash iff\; ac\; \backslash mid\; bc$ for nonzero $c$. This follows immediately from writing $ka\; =\; b\; \backslash iff\; kac\; =\; bc$.

If $a\; \backslash mid\; bc,$ and $\backslash gcd(a,\; b)\; =\; 1,$ then $a\; \backslash mid\; c.${{efn|$\backslash gcd$ refers to the greatest common divisor.}} This is called Euclid's lemma.

If $p$ is a prime number and $p\; \backslash mid\; ab$ then $p\; \backslash mid\; a$ or $p\; \backslash mid\; b.$

A positive divisor of $n$ that is different from $n$ is called a {{vanchor|proper divisor}} or an {{vanchor|aliquot part}} 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 {{vanchor|aliquant part}} 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)\backslash times\; d(n).$ For instance, $d(42)\; =\; 8\; =\; 2\; \backslash times\; 2\; \backslash times\; 2\; =\; d(2)\; \backslash times\; d(3)\; \backslash 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)\backslash times\; d(n).$ The sum of the positive divisors of $n$ is another multiplicative function $\backslash sigma\; (n)$ (for example, $\backslash sigma\; (42)\; =\; 96\; =\; 3\; \backslash times\; 4\; \backslash times\; 8\; =\; \backslash sigma\; (2)\; \backslash times\; \backslash sigma\; (3)\; \backslash times\; \backslash sigma\; (7)\; =\; 1+2+3+6+7+14+21+42$). Both of these functions are examples of divisor functions.

{{anchor|number_of_divisors_formula}}If the prime factorization of $n$ is given by

: $n\; =\; p\_1^\{\backslash nu\_1\}\; \backslash ,\; p\_2^\{\backslash nu\_2\}\; \backslash cdots\; p\_k^\{\backslash nu\_k\}$

then the number of positive divisors of $n$ is

: $d(n)\; =\; (\backslash nu\_1\; +\; 1)\; (\backslash nu\_2\; +\; 1)\; \backslash cdots\; (\backslash nu\_k\; +\; 1),$

and each of the divisors has the form

: $p\_1^\{\backslash mu\_1\}\; \backslash ,\; p\_2^\{\backslash mu\_2\}\; \backslash cdots\; p\_k^\{\backslash mu\_k\}$

where $0\; \backslash le\; \backslash mu\_i\; \backslash le\; \backslash nu\_i$ for each $1\; \backslash le\; i\; \backslash le\; k.$

For every natural $n,$

Also,{{sfn|ps=|Hardy|Wright|1960|p=264|loc=Theorem 320}}

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

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

{{Main|Divisibility (ring theory)}}

{{Main|Division lattice}}

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

• 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

{{notelist}}

{{reflist}}

{{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)