Waste less time on Facebook — follow Brilliant.
×

Divisors of an Integer

This note has been used to help create the Factors wiki

Definition

What is a divisor of a number \(N\)? We say that \(m\) is a divisor of \(N\), if there exists an integer \(k\) such that \( N = km \).

In general, the divisors of a number refer to the positive divisors, unless otherwise noted. Since the negative divisors will be the negative of a positive divisor (and vice versa), we shall just consider positive divisors.

We also tend to ignore 0 the possibility for any of these numbers to be 0. Since \( 0 = 0 \times m \) our definition above gives us that every integer is a divisor of \(0\).

Technique

Let the integer \( N\) have a prime factorization \( p_1 ^{q_1} p_2^{q_2} \ldots p_n ^ {q_n}\), where \( p_1, p_2 \ldots , p_n\) are distinct prime numbers, and \( q_1, q_2 \ldots q_n\) are positive integers. Let \( d\) be a divisor of \( N\); then any prime factor \( p\) that divides \( d\) must divide \( N\), hence it must be one of \( p_1, p_2, \ldots , p_n\).

Without loss of generality, set \( p = p_i\). Let the highest power of \( p\) that divides \( d\) be \( p_i^{r_i}\). Then, \( p_i^{r_i}\) divides \( d\), which in turn divides \( N\), hence, \( p_i^{r_i}\) must divide \( p_i ^{q_i}\), which means that \( r_i \leq q_i\). Thus, by considering all the prime factors of \( d\), we get that it must have the form \( d = p_1^{r_1} p_2^{r_2} \ldots p_n^{r_n}\) where \( 0 \leq r_i \leq q_i\) for all \( i\).

Conversely, given a number \( d\) that has the form \( d = p_1^{r_1} p_2^{r_2} \ldots p_n^{r_n}\) where \( 0 \leq r_i \leq q_i\) for all \( i,\) it is clear that \( d\) is a divisor of \( N\). As such, we have a complete classification of all the divisors.

Divisor Function

How many divisors does the number \( N\) have? From the above classification, we can set up a direct bijection between \( d = p_1^{r_1} p_2^{r_2} \ldots p_n^{r_n}\) and sets of \( n\) integers \( ( r_1, r_2, \ldots r_n ) \) that satisfy \( 0 \leq r_i \leq q_i\). For each \( r_i\), there are \( q_i - 0 + 1 = q_i + 1\) possibilities. Hence, by the product rule, there are going to be \( (q_1 +1) (q_2 +1) \ldots (q_n + 1) \) divisors in all. The number of divisors of an integer \( N\) is often denoted as the \( \phi (N)\) or \( \sigma_0 (N)\).

How many divisors does the number \( 2000\) have?

We have \( 2000 = 2^4 5^3\). Hence, from the above discussion, it has \( (4+1)(3+1)=20\) divisors.

We can list them out as 1, 2, 4, 8, 16, 5, 10, 20, 40, 80, 25, 50, 100, 200, 400, 125, 250, 500, 1000, 2000.

(Can you see why we listed out the divisors this way, instead of in increasing order?)

 

What is the sum of all divisors of the number \( 2000\)?

Consider the product \( (1+2+2^2+2^3+2^4)(1+5+5^2+5^3)\) when expanded out. From the classification of the divisors, each divisor would appear exactly once as a term. Moreover, every term would be a divisor of the number \( 2000\). Hence the product represents the sum of all the divisors of the number \( 2000\), which is \( 31\times 156 = 4836\).

(Pop quiz: How would you generalize this to find the sum of all divisors of the number \( N\)? It is sometimes denoted as \( \sigma (N)\) or \( \sigma_1(N)\).)

Application and Extensions

Show that an integer \( N\) has an odd number of divisors if and only if it is a perfect square.

Since \( \phi(N) = (q_1 +1)(q_2+1) \ldots (q_n+1)\), this product is odd if and only if every term is odd, which happens if and only if every value \( q_i\) is even, which happens if and only if \( N\) is a perfect square.

 

What is the smallest integer \( N\) that has exactly 14 divisors?

Since \( 14 = 2 \cdot 7\), an integer has exactly 14 divisors if it has the form \( p^{13}\) or \( p_1 \cdot p_2 ^6\). The smallest number in the first case and second case are, \( 2^{13} = 8192\) and \( 3 \cdot 2^6 = 192\), respectively. Hence 192 is the smallest integer that has exactly 14 divisors.

Note by Calvin Lin
3 years ago

No vote yet
1 vote

Comments

Sort by:

Top Newest

As a fact, 0 divides 0, according to the definition, but the result is undefined, as every integer becomes 0 when multiplied by 0. Mateo Matijasevick · 10 months, 4 weeks ago

Log in to reply

Brilliant sir Rahul Kamble · 1 year, 9 months ago

Log in to reply

I don't understand the part of p1xp2^6. Huhu Astro Enthusiast · 2 years, 8 months ago

Log in to reply

@Astro Enthusiast It is \( p^{13}.. OR.. p_{1}^{2 - 1} \times p_{2}^{7 - 1} .....
14 ...implies.. p^{14 - 1}.. OR.... 14 = 2\times 7.. .implies... p_{1}^{2 - 1} \times p_{2}^{7 - 1} \)
14 are number of factors, including 1 and the number. Hope this might be useful. Niranjan Khanderia · 2 years, 8 months ago

Log in to reply

@Niranjan Khanderia Thank you so much Wesllen Brendo · 2 years, 8 months ago

Log in to reply

@Niranjan Khanderia Yes, it is. Thank you so much! :D Astro Enthusiast · 2 years, 8 months ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...