1
$\begingroup$

I've seen this posted but I haven't seen this in depth as i need it. I turned this in as homework but only got 1 out of 3 on it, so any clarification would be wonderful.

Show that if the sum of all divisors of n is a prime, say p, then the number of divisors of n is also a prime.

So we know n=$p_1^{a_1}p_2^{a_2}...p_k^{a_k}$ and we have our divisor function $\sigma$(n) = $\sigma(p_1^{a_1}p_2^{a_2}...p_k^{a_k})$ = $\sigma(p_1^{a_1})\sigma(p_2^{a_2})...\sigma(p_k^{a_k})$, since $\sigma$ is a multiplicative function.
But, $\sigma(n)$ is a prime, say p. So at most, $\sigma(n)$ = $\sigma(p^a)$ = q, where q is also a prime, since $\sigma(p_1^{a_1})\sigma(p_2^{a_2})...\sigma(p_k^{a_k})$ is a composite number.
Therefore, $\sigma(p^a)$ = $\frac{p^{a+1}-1}{p-1}$ = $\frac{(p^{a}+p^{a-1}+...+p+1)(p-1)}{p-1}$ = $p^{a}+p^{a-1}+...+p+1$ = q.
let $f(p)$=$p^{a}+p^{a-1}+...+p+1$.

Cases: If $deg(f(p))$ is odd then our cyclotomic polynomial $f(p)$ has an even number of terms and can be factored which implies it is composite. Thus it is a necessary codition for $a$ to be even.
If it is such that $a+1$ is a composite number, we can still factor $f(p)$. (i think this is where my error is because I have to validate this statement and I can't think of how to show this is the case...).
Thus, the only way for $f(p)$ to be irreducible is for $a+1$ to be prime. (again, what is my proof here?)

This implies $d(n) = d(p^a) = a+1$, which is a prime and where $d(n)$ is the divisor function.

$\endgroup$
2
  • $\begingroup$ My professor underlined the statement that if a is odd, then you can factor f(p) which implies it is composite. He wrote with red pen, WHY! I thought that was enough...since it's cyclotomic you can factor out (p+1). I didn't write that, so maybe he was just being a stickler. $\endgroup$
    – Eleven-Eleven
    Mar 31, 2013 at 4:06
  • $\begingroup$ Also, some very similar ideas are used in proving euclids result on even perfect numbers. $\endgroup$
    – Ethan Splaver
    Mar 31, 2013 at 4:11

2 Answers 2

Reset to default
2
$\begingroup$

This proof looks fine to me, the case when $a+1$ is composite does indeed lead to $\frac{(p^{a+1}-1)}{(p-1)}$ being composite, because if $a+1=rt$, then we would have $$\frac{(p^{rt}-1)}{(p-1)}=\frac{((p^{r})^t-1)}{(p-1)}=\frac{(p^r-1)}{(p-1)}(1+p^r+p^{2r}...p^{r(t-1) })$$ Which is clearly composite sense $p-1$ divides $p^r-1$

$\endgroup$
8
  • $\begingroup$ so he most likely gave me points off for lack of rigor. Since I didn't prove the cases of a+1 being an even number and an odd composite number. Now if it's an odd composite number, then $a+1$=$mn$ where both $m$ and $n$ are odd so $p^{mn}-1$ = $((p^m)^n))-1$ = $(p^m-1)(g(p))$.....etc... $\endgroup$
    – Eleven-Eleven
    Mar 31, 2013 at 4:19
  • $\begingroup$ Can you show why f(p) is irreducible if $a+1$ is prime? That is the last step here which I'm missing... $\endgroup$
    – Eleven-Eleven
    Mar 31, 2013 at 4:27
  • $\begingroup$ @ChristopherErnst If $f(x)=\frac{x^p-1}{x-1}$, we can substitute $x+1$ for $x$, so that $f(x+1)=\frac{(x+1)^p-1}{x}$, we also have that $\frac{(x+1)^p-1}{x}\equiv 1 \text{ mod p}$ by fermats lttle theorem, so that all the coeifients except the leading one are divisible by p, now if we look at the case when $x=1$, we see it is divisible by p. From here we can see it satisfies Eisensteins criterion. This shows its irreducible over the rationals and also the integers. $\endgroup$
    – Ethan Splaver
    Mar 31, 2013 at 4:35
  • $\begingroup$ @Ethan....ahhh, I haven't looked in my Abstract text in a while and forgot all about Eisenstein.... $\endgroup$
    – Eleven-Eleven
    Mar 31, 2013 at 4:44
  • $\begingroup$ @Christopher: Please be aware there is a difference between polynomials being irreducible and values they take being prime. (In general, both primes and composites can be in the range of a polynomial, be it reducible or irreducible. Though a reducible polynomial may only achieve finitely many prime values.) You want to show «$\sigma(p^a)$ prime implies $a+1$ prime» by showing the contrapositive «$a+1$ composite implies $\sigma(p^a)$ composite». You do not need to show the converse, «$a+1$ prime implies $\sigma(p^a)$ prime» (which is false: take $a=1$ and any odd $p$). $\endgroup$
    – anon
    Mar 31, 2013 at 4:47
1
$\begingroup$

If I were grading your homework I would challenge two things.

Firstly, your explanation for $\deg f$ being odd is unclear. If you spelled out that you can factor $p+1$ clearly, that's fine; but the way you put it ($f$ having even number of terms thus can be factored?) is unclear.

Secondly, the point is not whether $\deg f$ is odd or not, it's whether $\deg f + 1$ is composite or not. You seem to notice this point, but failing to supply a proof for $\deg f + 1$ being composite means that you are quite far from giving a complete solution of the problem.

$\endgroup$
1
  • $\begingroup$ I can see where a professor would red pen me because of that... $\endgroup$
    – Eleven-Eleven
    Mar 31, 2013 at 4:48

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .