Problem 1713

1. Lemma 1: Given any non-zero integer $a$, there exists a prime number $p$ and an integer $m$ such that $p^{2m} + a$ has a prime divisor $q$ such that $v_q(p^{2m} + a)$ is odd.

Proof:
- If $a$ is even and $3 \nmid a$, take $p = 3$ and $m$ sufficiently large so that $3^{2m} + a$ is not a perfect square. Since $3 \nmid 3^{2m} + a$ and $2 \nmid 3^{2m} + a$, there exists a prime divisor $q > 3$ of $3^{2m} + a$ such that $v_q(3^{2m} + a)$ is odd.
- If $a$ is even and $3 \mid a$, take a sufficiently large prime $p$ and sufficiently large $m$ such that $p^{2m} + a$ is not a perfect square. Since $2, 3 \nmid p^{2m} + a$, it has a prime divisor $q > 3$ for which $v_q(p^{2m} + a)$ is odd.
- If $a$ is odd and $3 \mid a$, take $p = 2$ and $m$ sufficiently large so that $2^{2m} + a$ is not a perfect square. Since $2, 3$ are not divisors of $2^{2m} + a$, it has a divisor $q > 3$ so that $v_q(2^{2m} + a)$ is odd.
- If $a$ is odd and $a \equiv 1 \pmod{3}$, take $p = 2$ and $m$ sufficiently large so that $2^{2m} + a$ is not a perfect square. Since $2, 3$ are not divisors of $2^{2m} + a$, it has a divisor $q$ with $v_q(2^{2m} + a)$ odd.

Finally, consider the case when $a$ is odd and $a \equiv -1 \pmod{3}$. Assume the lemma is false. For sufficiently large odd $x$, $2^{2x} + a$ is not a perfect square. By our assumption, for all primes $q > 3$, $v_q(2^{2x} + a)$ is even. Thus, $v_3(2^{2x} + a)$ is odd. Hence, $\frac{2^{2x} + a}{3}$ is a perfect square and odd. So,
$$\frac{2^{2x} + a}{2} = b^2 \implies 2^{2x} + a = 3b^2 \equiv 3 \pmod{8} \implies a + 1 \equiv 4 \pmod{8}$$
Which means $v_2(a + 1) = 2$.

Now observe that, for large odd $x$,
$$v_2(3^{2x} - 1) = v_2(x) + 3 = 3$$
But then,
$$v_2(3^{2x} + a) = v_2(3^{2x} - 1 + a + 1) = \min\{v_2(3^{2x} - 1), v_2(a + 1)\} = 2$$
Since $3^{2x} + a$ is not a perfect square for large $x$, $3$ does not divide it and $v_2(3^{2x} + a)$ is 2. Hence, $3^{2x} + a$ must have a divisor $q > 3$ with $v_q(3^{2x} + a)$ odd. This contradicts our assumption. $\blacksquare$

2. Lemma 2: Given any $r \in \mathbb{N}$ and $r$ integers $a_1, a_2, \dots, a_r$ such that at least one of them is non-zero, we can find distinct primes $p_1, p_2, \dots, p_r$ and positive integers $m_1, m_2, \dots, m_r$ such that the number
$$(p_1^{2m_1} + a_1)(p_2^{2m_2} + a_2) \dots (p_r^{2m_r} + a_r)$$
has a prime divisor $q > 3$ such that
$$v_q((p_1^{2m_1} + a_1)(p_2^{2m_2} + a_2) \dots (p_r^{2m_r} + a_r))$$
is odd. In particular, the number is not a perfect square.

Proof:
We can cancel out all terms of the form $(p_k^{2m_k} + a_k)$ where $a_k = 0$ since it contributes a perfect square. So, WLOG, assume all $a_i \ne 0$. We will prove the claim by induction on $r$.

The base case is basically the previous lemma. Now assume that the lemma is true for $r = 1, 2, \dots, k-1$. Therefore, by induction hypothesis, there are $k-1$ primes $q_2, q_3, \dots, q_k$ and $k-1$ positive integers $m_2, m_3, \dots, m_k$ such that
$$Q = (q_2^{2m_2} + a_2) \dots (q_k^{2m_k} + a_k)$$
has a prime divisor $q > 3$ such that $v_q(Q)$ is odd.

Now by Dirichlet's theorem, there exists a sufficiently large prime $p \ne q$ such that
$$p \not\equiv 1 \pmod{q} \quad \text{and} \quad p \not\equiv -1 \pmod{q}$$
Since $q > 3$, this can be found. Now, observe that for sufficiently large $m$, $q$ can't divide both $p^{2m} + a_1$ and $p^{2m+2} + a_1$ since otherwise, $q$ will divide their difference, i.e., $q \mid p^{2m}(p-1)(p+1)$. This is a contradiction.

So, we can find $p$ and $m_1$ such that $v_q(p^{2m_1} + a_1) = 0$.

So indeed,
$$v_q((p^{2m} + a_1)(q_2^{2m_2} + a_2) \dots (p_k^{2m_k} + a_k))$$
is odd. And the induction is complete. $\blacksquare$

3. Main Problem:
Assume that
$$a = p_1^{g_1} p_2^{g_2} \dots p_r^{g_r}$$
and
$$b = p_1^{h_1} p_2^{h_2} \dots p_r^{h_r}$$
Assume for the sake of contradiction that $a \ne b$. Therefore, there is some $i$ for which $g_i \ne h_i$.

Take
$$n = p_1^{x_1} p_2^{x_2} \dots p_r^{x_r}$$
where $x_i = q_i^{c_i} - g_i - 1$ where primes $q_i$ and powers will be determined later. Then
$$\tau(\tau(an)) = \tau(q_1^{c_1} q_2^{c_2} \dots q_r^{c_r}) = (c_1 + 1)(c_2 + 1) \dots (c_r + 1)$$
So for all even $c_i$, $\tau(\tau(an))$ is odd.

Now observe that,
$$\tau(\tau(bn)) = \tau((q_1^{c_1} + h_1 - g_1)(q_2^{c_2} + h_2 - g_2) \dots (q_r^{c_r} + h_r - g_r))$$

Since there exists at least one $h_k - g_k \ne 0$, by the previous lemma, there exist distinct primes $q_1, q_2, \dots, q_r$ and even $c_1, c_2, \dots, c_r$ such that $(q_1^{c_1} + h_1 - g_1)(q_2^{c_2} + h_2 - g_2) \dots (q_r^{c_r} + h_r - g_r)$ is not a perfect square. So for that particular $n$,
$$\tau(\tau(bn)) = \tau((q_1^{c_1} + h_1 - g_1)(q_2^{c_2} + h_2 - g_2) \dots (q_r^{c_r} + h_r - g_r)) = \text{even}$$

Hence, $\tau(\tau(an)) \ne \tau(\tau(bn))$. This is a contradiction. $\blacksquare$