Английская Википедия:Divisor
Шаблон:Short description Шаблон:More footnotes Шаблон:About Шаблон:Redirect
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 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.
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Шаблон:Sfn
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Шаблон:Sfn
- With the convention that <math>m</math> be nonzero, <math>m \mid 0</math> for every nonzero integer <math>m.</math>Шаблон:SfnШаблон:Sfnp
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). 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 <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:
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>Шаблон:Efn 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 <math>\gcd(a, b) = 1,</math> then <math>a \mid c.</math>Шаблон:Efn 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 or an Шаблон:Vanchor of <math>n.</math> A number that does not evenly divide <math>n</math> but leaves a remainder is sometimes called an Шаблон:Vanchor 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> 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> (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 functions.
Шаблон:Anchor 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
- <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.
In abstract algebra
Ring theory
Division lattice
Шаблон:Main 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
Citations
References
- Шаблон:Cite book
- Шаблон:Citation; section B
- Шаблон:Cite book
- Шаблон:Citation
- Шаблон:Cite book
- Øystein Ore, Number Theory and its History, McGraw–Hill, NY, 1944 (and Dover reprints).
- Шаблон:Citation
- Шаблон:Cite book
Шаблон:Divisor classes Шаблон:Fractions and ratios
