5
$\begingroup$

How can I solve the equation $p(n)^2=\sigma(n)+423$ for $1<n<2012$, where $p(n)$ is the product of distinct prime divisors of $n$ and $\sigma(n)$ is the sum of divisors of $n$.

I did this: $n=p_1^{a_1}\cdot p_2^{a_2}\cdots p_k^{a_k}$, then $p(n)=p_1\cdots p_k$ and $\sigma(n)=\frac{p_1^{a_1+1}-1}{p_1-1}\cdots \frac{p_k^{a_k+1}-1}{p_k-1}$. Then we have $$(p_1\cdots p_k)^2=\frac{p_1^{a_1+1}-1}{p_1-1}\cdots\frac{p_k^{a_k+1}-1}{p_k-1}+423.$$

But now I'm stuck :(. Help me please.

$\endgroup$
  • $\begingroup$ $\sigma(.)$ is the standard notation for the sum of divisors. $\endgroup$ – Xam Apr 3 '17 at 20:19
  • $\begingroup$ What is the source of this problem? $\endgroup$ – Ghartal Apr 17 '17 at 11:11
2
$\begingroup$

Short answer: A simple program can show that $n=1377$ is the only number less than $100000$ satisfying $p(n)^2=\sigma(n)+423$

Rigorous full answer:

Lemma 1: $n$ is odd number.

Suppose $n$ is even. Then we can observe that $p(n)^2-423=\sigma(n)$ is odd. Therefore, each $(p_i^{a_i+1}-1)/(p_i-1)=1+p_i+\cdots+p_i^{a_i}$ is odd. There are two possibilities to make this number odd: i) $p_i=2$, ii) $a_i$ is even. That is, $n=2^am^2$ for some positive integer $a$ and odd number $m$.

Now, suppose that there is an odd prime $p_j$ such that $a_j \ge 4$. Then, $$n+423<\sigma(n)+423=p(n)^2=\prod_{i=1}^k p_i^2\le\frac{2}{p_j^2}\prod_{i=1}^k p_i^{a_i}\le \frac{2n}{9}$$this is contradiction. Also, if exponent of $2$ is greater than $1$, then$$n+423<\sigma(n)+423=p(n)^2=\prod_{i=1}^k p_i^2\le\prod_{i=1}^k p_i^{a_i}=n$$and this is also contradiction. Therefore, $a_i=1$ if $p_i=2$, $a_i=2$ otherwise. It follows that $p(n)^2=2n$.

Also note that if $3|n$, then $2n=p(n)^2>\sigma(n)\ge n+n/2+n/3+n/6=2n$, which is a contradiction.

i) $k=1$: $n=2$, impossible.

ii) $k=2$: $n=2p^2$ for some odd prime $p$. But the equation $3(p^2+p+1)+423=4p^2$ has no integer root.

iii) $k \ge 3$: $n\ge2 \times 5^2 \times 7^2>2016$, so no solution.

Therefore, $n$ must be odd number.

Lemma 2: $k > 1$. That is, $n$ is not $1$, prime or prime power.

It is easy to see that $n$ is not $1$. Let $n=p^a$ for some prime $p$. Then,$$p^2=p(n)=\sigma(n)+423=1+\cdots+p^a+423$$and if $a\ge 2$, it is obvious that$$p^2<1+\cdots+p^a+423$$. Therefore $a=1$. But, then $p^2=1+p+423$ and one can check that the quadratic equation has no integer root.

Lemma 3: $k<3$.

Firstly, if $k \ge 5$, then $n \ge 3*5*7*11*13 \ge 2016$. Therefore $k \le 4$.

Recall that$$\frac{\sigma(n)}{n}=\prod_{i=1}^k \left(1+\frac{1}{p_i}+\cdots+\frac{1}{p_i^{a_i}}\right)<\prod_{i=1}^k \left(1+\frac{1}{p_i-1}\right)=\prod_{i=1}^k \left(\frac{p_i}{p_i-1}\right)$$ if $k\ge 3$, then by lemma 1, $p(n)^2\ge(3*5*7)^2>10000$ and $\sigma(n)+423<n*(3/2)*(5/4)*(7/6)*(11/10)+423<n*2.5+423<2012*2.5+423<10000$ therefore there is no $n$ satisfying the equation.

The solution to problem itself

By lemma 2 and 3, $k=2$. Let $n=p^aq^b$ where $p$ and $q$ are primes and $p<q$ without loss of generality. By lemma 1, both $p$ and $q$ are odd. By processing RHS, we get$$\sigma(n)+423<n\frac{p}{p-1}\frac{q}{q-1}+423<2012\frac{3}{2}\frac{5}{4}+423=4195.5$$and we get $pq=p(n)<\sqrt{4195.5}<65$. Therefore, there are limited number of possible $(p,q)$ pair: $(3,5), (3,7), (3,11), (3,13), (3,17), (3,19), (5,7), (5,11)$. Let's check all these cases one by one. Note that $\sigma(n)=p^2q^2-423$.

i) $(p,q)=(3,5)$: $\sigma(n)=-198$. No solution.

ii) $(p,q)=(3,7)$: $\sigma(n)=18$. $21\le n<\sigma(n)=18$. No solution.

iii) $(p,q)=(3,11)$: $\sigma(n)=666$. $666$ is multiple of $37$, therefore $37|(3^{a+1}-1)$ or $37|(11^{b+1}-1)$, and $3^a<666$, $11^b<666$. However, there exists no such $a$ or $b$ which satisfies these conditions.

iv) $(p,q)=(3,13)$: $\sigma(n)=1098$. $1098$ is multiple of $61$, therefore $61|(3^{a+1}-1)$ or $61|(13^{b+1}-1)$, and $3^a<1098$, $13^b<1098$. The only $a$ or $b$ satisfying the condition is $b=2$. But now we get $\sigma(3^a)=6$, which is impossible.

v) $(p,q)=(3,17)$: $\sigma(n)=2178$. $2178$ is multiple of $11^2$, but there is no $b$ such that $11|(17^{b+1}-1)$ and $17^b<2178$. On the other hand, the only $a$ satisfying $11|(3^{a+1}-1)$ and $3^a<2178$ is $a=4$. Now we get $\sigma(17^b)=18$, which gives $b=1$ and $n=1377$.

vi) $(p,q)=(3,19)$: $\sigma(n)=2826$. $2826$ is multiple of $157$, therefore $157|(3^{a+1}-1)$ or $157|(19^{b+1}-1)$, and $3^a<2826$, $19^b<2826$. However, there exists no such $a$ or $b$ which satisfies these conditions.

vii) $(p,q)=(5,7)$: $\sigma(n)=802$. $802$ is multiple of $401$, therefore $401|(5^{a+1}-1)$ or $401|(7^{b+1}-1)$, and $5^a<802$, $7^b<802$. However, there exists no such $a$ or $b$ which satisfies these conditions.

viii) $(p,q)=(5,11)$: $\sigma(n)=2602$. $2602$ is multiple of $1301$, therefore $1301|(5^{a+1}-1)$ or $1301|(11^{b+1}-1)$, and $5^a<2602$, $11^b<2602$. However, there exists no such $a$ or $b$ which satisfies these conditions.

Therefore, $n=1377$ is the only solution.

$\endgroup$
  • $\begingroup$ Thank you but I'm not allowed to use programs to solve the problem :( $\endgroup$ – Victor_Krull Apr 3 '17 at 19:46

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.