divisor

This is one of the fundamental concepts in number theory.

If a, b are integers then a is said to divide b, written a|b, iff there is an integer c such that b = ac. If a divides b then a is said to be a divisor of b, and b is said to be divisible by a.

Some basic results:

a|0 for all a
0|a iff a = 0
1|a for all a
a|b => a|bc for all c
a|b and a|c => a|(b+c)

Every number a is divisible by ±1 and ±a; these are called improper divisors of a. Any other divisor of a is called proper divisor of a. If a has no proper divisors then a is said to be prime.

There is a little nice theorem which allows us to find how many divisors a number has, if we know its Prime Factorization.

Consider an integer number, n.
Suppose n = (p₁)^a₁ * (p₂)^a₂ * ... * (p_k)^a_k
,where p₁...p_k are prime numbers, and a₁...a_k are the corresponding exponents.

Then, you can easily find out how many divisors n has (say S), with the following simple formula:

S = (a₁+1)*(a₂+1)*...*(a_k+1)

---

Proof

Suppose as above n = (p₁)^a₁ * (p₂)^a₂ * ... * (p_k)^a_k

The divisors of the number n then are those with prime factorizations with the same primes as n but with powers no bigger than the powers a_i. Each power can be chosen independently, so there are (a₁+1)(a₂+1)...(a_k+1) such divisors.

---

Let's see that through an example. Consider 24.
24 = 2³ * 3¹
So, with the above formula we take (3+1)*(1+1) = 8 divisors
Let's check this.
Divisors of 24: 1, 2, 3, 4, 6, 8, 12, 24
OK, they are 8.

Source: The Papyrous, Larousse, Britannica Encyclopedia

Di*vi"sor (?), n. [L., fr. dividere. See Divide.] Math.

The number by which the dividend is divided.

Common divisor. Math. See under Common, a.

 

© Webster 1913.