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, 8 months ago

No vote yet
1 vote

  Easy Math Editor

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list

  • bulleted
  • list

1. numbered
2. list

  1. numbered
  2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1

paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
    # 4 spaces, and now they show
    # up as a code block.

    print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in \( ... \) or \[ ... \] to ensure proper formatting.
2 \times 3 \( 2 \times 3 \)
2^{34} \( 2^{34} \)
a_{i-1} \( a_{i-1} \)
\frac{2}{3} \( \frac{2}{3} \)
\sqrt{2} \( \sqrt{2} \)
\sum_{i=1}^3 \( \sum_{i=1}^3 \)
\sin \theta \( \sin \theta \)
\boxed{123} \( \boxed{123} \)

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 - 1 year, 7 months ago

Log in to reply

Brilliant sir

Rahul Kamble - 2 years, 6 months ago

Log in to reply

I don't understand the part of p1xp2^6. Huhu

Astro Enthusiast - 3 years, 5 months ago

Log in to reply

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 - 3 years, 5 months ago

Log in to reply

Thank you so much

Wesllen Brendo - 3 years, 5 months ago

Log in to reply

Yes, it is. Thank you so much! :D

Astro Enthusiast - 3 years, 5 months ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...