La mia soluzione del 3 è un po' più lunga di quella di Elianto:
Prendo un primo $ p\geq 20 $ tale che $ p\equiv 1 \mod 4 $.
Allora $ \Big( \frac{-1}{p} \Big) = (-1)^{\frac{p-1}{2}} = 1 $, quindi esiste $ n $ tale che $ n^2+1\equiv 0 \mod p $ con $ n\leq \frac{p-1}2 $.
Sia $ n=\frac{p-k}{2} $ con $ k $ intero positivo dispari. Allora
$ \left( \frac{p-k}{2} \right) ^2 +1 \equiv 0 \mod p $, quindi $ k^2+4\equiv 0 \mod p $, da cui $ p\leq k^2+4 $, ovvero $ k\geq \sqrt{p-4} $.
Quindi $ n\leq \frac{p-\sqrt{p-4}}{2} $, da cui $ p\geq 2n+\sqrt{p-4} $.
Ma per $ p\geq 20 $, $ 2n+\sqrt{p-4} \geq 2n + 4 $, quindi
$ p\geq 2n+\sqrt{p-4} \geq 2n + \sqrt{2n+4-4} = 2n+\sqrt{2n} $.
L'uguaglianza vale inoltre solo se $ p=20 $, assurdo.
Quindi per ogni $ p\equiv 1 \mod 4 $ e $ \geq 20 $ ho una soluzione per $ n $ che rispetta le condizioni; è ovvio che per due primi $ p,q $ diversi ottengo due $ n $ diversi, perché $ pq\geq (2n+\sqrt{2n})^2>n^2+1 $, quindi ho generato infiniti $ n $.
Ho fatto anche il 2 ma la soluzione è troppo brutta per essere scritta qui.
]