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$
  • $\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 '13 at 4:06
  • $\begingroup$ Also, some very similar ideas are used in proving euclids result on even perfect numbers. $\endgroup$ – Ethan Mar 31 '13 at 4:11
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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I can see where a professor would red pen me because of that... $\endgroup$ – Eleven-Eleven Mar 31 '13 at 4:48
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$

| cite | improve this answer | |
$\endgroup$
  • $\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 '13 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 '13 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 Mar 31 '13 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 '13 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 '13 at 4:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.