Find all positive integers $n$ such that $\varphi(n)$ divides $n^2 + 3$

First, we observe that $n$ can't be even. If it were even, $n^2+3$ would be odd and hence $\varphi(n)$ couldn't divide $n^2+3$ as $\varphi(n)$ is always even unless $n=1,2$. Since $\varphi(n)=1$ for $n=1,2$, these are two trivial solutions.

Let $n=3^ap_1^{a_1}p_2^{a_2}\ldots p_k^{a_k}$, where $p_j$'s are primes bigger than $3$ and $a_j\geq1$. If for some $j$ we have $a_j\geq2$, then $p_j\mid \varphi(n)\implies p_j\mid n^2+3\implies p_j\mid3$. A contradiction! Hence $a_j=1$ for all $1\leq j\leq k$. Now if $a>0$, $v_3(n^2+3)=1$. Since $v_3(\varphi(n))\geq(a-1)$, we must have $a=2$ and $3\nmid p_j-1$ for all $1\leq j\leq k$.

case $1$: Let $a=0$. Then $n=p_1p_2\ldots p_k$ and $\varphi(n)=(p_1-1)(p_2-1)\ldots(p_k-1)$. clearly $v_2(\varphi(n))\geq2^k$ and hence $v_2(n^2+3)\geq2^k$. Since $n$ is odd, $n^2\equiv1\pmod{8}\implies n^2+3\equiv4\pmod{8}\implies v_2(n^2+3)=2$. This means $k\leq2$.

For $k=1$, we have $n$ is a prime $p$ and $(p-1)\mid (p^2+3)$. Now $(p-1)\mid(p-1)^2=p^2-2p+1\implies (p-1)\mid((p^2+3)-(p^2-2p+1))=2(p+1)$. Since $p$ is odd, $(p-1)=2$ or $(p-1)=4$. since we have assumed that $p>3$, in this case the only solution is $p=5$.

For $k=2$ we have the situation $n=pq$ for two distinct primes bigger than $3$. We have to solve the congruence $(pq)^2+3\equiv0\pmod{(p-1)(q-1)}$

$(p-1)(q-1)\mid((pq)^2-p^2q-pq^2+pq)\implies (p-1)(q-1)\mid(p^2q+q^2p+3-pq)$

$(p-1)(q-1)\mid(p^2q-p^2-pq+p)$ and $(p-1)(q-1)\mid(q^2p-q^2-pq+q)$. Therefore,

$(p-1)(q-1)\mid(p^2q+q^2p-p^2-q^2-2pq+p+q-(p^2q+q^2p+3-pq))\implies (p-1)(q-1)\mid(p^2+q^2+pq-p-q+3)\implies (p-1)(q-1)\mid(p^2+q^2+2)$

$(p-1)\mid(p^2+q^2+2)\implies(p-1)\mid(p^2+q^2+2-p^2+2p-1)=(q^2+2p+1)\implies (p-1)\mid(q^2+2p-2p+3)=(q^2+3)$. Similarly we get $(q-1)\mid(p^2+3)$. Let $\mathrm{WLOG}$ $p<q$. If $p=3$ then we can deduce that $q=7$. Therefore $n=21$ is a solution. Let $p>q>3$. Since $(pq)^2+3\equiv4\pmod{8}$ and $(p-1)(q-1)\mid((pq)^2+3)$ we get $v_2(p-1)=v_2(q-1)=1$. Any odd prime dividing $p-1$ or $q-1$ divides $(pq)^2+3$ and hence $-3$ is a quadratic residue modulo those primes. Therefore they are either $3$ or of the form $6l+1$. If $(q-1)/2\equiv1\pmod{6}$ then $q-1\equiv2\pmod{6}$, which implies $3\mid pq$. A contradiction! Therefore $p=3,q=7$ is the only solution in this case.

case $2$: Let $a=1$. In this case $n=3$ is a solution as $\varphi(3)=2\mid3^2+3=12$.

We investigate now the other possibilities. For $a=1$, if $n\neq3$, then $n$ can be of the form $3p$ for some odd prime $p>3$. Otherwise $v_2(\varphi(n))>2$ which can't be possible as we have shown before.

In this case, the situation is, $\varphi(3p)=2(p-1)\mid(9p^2+3)$. We have $(p-1)\mid(9p^2+3)\implies (p-1)\mid(9p^2+3-9p^2+9p)=(9p+3)\implies (p-1)\mid12$. Then $p$ can be $7$ or $13$. For $p=13$, $v_2(\varphi(n))=3$ which is not possible. So in this case only possible solution is $n=3\cdot7=21$

last case: For $a=2$, we have $9$ is a solution. By similar arguments as above, we can show that there can't be any other solutions.

Hence only possible solutions are $n=1,2,3,5,9,21$

DONE!

Note that $\phi(n)=1$ if and only if $n=1,2$, and even if and only if $n>2$. Therefore, $\boxed{n=1,2}$ are both solutions to

$$ \phi(n) \mid (n^2+3). \quad \ldots \quad (1) $$

Henceforth, assume $n>2$. Then $\phi(n)$ is even, and so $n$ must be odd. But then $n^2+3 \equiv 4\pmod{8}$, so $n^2+3=4m$, with $m$ odd.

Since $\phi$ is multiplicative:

$$ \phi(mn) = \phi(m) \cdot \phi(n) $$

whenever $\gcd(m,n)=1$, and

$$ \phi(p^{\alpha}) = p^{\alpha-1}(p-1), $$

we have

$$ \phi(n) = \prod_{p^{\alpha}\,\mid\mid\,n} p^{\alpha-1}(p-1). $$

Each prime factor $p$ of $n$ contributes $p-1$ to $\phi(n)$. Since $p-1$ is even, $\phi(n)$ is divisible by $2^k$, where $k$ equals the number of distinct prime divisors of $n$. Since $n^2+3=4m$, with $m$ odd, $k=1$ or $2$.

$\bullet$ Suppose $k=1$, and write $n=p^{\alpha}$, $p$ prime. Then eqn.$(1)$ gives

$$ p^{\alpha-1}(p-1) \mid (p^{2\alpha}+3). \quad \ldots \quad (2) $$

If $\alpha=1$, then $(p-1) \mid (p^2+3)$, and so $(p-1) \mid \big((p^2+3)-(p^2-1)\big)$. Thus, $p-1 \in \{1,2,4\}$, and $p=3$ or $5$; so $n=3,5$ are solutions.

If $\alpha>1$, then $p \mid (p^{2\alpha}+3)$, and so $p \mid 3$. This implies $p=3$, and eqn.$(2)$ gives

$$ 2 \cdot 3^{\alpha-1} \mid 3\big(3^{2\alpha-1}+1\big). $$

Since the highest power of $3$ dividing the RHS is $1$, we can only have $\alpha=2$. We note that $\phi(3^2) \mid (3^4+3)$; so $n=3^2$ is a solution.

So the three solutions in this case are $\boxed{n=3,5,3^2}$.

$\bullet$ Suppose $k=2$, and write $n=p^{\alpha}q^{\beta}$, $p,q$ primes, $\alpha \ge \beta \ge 1$. Note that since $4$ is the highest power of $2$ dividing the LHS of eqn.$(1)$, we must have $p \equiv q \equiv 3\pmod{4}$.

Now eqn.$(1)$ gives

$$ p^{\alpha-1} q^{\beta-1} (p-1)(q-1) \mid (p^{2\alpha}q^{2\beta}+3). \quad \ldots \quad (3) $$

If $\alpha=1$, then $\beta=1$, and eqn.$(3)$ gives

$$ (p-1)(q-1) \mid (p^2q^2+3). \quad \ldots \quad (4) $$

Thus, $(p-1) \mid \big((p^2q^2+3)-(p^2-1)q^2\big)=(q^2+3)$; similarly, $(q-1) \mid (p^2+3)$.

If $p=3$, this gives $(q-1) \mid 12$. Since $q-1 \equiv 2\pmod{4}$, $q>p$, we have $q=7$. Note that $\phi(3 \cdot 7) \mid (21^2+3)$; so $n=3 \cdot 7$ is a solution.

Now suppose $3<p<q$. Then $p^2+3 \equiv q^2+3 \equiv 1\pmod{3}$, so that $p \equiv q \equiv 2\pmod{3}$ since $(p-1) \mid (q^2+3)$ and $(q-1) \mid (p^2+3)$. So both $p+1$ and $q+1$ are multiples of $3$ and $4$, and hence $p,q \equiv -1\pmod{12}$.

Now suppose $\ell$ is a prime divisor of $(pq)^2+3$, $\ell>3$. Then $-3$ is a quadratic residue modulo $\ell$, and so we have

$$ \left(\frac{-1}{\ell}\right) = \left(\frac{3}{\ell}\right) = \pm 1. $$

If each is $+1$, then $\ell \equiv 1\pmod{4}$ and so $1=\left(\frac{\ell}{3}\right)$. This implies $\ell \equiv 1\pmod{3}$. Together we get $\ell \equiv 1\pmod{12}$.

If each is $-1$, then $\ell \equiv -1\pmod{4}$ and so $1=\left(\frac{\ell}{3}\right)$. Again $\ell \equiv 1\pmod{3}$, and we get $\ell \equiv 7\pmod{12}$.

Hence, $\ell \equiv 1\pmod{6}$. Since $p,q \equiv -1\pmod{12}$, $3 \nmid (p-1)$ and $3 \nmid (q-1)$. So both $p-1,q-1$ are of the form $2t$, where $t$ is a (possibly empty) product of primes of the form $6\lambda+1$.

The empty product gives $p-1=2$, and has been dealt with. Otherwise, both $p-1$ and $q-1$ are of the form $12\lambda+2$, which contradicts the fact that $p,q \equiv -1\pmod{12}$.

We conclude that there is no solution with $3<p<q$.

If $\alpha>1$, then $p$ must divide $p^{2\alpha}q^{2\beta}+3$. Hence, $p \mid 3$, and so $p=3$. Now eqn.$(3)$ gives

$$ 2(q-1)3^{\alpha-1}q^{\beta} \mid 3\big(3^{2\alpha-1}q^{2\beta}+1\big). $$

Since the highest power of $3$ dividing the RHS is $1$, we can only have $\alpha=2$. Thus,

$$ 2(q-1)q^{\beta} \mid (27q^{2\beta}+1). $$

However, $q$ divides the LHS but not the RHS, so we have no further solutions.

The only solution in this case is $\boxed{n=3 \cdot 7}$.

Therefore,

$$ \phi(n) \mid (n^2+3) \Longleftrightarrow n \in \{1,2,3,5,9,21\}. $$