Divisors of an Integer

This note has been used to help create the Factors wiki

Definition

What is a divisor of a number NN? We say that mm is a divisor of NN, if there exists an integer kk such that N=km 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×m 0 = 0 \times m our definition above gives us that every integer is a divisor of 00.

Technique

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

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

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

Divisor Function

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

How many divisors does the number 2000 2000 have?

We have 2000=2453 2000 = 2^4 5^3. Hence, from the above discussion, it has (4+1)(3+1)=20 (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 2000?

Consider the product (1+2+22+23+24)(1+5+52+53) (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 2000. Hence the product represents the sum of all the divisors of the number 2000 2000, which is 31×156=4836 31\times 156 = 4836.

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

Application and Extensions

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

Since ϕ(N)=(q1+1)(q2+1)(qn+1) \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 qi q_i is even, which happens if and only if N N is a perfect square.

 

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

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

Note by Calvin Lin
5 years, 6 months ago

No vote yet
1 vote

  Easy Math Editor

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

  • Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
  • Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
  • Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.
  • Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

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×3 2 \times 3
2^{34} 234 2^{34}
a_{i-1} ai1 a_{i-1}
\frac{2}{3} 23 \frac{2}{3}
\sqrt{2} 2 \sqrt{2}
\sum_{i=1}^3 i=13 \sum_{i=1}^3
\sin \theta sinθ \sin \theta
\boxed{123} 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 - 3 years, 5 months ago

Log in to reply

A Number has exactly 13 divisors.What can we say about the number?

Bharathi Priya - 1 year, 8 months ago

Log in to reply

It is a perfect square

Antoine Geagea - 1 year, 5 months ago

Log in to reply

The Number 4096 has 13 posirive divisors exactly.4096 is a ecen composite number and it is also called an deficiency number.Because the sum of its proper divisors is 4095.Then 4096-4095 =1.The remainder is 1 so that it is a deficiency number

Bharathi Priya - 1 year, 5 months ago

Log in to reply

13 is a prime number. Its only divisor is itself. Therefore integer n has 13 divisors if and only if it is of the form p^(12).

The smallest such positive integer n is 2^12 = 4096.

Also, since 13 is a prime number > 2, it is odd, n has an odd number of divisors, and n must be a perfect square. p^12 = (p^6)^2.

Emily Falces - 1 year, 2 months ago

Log in to reply

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

Astro Enthusiast - 5 years, 3 months ago

Log in to reply

It is p13..OR..p121×p271.....14...implies..p141..OR....14=2×7...implies...p121×p271 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 - 5 years, 3 months ago

Log in to reply

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

Astro Enthusiast - 5 years, 3 months ago

Log in to reply

Thank you so much

Wesllen Brendo - 5 years, 3 months ago

Log in to reply

Brilliant sir

Rahul Kamble - 4 years, 4 months ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...