Divisor
|
|
- For divisors in algebraic geometry, see divisor (algebraic geometry).
In mathematics, a divisor of an integer n, also called a factor of n, is an integer which evenly divides n without leaving a remainder. For example, 7 is a divisor of 42 because 42/7 = 6. We also say 42 is divisible by 7 or 42 is a multiple of 7 or 7 divides 42 and we usually write 7 | 42. Divisors can be positive or negative. The positive divisors of 42 are {1, 2, 3, 6, 7, 14, 21, 42}.
Some special cases: 1 and -1 are divisors of every integer, and every integer is a divisor of 0. Numbers divisible by 2 are called even and those that are not are called odd.
The name comes from the arithmetic operation of division: if a/b=c then a is the dividend, b the divisor, and c the quotient.
| Contents |
Rules for small divisors
There are some rules which allow to recognize small divisors of a number from the number's decimal digits:
A divisibility rule is a rule you can use to determine a number's divisibility by another number. In decimal, the divisibility rules are:
- a number is divisible by 2 iff the last digit is divisible by 2
- a number is divisible by 3 iff the sum of its digits is divisible by 3
- a number is divisible by 4 iff the number given by the last two digits is divisible by 4
- a number is divisible by 5 iff the last digit is 0 or 5
- a number is divisible by 6 iff it is divisible by 2 and by 3
- a number is divisible by 7 iff the result of subtracting twice the last digit from the number with the last digit removed is divisible by 7 (e.g. 364 is divisible by 7 since 36-2×4 = 28 is divisible by 7). If the number is too big, you can divide it in groups of three digits from right to left, putting alternating signs before each group (for example, instead of 1,048,576 you can test 576-048+1 = 529, which isn't divisible by seven since 52-18 = 34 is not)
- a number is divisible by 8 iff the number given by the last three digits is divisible by 8
- a number is divisible by 9 iff the sum of its digits is divisible by 9
- a number is divisible by 10 iff the last digit is 0
- a number is divisible by 11 iff the alternating sum of its digits is divisible by 11 (e.g. 182919 is divisible by 11 since 1-8+2-9+1-9 = -22 is divisible by 11)
- a number is divisible by 12 iff it's divisible by 3 and by 4
- A number is divisible by 13 iff the result of subtracting 9 times the last digit from the number with the last digit removed is divisible by 13 (e.g. 858 is divisible by 13 since 85-9×8 = 13 is divisible by 13). The method of dividing a big number into groups of three digits, explained for divisibility by 7, works for 13, too
- A number is divisible by 14 iff it's divisible by 2 and by 7
- A number is divisible by 15 iff it's divisible by 3 and by 5
Further notions and facts
Some elementary rules:
- If a | b and a | c, then a | (b + c), in fact, a | (b m + c n) for all integers m, n.
- If a | b and b | c, then a | c. (transitive relation)
- If a | b and b | a, then a = b or a = -b.
The following property is important:
- If a | b c, and gcd(a,b) = 1, then a | c. (Euclid's lemma)
A positive divisor of n which is different from n is called a proper divisor (or aliquot part) of n. (A number which does not evenly divide n, but leaves a remainder, is called an aliquant part of n.)
An integer n > 1 whose only proper divisor is 1 is called a prime number.
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.
If a number equals the sum of its proper divisors, it is said to be a perfect number. Numbers less than that sum are said to be deficient, while numbers greater than that sum are said to be abundant.
The total number of positive divisors of n is a multiplicative function d(n) (e.g. d(42) = 8 = 2×2×2 = d(2)×d(3)×d(7)). The sum of the positive divisors of n is another multiplicative function σ(n) (e.g. σ(42) = 96 = 3×4×8 = σ(2)×σ(3)×σ(7)).
If the prime factorization of n is given by
- <math> n = p_1^{\nu_1} \, p_2^{\nu_2} \, ... \, p_n^{\nu_n} <math>
then the number of positive divisors of n is
- <math> d(n) = (\nu_1 + 1) (\nu_2 + 1) ... (\nu_n + 1), <math>
and each of the divisors has the form
- <math> p_1^{\mu_1} \, p_2^{\mu_2} \, ... \, p_n^{\mu_n} <math>
where
- <math> \forall i : 0 \le \mu_i \le \nu_i. <math>
The relation | of divisibility turns the set N of non-negative integers into a partially ordered set, in fact into a complete distributive lattice. The largest element of this lattice is 0 and the smallest one is 1. The meet operation ^ is given by the greatest common divisor and the join operation v by the least common multiple. This lattice is isomorphic to the dual of the lattice of subgroups of the infinite cyclic group Z.
If an integer n is written in base b, and d is an integer with b ≡ 1 (mod d), then n is divisible by d if and only if the sum of its digits is divisible by d. The rules for d=3 and d=9 given above are special cases of this result (b=10).
We can generalize this method even further to find how to check divisibility of any integer in any base by any other (smaller integer). Let us say that we want to determine if d | a in base b. Then we first find a pair of integers (n, k) that solves the congruence bn ≡ k (mod d). Now rather than summing the digits, we take a (which has m digits) and multiply the first m-n digits by k and add the product to the last (or more precisely, smallest) k digits and repeat if necessary. If the result is a multiple of d then the original number is divisible by d. A few examples will help demonstrate this. Since 103 ≡ 1 (mod 37) then the number 1523836638 gives 1+523+836+638 = 1998 which gives 999 which we know is divisible by 37 due to the above congruence. Again, 102 ≡ 2 (mod 7) so 43106 gives 431×2 + 06 = 868 which gives 8×2+68 = 84 which is easily noted as being a multiple of 7. Note that there is no unique triple (n, k, d) since for example 10 ≡ 3 (mod 7) so we could also have done 4310×3 + 6 = 12936 and 1293×3 + 6 = 3885 and 388×3 + 5 = 1169 and 116×3 + 9 = 357 and 35×3 + 7 = 112 and 11×3 + 2 = 35 and 3×3 + 5 = 14 and 1×3 + 4 = 7. Clearly this is not always efficient but note that each number in this series, 43106, 12936, 3885, 1169, 357, 112, 35, 14, 7 is a multiple of 7 and many series could contain trivially identifiable multiples. This method is not necessarily useful for some numbers (for example 104 ≡ 4 (mod 17) is the first n where k < 10) but lends itself to fast calculations in other cases where n and k are relatively small.
Generalization
One can talk about the concept of divisibility in any integral domain. Please see that article for the definitions in that setting.
See also
- Table of prime factors — A table of prime factors for 1-1000
- Table of divisors — A table of prime and non-prime divisors for 1-1000
- Euler's totient function
External links
- Divisibility Criteria (http://www.cut-the-knot.org/blue/divisibility.shtml)
- Divisibility by 9 and 11 (http://www.cut-the-knot.org/Generalization/div11.shtml)
- Divisibility by 7 (http://www.cut-the-knot.org/Generalization/div11.shtml#div7)
- Divisibility by 81 (http://www.cut-the-knot.org/Generalization/81.shtml)
- Factoring Calculator (http://www.farfarfar.com/math/calculators/factoring/) -- Factoring calculator that displays the prime factors and the prime and non-prime divisors of a given number.cs:Dělitelnost
da:Divisor de:Teilbarkeit es:Factor propio fr:Facteur (mathmatiques) it:Divisore ja:約数 nl:Deelbaar pl:Dzielnik pt:Divisor sl:delitelj ru:Делимость zh:因數