Niech \(\displaystyle{ \mathbb{P}}\) oznacza zbiór liczb pierwszych.
Lemat 1.Niech \(\displaystyle{ p\in \mathbb{P}\setminus \{2\}}\) wówczas kongruencja \(\displaystyle{ x^2+1\equiv 0\,(\mathrm{mod}\,p^2)}\) ma co najwyżej dwa rozwiązania modulo \(\displaystyle{ p^2}\). dowód. Załóżmy, że \(\displaystyle{ x, y\in \mathbb{Z}/p^2\mathbb{Z}}\) są takie, że \(\displaystyle{ x^2+1=0}\) oraz \(\displaystyle{ y^2+1=0}\). Wówczas \(\displaystyle{ x^2-y^2=0}\) czyli \(\displaystyle{ (x-y)(x+y)=0}\). Niech \(\displaystyle{ (p)}\) oznacza ideał w pierścieniu \(\displaystyle{ \mathbb{Z}/p^2\mathbb{Z}}\) generowany przez \(\displaystyle{ p}\). Mamy przypadki
1) \(\displaystyle{ (x-y)\in (p)}\), \(\displaystyle{ (x+y)\in (p)}\)
Wówczas \(\displaystyle{ 2x\in (p)}\) i \(\displaystyle{ 2y\in (p)}\). Na mocy \(\displaystyle{ p\neq 2}\) dostajemy \(\displaystyle{ x\in (p)}\) oraz \(\displaystyle{ y\in (p)}\). To daje sprzeczność z równościami \(\displaystyle{ x^2+1=y^2+1=0}\).
2) \(\displaystyle{ (x-y)=0}\) czyli \(\displaystyle{ x=y}\)
3) \(\displaystyle{ x+y=0}\) czyli \(\displaystyle{ x=-y}\)
Oznacza to, że dowolne dwa rozwiązania naszej kongruencji wzięte modulo \(\displaystyle{ p^2}\) są równe albo różnią się znakiem.
Lemat 2.Kongruencja \(\displaystyle{ x^2+1\equiv 0\,(\mathrm{mod}\,4)}\) nie ma rozwiązań.
Niech \(\displaystyle{ A}\) oznacza zbiór liczb \(\displaystyle{ n\in \mathbb{N}}\) takich, że \(\displaystyle{ n^2+1}\) jest podzielna przez kwadrat liczby pierwszej. Niech \(\displaystyle{ p\in \mathbb{P}}\) i niech \(\displaystyle{ A_p}\) będzie zbiorem tych liczb \(\displaystyle{ n\in \mathbb{N}}\), że \(\displaystyle{ p^2|n^2+1}\).
Z Lematu 2 dostajemy \(\displaystyle{ A=\bigcup_{p\in \mathbb{P}\setminus \{2\}}A_p}\)
Teraz niech \(\displaystyle{ N}\) będzie liczbą naturalną większą od zera. Wówczas na mocy Lematu 1 \(\displaystyle{ |A_p\cap [0,N]|\leq 2\left(\left[\frac{N}{p^2}\right]+1\right)}\)
Stąd mamy oszacowanie \(\displaystyle{ |A\cap [0,N]|\leq \sum_{p\in \mathbb{P}\setminus \{2\}}|A_p\cap [0,N]|\leq \sum_{p\in \mathbb{P}\setminus \{2\},p\leq N}2\left(\left[\frac{N}{p^2}\right]+1\right)=2\sum_{p \in \mathbb{P}\setminus \{2\}}\frac{N}{p^2}+2\pi(N)}\)
gdzie \(\displaystyle{ \pi(N)}\) oznacza liczbę liczb pierwszych mniejszych równych \(\displaystyle{ N}\).
Mamy, że \(\displaystyle{ \sum_{p\in \mathbb{P}\setminus \{2\}}\frac{1}{p^2}\leq \frac{1}{3^2}+\sum_{p\in \mathbb{P},\,p> 3}\frac{1}{p^2}\leq \frac{1}{9}+\sum_{n=4}^{+\infty}\frac{1}{n^2}\leq \frac{1}{9}+\sum_{n=4}^{+\infty}\frac{1}{n(n-1)}=\frac{1}{9}+\frac{1}{3}=\frac{4}{9}}\)
Zatem \(\displaystyle{ |A\cap [0,N]|\leq 2\sum_{p \in \mathbb{P}\setminus \{2\}}\frac{N}{p^2}+2\pi(N)\leq 2N\cdot \frac{4}{9}+2\pi(N)}\)
Stąd \(\displaystyle{ \lim \sup_{N\rightarrow +\infty}\frac{|A\cap [0,N]|}{N}\leq \lim_{N\rightarrow +\infty}\left(\frac{8}{9}+2\frac{\pi(N)}{N}\right)=\frac{8}{9}}\)
Uzyskaliśmy, że zbiór \(\displaystyle{ A}\) ma gęstość (to ta granica górna) mniejszą od \(\displaystyle{ 1}\). Oznacza to, że jego dopełnienie nie może być zbiorem skończonym. Stąd dopełnienie \(\displaystyle{ A}\) jest zbiorem nieskończonym, a to należało wykazać.