Competition problem — Number theory

Library / /2 of 17

Number theory Difficulty 5.1 AIME, harder Prove it 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?

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.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.