Divisor

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, ${\displaystyle n}$ and ${\displaystyle -n}$ are known as the trivial divisors of ${\displaystyle n.}$ A divisor of ${\displaystyle n}$ that is not a trivial divisor is known as a non-trivial divisor (or strict divisor). 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

• 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;}$ that is, divisibility is a transitive relation.
• If ${\displaystyle a\mid b}$ and ${\displaystyle b\mid a,}$ then ${\displaystyle a=b}$ or ${\displaystyle a=-b.}$ (That is, ${\displaystyle a}$ and ${\displaystyle b}$ are associates.)
• If ${\displaystyle a\mid b}$ and ${\displaystyle a\mid c,}$ then ${\displaystyle a\mid (b+c)}$ holds, as does ${\displaystyle a\mid (b-c).}$ However, if ${\displaystyle a\mid b}$ and ${\displaystyle c\mid b,}$ then ${\displaystyle (a+c)\mid b}$ does not always hold (for example, ${\displaystyle 2\mid 6}$ and ${\displaystyle 3\mid 6}$ but 5 does not divide 6).
• ${\displaystyle a\mid b⟺ac\mid bc}$ for nonzero ${\displaystyle c}$. This follows immediately from writing ${\displaystyle ka=b⟺kac=bc}$.

If ${\displaystyle a\mid bc,}$ and ${\displaystyle gcd(a,b)=1,}$ then ${\displaystyle a\mid c.}$ 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}$ that is different from ${\displaystyle n}$ is called a proper divisor or an aliquot part of ${\displaystyle n}$ (for example, the proper divisors of 6 are 1, 2, and 3). 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}$, each 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)}$ (for example, ${\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\le {\mu }_i\le {\nu }_i}$ for each ${\displaystyle 1\le i\le k.}$

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

Also,

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

Division lattice

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