Something Simple for a Change

by t0rajir0u, Feb 11, 2007, 12:32 AM

I keep forgetting this is here, sorry. Anyway, I'll just be addressing a cute little topic today: the divisor function.

Definition: Given a positive integer $n$ , let $\sigma(n)$ denote the sum of the positive divisors of $n$ . For example, $\sigma(12) = 1+2+3+4+6+12 = 28$ . In sigma notation, this is

$\sigma(n) = \sum_{d | n}d$

Perfect numbers are numbers $n$ such that the sum of their proper divisors (not including $n$ ) is equal to $n$ . In other words:

Definition: A number $n$ is a perfect number if $\sigma(n) = 2n$ .

The first few perfect numbers are

$6 = 1+2+3 = 2 \cdot 3$
$28 = 1+2+4+7+14 = 4 \cdot 7$
$496 = 1+2+4+8+16+31+62+124+248 = 16 \cdot 31$

If $\sigma(n) > 2n$ then the number is said to be abundant, and if $\sigma(n) < 2n$ then $n$ is said to be deficient.

Now we prove a few interesting results.

Definition: Let $r(n) = \frac{ \sigma(n) }{n}$ . Then $n$ is perfect if $r(n) = 2$ , and so forth.

Lemma: $r(n) = \sum_{d | n}\frac{1}{d}$ . In other words, $r(n)$ is the sum of the reciprocals of the divisors of $n$ .

Proof: Given any divisor $d_{i}$ of $n$ , the quotient $\frac{n}{d_{i}}= d_{j}$ is an integer (definition of a divisor), so it must also be a divisor of $n$ . In other words, if you take the divisors $d_{i}$ of $n$ , sorted in increasing order, and divide them by $n$ , you get

$\frac{d_{1}+d_{2}+d_{3}+...+d_{k}}{n}= \frac{1}{d_{k}}+\frac{1}{d_{k-1}}+...+\frac{1}{d_{1}}$

When $n$ is a perfect number we have $r(n) = 2$ . Therefore:

- For $n = 6$ : We have $1+\frac{1}{2}+\frac{1}{3}+\frac{1}{6}= 2$ .

- For $n = 28$ : We have $1+\frac{1}{2}+\frac{1}{4}+\frac{1}{7}+\frac{1}{14}+\frac{1}{28}= 2$ .

- For $n = 496$ : We have $1+\frac{1}{2}+\frac{1}{4}+\frac{1}{8}+\frac{1}{16}+\frac{1}{31}+\frac{1}{62}+\frac{1}{124}+\frac{1}{248}+\frac{1}{496}= 2$ .

And so forth.

Using this result, you can show that if $n$ is a perfect or abundant number, then any multiple $kn$ of $n$ must be an abundant number (since it must have at least one more divisor than $n$ , so $r(kn) > r(n)$ ).

One more note: Notice that the perfect numbers given can all be written in the form $\frac{p(p+1)}{2}$ , where $p$ is a prime. Here, $p = 3, 7, 31$ .

Notice also that these primes are all one less than a power of $2$ : We have $3 = 2^{2}-1, 7 = 2^{3}-1, 31 = 2^{5}-1$ .

Finally, notice that the exponents of the powers of $2$ are themselves prime. Primes of this type are known as Mersenne primes. Euler proved that this construction generates all even perfect numbers, but we'll go with the weaker proof by Euclid that this construction generates some even perfect numbers. To do that, we need a nice way to calculate $\sigma(n)$ .

Lemma: Let $n = p_{1}^{e_{1}}p_{2}^{e_{2}}p_{3}^{e_{3}}...$ , where $p_{i}$ are the primes in the prime factorization of $n$ . Then

$\sigma(n) = (1+p_{1}+p_{1}^{2}+...+p_{1}^{e_{1}})(1+p_{2}+p_{2}^{2}+...+p_{2}^{e_{2}})...$

Proof: I won't go into detail here, but the general idea is that if you expand out the above product you get every possible combination of prime factorizations that could possibly divide $n$ . Incidentally, this provides a quick proof concerning the number of divisors of $n$ .

Back to perfect numbers. The conjecture here is that if $q$ is a prime such that $2^{q}-1$ is also a prime (a Mersenne prime), then $n = 2^{q-1}(2^{q}-1)$ is a perfect number. Well,

$\sigma(n) = (1+2+2^{2}+...+2^{q-1})(1+(2^{q}-1)) = (2^{q}-1)2^{q}= 2n$

Exactly as expected. QED.

Practice Problem 1: Show that if $2^{q}-1$ is prime then $q$ is prime. (One of the easier problems featured on this blog

)

Practice Problem 2: Show that the above construction produces all even perfect numbers.

Comment

2 Comments

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Whats with all the number theory. I look forward to your posts, only to have them be on topics I already know about! Teach me some combinatorics or something. (your blog is good)

by Pakman2012, Feb 11, 2007, 10:12 PM

Report

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

That is called "perfect number"....6,28,496 are perfect number~~

by FaBreGas-4, Mar 8, 2007, 12:45 AM

Report

Submit

orz $~~~~$
by clarkculus, Jan 10, 2025, 4:13 PM
Insanely auraful
by centslordm, Jan 1, 2025, 11:17 PM
Fly High
by Siddharthmaybe, Oct 22, 2024, 8:34 PM
Dang it he is gone ( /revive/revive/revive/revive/revive/revive/revive/revive/revive/revive/revive/revive/revive/revive/revive/revive/revive/revive/revive/revive/revive/revive/revive/revive/revive/revive/revive/revive/revive/revive/revive/revive/revive.
by 799786, Aug 4, 2022, 1:56 PM
annoying precision
by centslordm, May 16, 2021, 7:34 PM
rip t0rajir0u
by OlympusHero, Dec 5, 2020, 9:29 PM
Shoutbox bump xD
by DuoDuoling0, Oct 4, 2020, 2:25 AM
dang hes gone
by OlympusHero, Jul 28, 2020, 3:52 AM
First shout in July
by smartguy888, Jul 20, 2020, 3:08 PM
https://artofproblemsolving.com/community/c2448

has more.

-πφ
by piphi, Jun 12, 2020, 8:20 PM
wait hold up 310,000
people visited this man?!?!??
by srisainandan6, May 29, 2020, 5:16 PM
first shout in 2020
by OlympusHero, Apr 4, 2020, 1:15 AM
in his latest post he says he moved to wordpress
by MelonGirl, Nov 16, 2019, 2:43 AM
Please revive!
by AopsUser101, Oct 30, 2019, 7:10 PM
first shout in october fj9odiais
by bulbasaur., Oct 14, 2019, 1:14 AM
t0rajir0u is beast dude. I bet he'll make IMO this year
by #H34N1, Mar 26, 2008, 2:37 AM
"annoying precision" is somewhat of an understatement, don't you think?
by xscapezaer, Mar 23, 2008, 10:06 PM
Wow. Just by looking at the page--I gained IQ points. That's uncanny. Keep it up!
by The_Scintillator, Mar 21, 2008, 2:20 AM
Mmm t0r... Are you a senior? You're too genius Nice Blog btw... But for the sake of some less advanced people, go about defining some terms...
by resurrection, Jan 31, 2008, 1:08 AM
weird
by Airjohn6, Jan 30, 2008, 11:52 PM
pls help me with integrals i cant private message u b/c i just joined mathlinks, write me back at memena@loyno.edu
by memena, Jan 22, 2008, 2:18 AM
Can you post more problems about number theory? I'd like to suggest you about combinatorial problems!
by ghjk, Jan 10, 2008, 7:03 AM
The article: A Digression is nice
by FOURRIER, Nov 5, 2007, 4:47 PM
Interested in number theory? Mmm... I am bad in number theory but I need to take it. Hope that you can help me.
by ifai, Oct 13, 2007, 7:14 AM
your blog is very useful and i like it.
by lovejrz, Oct 12, 2007, 9:26 AM
madness
by madness, Oct 4, 2007, 4:48 PM
t0r, I recommend you watch out at the RSI-PROMYS frisbee game this weekend. You betrayed both MOP and PROMYS for RSI. I'm not going to be there, but let's just say there's a hitman after you.
by K81o7, Jul 27, 2007, 3:27 AM
hello.
by ajai, Jul 13, 2007, 12:52 AM
just drop by to say hello! and digging for stuffs that I could understand
by jeez123, Jun 30, 2007, 5:02 PM

128 shouts

Annoying precision

Something Simple for a Change

by t0rajir0u, Feb 11, 2007, 12:32 AM

2 Comments