Maths Olympiad Prep

Library / /9 of 14

Number theory Difficulty 4.9 AIME Prove it United States

Problem:

Prove that there are infinitely many positive integers nn for which n2+1n^{2}+1 has no repeated prime factors (that is, n2+1n^{2}+1 is squarefree).

Solution

Solution:

By Fermat's Christmas theorem, the only primes which may divide n2+1n^{2}+1 other than 22 are those which are 1(mod4)1 \pmod{4}, and moreover 22n2+12^{2} \nmid n^{2}+1 for any nn.

Consider primes p1(mod4)p \equiv 1 \pmod{4}. Observe that for any xx, we have
#{nxn2+10(modp2)}2p2x+2 \#\{n \leq x \mid n^{2}+1 \equiv 0 \pmod{p^{2}}\} \leq \frac{2}{p^{2}} x + 2
since there are at most two solutions mod p2\bmod\ p^{2} to n21(modp2)n^{2} \equiv -1 \pmod{p^{2}}.

Summing over all primes p1(mod4)p \equiv 1 \pmod{4} now implies the result, since
p12p2<2(142+182+)=π2618<1 \sum_{p \equiv 1} \frac{2}{p^{2}} < 2\left(\frac{1}{4^{2}} + \frac{1}{8^{2}} + \ldots\right) = \frac{\pi^{2}}{6} \cdot \frac{1}{8} < 1

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.