Abstract Nonsense

Crushing one theorem at a time

Number Theory Problem

Problem: Define \sigma by

\displaystyle \sigma:\mathbb{N}\to\mathbb{N}:n\mapsto\sum_{d\mid n}d

Prove that if 2^{m}+1 is prime then \sigma(n)=2^{m}+1 has no solution for n\in\mathbb{N} except for \sigma(2)=3

Proof: We need a quick lemma.

Lemma: Suppose that n=ab where (a,b)=1, then \sigma(ab)=\sigma(a)\sigma(b)

Proof: Let \text{div}(a),\text{div}(b) denote the set of divisors of a and b respectively. For notational convenience let




Note then that if d\mid n then by the assumption that (a,b)=1 we have that d=a_pb_q for some a_q\in\text{div}(a) and some b_q\in\text{div}. But, not only is it true that if d\mid n that d=a_pb_q but in fact every number of that form also divides n. It follows that

\displaystyle \text{div}(n)=\bigcup_{p=1}^{j+1}\left\{a_p\cdot 1,\cdots,a_p\cdot b_k,a_p\cdot b_{k+1}\right\}

So that

\displaystyle \sigma(n)=\sum_{p=1}^{j+1}\left(a_p\cdot 1+\cdots+a_p\cdot b_{k+1}\right)=\left(1+\cdots+b_{k+1}\right)\sum_{p=1}^{j+1}a_p=\sigma(b)\sigma(a)

From where the conclusion follows. \blacksquare

Noting then that if n=p^{m} for some prime p we have that


So that

\displaystyle \sigma(n)=\sum_{j=0}^{m}p^j

We can combine this with the above lemma to conclude that if

n=p_1^{\alpha_1}\cdots p_m^{\alpha_m}


\displaystyle \sigma(n)=\prod_{k=1}^{m}\sum_{j=0}^{\alpha_k}p_k^j

So, getting to the actual problem. If m=1 then 2^m+1=3 and \sigma(2)=1+2=3. Thus, we may assume WLOG that m>1.

So, suppose that

\displaystyle 2^{m}+1=\sigma(n)

then by previous comment

\displaystyle 2^{m}+1=\prod_{k=1}^{m}\sum_{j=0}^{\alpha_k}p_k^j

But, since 2^{m}+1 is prime and the RHS of the above equation is a factorization of it it follows that

\displaystyle 2^{m}+1=\sum_{j=0}^{\alpha_{k_0}}p_k^j

for some k_0. But, expanding the RHS and subtracting one gives

2^{m}=p_{k_0}+\cdots+p_{k_0}^{\alpha_{k_0}}=p_{k_0}\left(1+\cdots+p_{k_0}^{\alpha_{k_0}-1}\right)\quad (1)

and thus p_{k_0}\mid 2^m and thus p_{k_0}=2^\ell for some \ell\in\mathbb{N}. But, remembering that p_{k_0} is prime it follows that p_{k_0}=2. Thus, dividing both sides of (1) by 2 gives

2^{m-1}=1+\cdots+2^{\alpha_{k_0}-1}\quad (2)

Now, since m>1 we see that 2^{m-1}>1 from where it follows that \alpha_{k_0}-1>0 and thus we see that the LHS of (2) is even whereas the RHS is odd, contradiction. The conclusion follows. \blacksquare


June 9, 2010 - Posted by | Fun Problems, Uncategorized

No comments yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s

%d bloggers like this: