3
$\begingroup$

I recently encountered the following problem:

A natural number $n$ is called correct if and only if the sum of the squares of $n$'s divisors equals $(n+3)^2$. Prove that no numbers of the form $n=p^m$, where $p$ is a prime and $m\in\Bbb{N}$ (prime powers) can be correct. (from the N. N. Mihaileanu Mathematics Contest – 8th Grade 2017, Romania)

First of all, I looked at the sum of the divisor squares:

$$S=\sum_{d\in D_{p^m}^+}d^2$$

Where $D_{p^m}^+$ is the set of $p^m$'s positive divisors. However, since $p^m$ is a prime power, this set can also be expressed as:

$$D_{p^m}^+=\{0\le k\le m\mid p^k\}$$

So it follows that our sum can simply be expressed as:

$$S=\sum_{k=0}^m (p^k)^2=\sum_{k=0}^m p^{2k}$$

Now, I tried to continue on with the proof using Reductio ad absurdum, by assuming that $S$ can equal $(n+3)^2$:

$$\sum_{k=0}^m p^{2k}=(p^m+3)^2$$

Subtracting $p^{2m}$ from both sides,

$$\sum_{k=0}^{m-1} p^{2k}=6p^m+9$$

Then, I tried evaluating the sum of that series, obtaining:

$$6p^m+9=\frac{p^{2m}-1}{p^2-1}$$


However, I am stuck here. I tried my best to avoid splitting in cases, but am currently unable to finish my proof. Any hints on what I should do next (preferably, without having to consider cases separately, but that works too)?

$\endgroup$
  • 1
    $\begingroup$ Why avoid modular arithmetic? $\endgroup$ – Kenny Lau May 22 '18 at 10:39
  • $\begingroup$ @KennyLau Mainly because I'd have to consider $2$ separately, at least $\mod p$. I realised I don't want to avoid MA, but rather taking things separately. I am fine with that if it's really needed, but I prefer not to deal with it :) $\endgroup$ – Mr. Xcoder May 22 '18 at 10:43
  • $\begingroup$ From that sum you get $6p^m-6p^m+9p^2-2p^2m=8$ so $modp$ this means $8=0modp$ which implies $p=2$. So you only need to examine that case. $\endgroup$ – Μάρκος Καραμέρης May 22 '18 at 11:10
4
$\begingroup$

Letting $x=p^m$, the key equation becomes $6x+9=(x^2-1)/(p^2-1)$, or

$$x^2-6(p^2-1)x-(9p^2-8)=0$$

for which the quadratic formula tells us

$$x=3(p^2-1)\pm\sqrt{9(p^2-1)^2+(9p^2-8)}=3(p^2-1)\pm\sqrt{9p^4-9p^2+1}$$

This implies the discriminant is a perfect square, which implies

$$36p^4-36p^2+4=(6p^2-3)^2-5$$

is a square. But the only two squares that differ by $5$ are $9$ and $4$, and

$$6p^2-3=3\implies p=\pm1$$

$\endgroup$
  • $\begingroup$ Absolutely beautiful argument, only using the quadratic formula and some clever tricks. Awesome! $\endgroup$ – Mr. Xcoder May 22 '18 at 12:37
  • 1
    $\begingroup$ This is arguably the best answer, imho. Unfortunately I have reached my daily voting limit, but if I didn't, $(+1)$ $\endgroup$ – Mr Pie May 25 '18 at 9:54
1
$\begingroup$

I think the simplest proof is a $\mod p$ argument (as suggested in one of the comments to the original question):

If $n=p^m$ then all of the divisors of $n$ apart from 1 are multiples of $p$, so

$\sum_{d|n} d^2 \equiv 1 \mod p$

and $(n+3)^2 = (p^m+3)^2 \equiv 9 \mod p$

If $1 \equiv 9 \mod p$ then $p=2$ and $p^m \in \{2,4,8,16\}$ - after 16, $\sum d^2 > (2^m+3)^2$. But we can eliminate $\{2,4,8,16\}$ by direct calculation. So

$\sum_{d|n} d^2 \ne (n+3)^2 \quad \forall n=p^m$

$\endgroup$
  • $\begingroup$ Why $p^m\in\{2,4,8\}$? $\endgroup$ – Mr. Xcoder May 22 '18 at 12:26
  • $\begingroup$ Should be $\{2,4,8,16\}$ - I have corrected my answer. $\endgroup$ – gandalf61 May 22 '18 at 13:17
1
$\begingroup$

I'll continue the argument from $$\sum_{k=0}^{m-1} p^{2k}=6p^m+9\tag{1}\label{eq1}$$

Firstly, assume $m=1$ or $m=2$. Then $\eqref{eq1}$ becomes $1=6p+9$ or $1+p^2=6p^2+9$, which is impossible. Thus $m\ge3$.

i) $p=2$. Then since $2^{2(m-1)}<6\times2^m+9<8\times2^m=2^{m+3}$, $m<5$. Manually checking the cases $m=3$ and $m=4$ gives no solutions.

ii) $p=3$, then $3^{2(m-1)}<6\times3^m+9<9\times3^m=3^{m+2}$, $m<4$. Manually checking the case $m=3$ gives no solution.

iii) $p=5$, then $5^{2(m-1)}<6\times5^m+9<25\times5^m=5^{m+2}$, $m<4$. Manually checking the case $m=3$ gives no solution.

iv) $p\ge7$, then $p^{2(m-1)}<6p^m+9<7p^m\le p^{m+1}$, $m<3$.

By i) to iv), we can conclude that no primes can be correct number.

Also, one can replace the arguments of ii) and iii) to modular arithmetic.

$\endgroup$

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.