6

I saw a hard competition problem with long and ugly proof in http://solmu.math.helsinki.fi/olympia/valmennus/2013/vt2013_12var.pdf ? The question is from Australian mathematical olympiad 1985. Is there a nice way to solve the following:

A positive integer $n$ has factors $1=d_1<d_2<\ldots < d_k=n$. Determine those $n$ that satisfies $n=d_6^2+d_7^2-1$.

Finnmath
  • 61

1 Answers1

4

From the equality $n = d_6^2 + d_7^2 - 1$, we see

  • $d_6$ and $d_7$ are mutually prime,
  • $d_7 \mid d_6^2 - 1 = (d_6 - 1)(d_6 + 1)$, and
  • $d_6 \mid d_7^2 - 1 = (d_7 - 1)(d_7 + 1)$.

Suppose $d_6 = ab$ and $d_7 = cd$ with $1 < a < b$ and $1 < c < d$.

Then $n$ has $6$ divisors smaller than $d_6$, namely $1$, $a$, $b$, $c$, $d$, $ac$. Hence one of $d_6$ and $d_7$ is either a prime $P$ or the square of a prime $p^2$. But $p$ is not $2$, therefore $d_7 = d_6 + 1$.

Write $d_6 = x$, $d_7 = x + 1$ to give$$n = x^2 + (x + 1)^2 - 1 = 2x(x + 1).$$

  1. Assume either $x$ or $x + 1$ is a prime $p$. So the other one has at most $6$ divisors and possible candidates are $2^3$, $2^4$, $2^5$, $2s$, $2s^2$, $4s$ where $s$ is an odd prime. $2^3$ and $2^4$ are not solutions. For $2^5$ we get the solution $x = 31$, $x + 1 = 32$, $n = 1984$. $2s$ is no solution because $n = 4ps$ has at most $4$ divisors less than $x$, namely $1$, $2$, $4$, $s$. $2s^2$ is no solution because $n = 4ps^2$ has $6$ divisors less than $x$, namely $1$, $2$, $4$, $s$, $2s$, $s^2$. $4s$ is no solution because $n = 8ps$ has $6$ divisors less than $x$, namely $1$, $2$, $4$, $8$, $s$, $2s$.
  2. Assume either $x$ or $x + 1$ is $p^2$. So the other one has at most $5$ divisors and possible candidates are $2^3$, $2^4$, $2s$ where $s$ is an odd prime. For $2^3$ we get the solution $x = 8$, $x + 1 = 9$, $n = 144$. $2^4$ is no solution. Also $2s$ is no solution because $n = 4p^2s$ has $6$ divisors less than $x$, namely $1$, $2$, $4$, $p$, $2p$, $s$.

Thus there are two solutions in all: $144$ and $1984$.

user345872
  • 466