Editing Divisor (section)

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