Track / Stage 5 / 91 of 400 #1171 of 2444

Problem 1171

AIME late

Number theory Difficulty 5.1 Prove it Croatian Mathematical Society Competitions · Croatia

A quadruple $(a, b, c, d)$ of positive integers is called green if
$b = a^2 + 1, \quad c = b^2 + 1, \quad d = c^2 + 1$
holds, and $D(a) + D(b) + D(c) + D(d)$ is odd, where $D(k)$ denotes the number of positive divisors of $k$ .
How many green quadruples having elements less than 1\ 000\ 000 are there?

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Official solution

Note that $D(k)$ is odd if and only if $k$ is a perfect square.
From $m^2 < m^2 + 1 < m^2 + 2m + 1 = (m+1)^2$ it follows that $m^2 + 1$ is not a perfect square for any positive integer $m$ . Hence $b, c$ and $d$ of any green quadruple are not perfect squares, i.e. $D(b), D(c)$ and $D(d)$ are even.
Therefore, $D(a)$ must be odd and $a$ is a perfect square.
Since $10^6 > d > c^2 > b^4 > a^8$ , i.e. $2^{10} = 1024 > 10^3 > a^4$ , we get $6^2 > 2^5 > a^2$ , i.e. $a < 6$ . Hence $a = 1$ or $a = 4$ .
A direct computation confirms that both options yield green quadruples: $(1, 2, 5, 26)$ and $(4, 17, 290, 84101)$ . Therefore, the answer is 2.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty, ordering) added by this project.