Tessellate S.T.E.M.S (2019) - Mathematics - Category C - Set 1 - Objective Problem 4

Clearly $n=1,2$ are solutions. Suppose $n > 2.$ Since $\phi(n)$ is even, $n^2+3$ must be even, so $n$ is odd. Then $n^2 + 3 \equiv 4 \pmod 8,$ so there are at most $2$ factors of $2$ in $\phi(n).$ This implies that there are at most two primes dividing $n.$ Now if $n$ is a prime power $p^k,$ we get $p^{k-1}(p-1)|(p^{2k}+3).$ If $k > 1$ then we get $p^{k-1}|3,$ so $p=3$ and $k=2.$ If $k=1$ we get $(p-1)|(p^2+3),$ but $(p-1)|(p^2-1)$ as well, so $(p-1)|4,$ so $p=2,3,5.$ So the only prime power solutions are $n=2,3,5,9.$

It remains to look at $n = p^aq^b$ where $p,q$ are distinct primes and $a,b$ are positive integers. By the previous remark about factors of $2,$ it must be the case that both $p$ and $q$ are $3 \pmod 4.$ If one of the exponents, say $a,$ is $\ge 2,$ then $\phi(n)$ is divisible by $p^{a-1},$ and so $p^{a-1}|(n^2+3),$ so $p^{a-1}|3,$ so $p=3$ and $a=2.$ So we've narrowed it down to two cases: (1) $n=9q$ and (2) $n=pq$ with $p,q$ distinct primes congruent to $3 \pmod 4.$

In case (1), we get $6(q-1)|(81q^2+3),$ so $2(q-1)|(27q^2+1),$ but $2(q-1)|(27q^2-27)$ as well, so $2(q-1)|28,$ which gives $q=2,3,8,15,$ but $q\ne 3$ is supposed to be an odd prime congruent to $3 \pmod 4,$ so there are no solutions in this case.

In case (2), we get $(p-1)(q-1)|(p^2q^2+3).$ Since $(p-1)(q-1)|(p^2q^2-p^2-q^2+1),$ we can subtract to get $(p-1)(q-1)|(p^2+q^2+2).$ Letting $A = \frac{p-1}2, B = \frac{q-1}2$ and simplifying gives $AB | (A^2+A+B^2+B+1)$ which is equivalent to $\begin{aligned} A &| (B^2+B+1) \\ B &| (A^2+A+1) \end{aligned}$

This is a version of a well-known Vieta descent problem. The key observation is that if $(A,B)$ is a solution, then so is $\left( \frac{A^2+A+1}{B}, A \right),$ and it's not hard to check that if $1 < A < B,$ then $\frac{A^2+A+1}{B} < A$ (note that $A = B$ and $A+1 = B$ are impossible). So we can keep reducing the solution to get one with $A=1,$ which implies $B=1$ or $3.$ (In fact $(1,3)$ reduces to $(1,1)$ in this way.)

So we can generate all solutions by starting at $(1,1)$ and reversing the process: $(1,1) \to (1,3) \to (3,13) \to (13,61) \to (61, 291) \cdots$ which leads to the candidate solutions $(3,3) \to (3,7) \to (7,27) \to (27,123) \to (123, 583) \cdots$ and now the thing to check is that at least one of the entries in each ordered pair is divisible by $3,$ so that $(3,7)$ is the largest ordered pair consisting of primes.

Well, the sequence $1,3,13,61,291,\ldots$ is in OEIS, so I'll just punt to that. It satisfies the recurrence $a_n = 6a_{n-1}-6a_{n-2}+a_{n-3}$ (provable by an easy induction), so $a_n \equiv a_{n-3} \pmod 3,$ so mod 3 that sequence is just $1,0,1, 1,0,1, 1,0,1, \ldots,$ so the sequence of solutions $3,7,27,123,583,\ldots$ is just $0,1,0,0,1,0,0,1,0, \ldots$ mod 3, so at least one of any two consecutive terms is divisible by $3,$ which proves that $(3,7)$ is the largest ordered pair consisting of primes.

So the full set of solutions to $\phi(n) | (n^2+3)$ is $n=1,2,3,5,9,21,$ and the answer is $\fbox{21}.$