See also here http://artofproblemsolving.com/community/c6h268806, but no answer. This also appears as question 25 in the Leo Moser Number Theory book.

Actually, this succumbs to rather elementary analytic tools. Let $f(m)$ be the number of positive integers $n \le m$, such that $n^2+1$ is squarefree. Also, for a prime $p$, suppose that $f_p(m)$ is the number of positive integers $\le m$ such that $p^2|n^2+1$. Note that $p$ is odd. Then, since there are atmost $2$ solutions to $n^2 \equiv -1 \pmod{p^2}$, in $\mathbb{Z}/ p^2 \mathbb{Z}$, we have \[f(m) \ge m-\sum_{2<p < m}f_p(m) \ge m- \sum_{2<p<m}2 \left(1+ \frac{1}{p^2} \right) \ge m-2(\pi(m)-1)-2m \sum_{2<p<m}\frac{1}{p^2}\]\[ \ge m-2\pi(m)-2m \left( \sum_{r=0}^{\infty}\frac{1}{r^2} -1-\frac{1}{4} \right) \ge m-2\pi(m)-2m\left( \frac{\pi^2}{6} - \frac{5}{4} \right) = m \left( \frac{7}{2} - \frac{\pi^2}{3} \right) -2\pi(m) = o(m)\]So, there exist infinitely many $n$ with $n^2+1$ squarefree.

You can do even better, just summing over $p$ $1$ mod $4$ that are odd. And the relevant sum $\frac {2} {p^2}$ over $p$ $1$ mod $4$ actually ends up being less than $.06$, so clearly there are infinitely many integers $n$ with $n^2+1$. Just bounding by the sum of the squares being less than $\frac {5} {3}$ and then throwing out all the squares before $\frac {2} {11^2}$ except $\frac {2} {5^2}$ works nicely. The above poster is slightly wrong - you can say the lim inf of the proportion of the first $K$ numbers is at least $.94$, but they do not necessarily actually have a density. Also if you want to be a little more rigorous or not analytic you can consider things from $1$ to $N$ and use some ceilings (and the primes are sparse enough to make this still easy work, although if you want you can use PNT).

This is a bit off topic however.. yugrey wrote: The above poster is slightly wrong - you can say the lim inf of the proportion of the first $K$ numbers is at least $.94$, but they do not necessarily actually have a density. Isn't that the definition of asymptotic density ?

How do you guys know analytic number theory?

dibyo_99 wrote: This is a bit off topic however.. yugrey wrote: The above poster is slightly wrong - you can say the lim inf of the proportion of the first $K$ numbers is at least $.94$, but they do not necessarily actually have a density. Isn't that the definition of asymptotic density ? This is not the definition of density. To have a density the proportion of the first $k$ must have a limit. How do I know analytic number theory? PFTB (Problems from the Book, Dospinescu and Andreescu) Chapter 17 (I think this is the right chapter number) is a great place to start.

Oh right, of course. Sorry. Silly me.

Also this problem is unsuitably easy for a China TST #3...

It seems to be easier than the corresponding Problem 1.

When are the China TST's (e.g. dates)?

Also see here.

Take a big $N$ and consider a fixed prime $p$, let $\mathcal{D}_{p,N}$ the set of numbers $n<N$ where $p^2 | n^2+1$. We can see that $2/p^2$ of the numbers $<N$ belong in this set and if we sum $2/p^2$ over all primes $1 \bmod 4$, the sum is $<1$,so we get that not all numbers $<N$ belong in some set $\mathcal{D}$,

Let $n=k^2+r$ and $1 \leq r \leq 2k $ . We want to count how many $1 \leq x \leq k $ such that there is an odd prime like $p$ : $p^2 \vert x^2+1$ . Suppose that the number of these numbers is $t$. So : $t \leq k \sum \frac{2}{p^2} $ . because we have atmost 2 numbers in \left $\{ x+1,x+2,...,x+p^2 \right \}$ such that $ p^2 \vert n^2+1 $ . $\sum \frac{2}{p^2}\leq 2(\frac{1}{5^2}+\frac{1}{6^2}+...)<2(\frac{1}{4\times 5}+\frac{1}{5\times 6}+...)<\frac{1}{4}$ so the numbers $x^2+1$ such that $1\leq x\leq k$ and $x^2+1$ is squarefree is more than$ \frac{k}{2}$. so we have at least $ \frac{k}{2}$ numbers from $\{ 1^2+1 , 2^2+1 , ... , k^2 + 1 \right \}$ . And It's true for all natural numbers $k$. so we have $\frac{4k}{2}$ numbers from $\{ 1^2+1 , 2^2+1 , ... , (4k)^2 + 1 \right \}$ . so at least we have $ k$ numbers from $\{ k^2+1 , (k+1)^2+1 , ... , (4k)^2 + 1 \right \}$ . So the Squarefree Numbers in the form $x^2+1$ is infinitely .

Here is a proof of a much stronger statement, which is example 1.6 in Freidlander and Iwaneic: Claim: $$F(x) = C\sqrt{x} + \mathcal{O}(x^{1/3 + \epsilon})$$for all $\epsilon > 0$ where $F(x) = |\{n^2 + 1 \le x| n^2 + 1\text{ squarefree}\}|$. where $$C = \prod_{p, p\equiv 1\pmod{4}} \left(1 - \frac{2}{p^2}\right)$$Proof: We have that $$F(x) = \sum_{m^2 + 1\le x} f(m^2 + 1)$$where $f(n) = 1$ if $n$ is squarefree, and 0 otherwise. Note that $f(n) = \sum_{d^2|n}\mu(d)$ where $\mu(n)$ is the mobius function. Plugging this in and reversing the order of summation, we have that $$F(x) = \sum_{d\le x; p|d\rightarrow p\equiv 1\pmod{4}}\mu(d)\mathcal{A}_{d^2}$$where $$\mathcal{A}_d = \sum_{m^2 + 1\le x; d|m^2 + 1} 1$$. For all squarefree $d$ such that $p|d\rightarrow p\equiv 1\pmod{4}$, we have that $$\mathcal{A}_{d^2} = \frac{\tau(d)\sqrt{x}}{d^2} + \mathcal{O}(\tau(d))$$. Let $$F_1(x) = \sum_{d\le x^{1/3}; p|d\rightarrow p\equiv 1\pmod{4}}\mu(d)\mathcal{A}_{d^2}$$ It then follows that $$F_1(x) = Cx + \mathcal{O}(x^{1/3}\log x)$$where $$C = \sum_{d ; p|d\rightarrow p\equiv 1\pmod{4}}\frac{\tau(d)\mu(d)}{d^2} = \prod_{p, p\equiv 1\pmod{4}} \left(1 - \frac{2}{p^2}\right)$$ It is now sufficient to bound $$F_2(x) = \sum_{x^{1/3} < d\le x; p|d\rightarrow p\equiv 1\pmod{4}}\mu(d)\mathcal{A}_{d^2}\le \sum_{d\le x; p|d\rightarrow p\equiv 1\pmod{4}}\mathcal{A}_{d^2}$$ Clearly, this is less than or equal to the number of solutions to $n^2 + 1 = d^2 k$ for some $k\le x/((x^{1/3})^2) = x^{1/3}$ Note that for all $k$, this is just a Pell equation, and since the solutions grow exponentially, for each $k$, the contribution is at most $\mathcal{O}(\log x)$. Therefore, $F_2(x) = \mathcal{O}(x^{1/3}\log x)$, so $$F(x) = Cx + \mathcal{O}(x^{1/3 + \epsilon})$$for all $\epsilon > 0$ as desired. This claim clearly implies that there are infinitely many squarefree integers one more than a perfect square.

my solution is similar to the above solutions but in more details: lemma: the polynomial $n^2+1$ has at most $two$ different roots modulo $p^2$ among the numbers $0,1,\cdots ,p^2-1$ where $p$ is a prime number. Prove:you can easily prove the lemma in the case $p=2$ so assume that $p$ is odd number assume for a sake of a contradiction that there are at least three distinct integers $a,b,c$ such that $a^2+1,b^2+1,c^2+1$ are divisible by $p^2$ then $a^2\equiv b^2\pmod{p^2}\longrightarrow p^2\mid (a-b)(a+b)$(1) now consider two cases: 1)$p\mid a-b$ then because $a-b<b^2\longrightarrow p^2\nmid a-b$ so from (1) we deduce that $p\mid a+b$ but $p\mid (a-b)+(a+b)=2a,p\mid (a+b)-(a-b)=2b$ thus because $p\neq 2\longrightarrow p\mid a$ but it is a contradiction with the assumption $p^2\mid a^2+1$. 2)$p\nmid a-b$ then from (1) $p^2\mid a+b$ similarly we prove that $p^2\mid a+c$ from these two we deduce that $p^2\mid b-c$ but because $b-c<p^2$, $b=c$ but it is contradiction with our assumption. Back to the main problem: Assume that $N$ is a large positive integer divisible by $p^2$ and the prime numbers between them are $p_1,p_2,\cdots,p_s$. Consider the sets $\{ 1,2,\cdots ,p^2\},\{p^2+1,p^2+2,\cdots ,2p^2\},\cdots,\{N-P^2+1,N-p^2+2,\cdots ,N\}$ from the lemma from each set there are at most two numbers like $n$ such that $p^2\mid n^2+1$ so between $1,2,\cdots ,N$ there are at most $\frac{2N}{p^2}$ numbers such that $p^2\mid n^2+1$ so the number of number of square free numbers are at least $t=N-(2N(\sum_{1\le i\le s} \frac{1}{p_i^2})$ but from this problem $\sum_{1\le i\le s} \frac{1}{p_i^2}<\frac{1}{2}$ so $t=N-(2N(\sum_{1\le i\le s} \frac{1}{p_i^2})>N-2N.\frac{1}{2}=0\longrightarrow t>0\longrightarrow t\ge 1$ thus between $1,2,\cdots ,N$ there is at least one square free number in a form $n^2+1$ now do the same thing with the numbers $N+1,\cdots ,2N$ and so on. DONE

I am silly

u don't know the meaning of square-free. here. https://en.wikipedia.org/wiki/Square-free_integer

Thank you, libra8

Lemma. For a prime $p$, $n^2+1 \equiv 0 \pmod{p^2}$ has at most two solutions in $\pmod{p^2}$. Proof of Lemma. $p=2$ is trivial, so consider odd primes. Assume that a solution $x$ exists, then $-x$ is a solution as well. Assume for the sake of contradiction that another solution $a$ exists. Now $a^2+1 \equiv x^2+1 \pmod{p^2}$, so $p^2|a^2-x^2$. Since $a \not\equiv \pm x \pmod{p^2}$, we have $a-x \equiv a+x \equiv 0 \pmod{p}$, giving $x \equiv 0 \pmod{p}$. This gives us $0 \equiv x^2+1 \equiv 1 \pmod{p^2}$, a contradiction. We work for large enough $m$. Now denote $f(m)$ as the cardinality of the set $\{n|n \in \mathbb{N}, 1 \le n \le m, \text{ }n^2+1 \text{ is squarefree}\}$ Denote $X_{m,p}$ as the set $\{x|x \in \{1,2, \cdots m\}, p^2|x^2+1\}$. Since we just need to sum over $p \equiv 1 \pmod{4}$, $$f(m) = m-|\cup_{5 \le p < m} X_{m,p}| \ge m-\sum_{5 \le p <m} |X_{m,p}| \ge m-2\sum_{5 \le p <m} \lceil \frac{m}{p^2} \rceil$$$$ >m-\sum_{5 \le p < m} \left(\frac{2m}{p^2}+2\right) > m-2m \sum_{5\le p <m} \frac{1}{p^2} - 2 \pi (m) = m\left(1-2\sum_{5 \le p <m} \frac{1}{p^2} - \frac{2\pi (m)}{m}\right)$$$$>m(1-2\left(\frac{\pi^2}{6}-1-\frac{1}{4}\right) - \frac{2\pi (m)}{m}) = m\left(\frac{7}{2}-\frac{\pi^2}{3} - \frac{2\pi (m)}{m}\right) \ge cm$$for some $c$ as $\lim_{n \to \infty} \frac{\pi (n)}{n} =0$. Therefore, $f(n)$ goes to infinity as $n$ goes to infinity, as desired. $\blacksquare$

Darn, at this point it might just be easier to make a list of problems that aren't applications of the Probabilistic Method.

Unless I'm doing something wrong, we can tightly approximate the inequalities in several of the previous posts to get that for arbitrarily large $N$, at least $0.89N$ of the positive integers $n\leq N$ satisfy $n^2+1$ is squarefree. This is quite a difference in proportion of squarefree numbers when compared to the general distribution over all integers, which is $\frac{6}{\pi^2}\approx0.608$.

Let $Q$ denote the set of primes which are 1 mod 4 as well as $2$. And, let $S$ denote the set of numbers in the form $n^2+1$. By FCT only primes in $Q$ can divide an element in $S$. Notice that there are at most two residues $r$ mod $p^2$ where $r^2 \equiv -1$ (mod $p^2$) for any $p$ . Thus, if we let $\lambda_p(m)$ denote the number of positive integers $k \leq m$ where $p^2$ divides $k^2+1$, then we have \[ \lim_{k \to \infty} \frac{\lambda_p(k)}{k} \leq \frac{2}{p^2}\]Thus, we let $\lambda(k)=\max_{p \in Q}(\lambda_p(k))$ then we have \[ \lim_{k \to \infty} \frac{\lambda(k)}{k} \leq \sum_{p \in Q} \frac{2}{p^2} < \frac{1}{2}+\sum_{i=1}^{\infty} \frac{2}{(4i+1)^2} < \frac{1}{2}+\sum_{i=1}^{\infty}\frac{1}{(4i)^2}=\frac{1}{2}+\frac{\pi^2}{96}<1 \]Which implies that there are infitely many elements in $S$ not divisible by $p^2$ for any $p \in Q$ as desired.

Not to belabor the point, but: For natural \(n\), denote by \(\text{X}\left(n\right)\subseteq \left\{0,\dots, n-1\right\}\) the subset of elements \(x\colon\left\{0,\dots, n-1\right\}\) for which \(x^{2}+1\) is not squarefree. Likewise denote by \(\text{P}_{4,1}\left(n\right)\subseteq\left\{0,\dots, n-1\right\}\) the subset of elements \(p\colon\left\{0,\dots, n-1\right\}\) that are primes congruent to \(1\) modulo \(4\). For every element \(x\colon\text{X}\left(n\right)\) there must exist an element \(p\colon\text{P}_{4,1}\left(n\right)\) such that \(p^{2}\) divides \(x^{2}+1\). Conversely, for every element \(p\colon\text{P}_{4,1}\left(n\right)\) there are at most \(2+\frac{2n}{p^{2}}\) elements \(x\colon\text{X}\left(n\right)\) such that \(p^{2}\) divides \(x^{2}+1\). Trivially, \(\#\text{P}_{4,1}\left(n\right)\leq 1+\frac{n}{4}\). Thus \begin{align*}\#\text{X}\left(n\right)\ &\leq\ \sum_{p\colon\text{P}_{4,1}\left(n\right)} 2+\frac{2n}{p^{2}}\\ &=\ \underbrace{2\#\text{P}_{4,1}\left(n\right)}_{\leq\ 2\left(1+\frac{n}{4}\right)}\ +\ \underbrace{2n\sum_{p\colon\text{P}_{4,1}\left(n\right)} \frac{1}{p^{2}}}_{\leq\ 2n\sum_{t=1}^{\infty} \frac{1}{\left(4t+1\right)^{2}}\ \leq\ \frac{2n}{4}\sum_{t=1}^{\infty}\left(\frac{1}{4t-1}-\frac{1}{4t+3}\right)\ =\ \frac{n}{6}}\\ &\leq\ 2+\frac{2n}{3}.\end{align*} We conclude that for each natural \(n\) the number of naturals \(x\) less than \(n\) with \(x^{2}+1\) squarefree is at least \(\frac{n}{3}-2\), from which the claim immediately follows. \(\blacksquare\) (The raison d'être of this post is to formalize the essential—but rigorously insufficient—union bound insight as lazily and elementarily as possible. As such, more or less every inequality above can be substantially tightened with more discerning analysis.)

If $n^2+1$ is not squarefree, then there must exist some prime $p$ such that $p^2\mid n^2+1.$ Suppose that there exist two integers $x,y\in\{1,2,\cdots,p^2\},$ so that $x^2+1\equiv y^2+1\equiv0\pmod{p^2}.$ Subtracting gives $x^2-y^2\equiv0\pmod{p^2},$ so that $$p^2\equiv(x-y)(x+y).$$Then either $x-y\equiv x+y\equiv0\pmod{p}$, $p^2\mid x-y$, or $p^2\mid x+y$. If $x-y\equiv x+y\equiv0\pmod{p}$, then $x\equiv y\equiv0\pmod{p}$, then $x^2+1\equiv y^2+1\equiv0\pmod{p^2},$ a contradiction. If $p^2\mid x-y$, then $x-y>\ge p^2$, so that $x$ and $y$ cannot both be between $1$ and $p^2$, another contradiction. Thus we are forced to have $x\equiv -y\pmod{p^2}$ for all $x$ and $y$ such that $p^2$ divides both $x^2+1$ and $y^2+1$, streamlining all such $x$ and $y$ into two conjugacy classes modulo $p^2.$ Since our set $\{1,2,\cdots,p^2\}$ contains exactly one element for each residue class modulo $p^2$, we deduce that there are at most $2$ elements $n\in\{1,2,\cdots,p^2\}$ such that $p^2\mid n^2+1$ for some $p.$ Thus, for any positive integer $m$, there are at most $2\left\lceil\frac{m}{p^2}\right\rceil$ elements $n$ such that $p^2\mid n^2+1.$ We can sum over all primes $3\le p\le m$ to obtain the total number of nonsquarefree $n$ in the set $\{1,2,\cdots,m\}$; note that the $3\le p$ is due to the fact that $2^2\nmid n^2+1$, as $n^2$ is either $0$ or $1$ modulo $4$, so that $n^2+1$ is either $1$ or $2$ modulo $4.$ Then, letting $a_m$ be the number of such $m$, we find that \begin{align*} a_m&\le\sum_{3\le p\le m}2\left\lceil\frac{m}{p^2}\right\rceil\\ &\le\sum_{3\le p\le m}\left(\frac{2m}{p^2}+2\right)\\ &2m\sum_{3\le p\le m}\frac{1}{p^2}+2\sum_{3\le p\le m}1. \end{align*}Noting that the summation $\sum_{3\le p\le m}1$ is exactly one less than the prime-counting function $\pi(m)$, we get \begin{align*} \frac{a_m}m&\le\frac{2m\sum_{3\le p\le m}\frac{1}{p^2}+2\sum_{3\le p\le m}1}m\\ &\le2\sum_{i=3}^\infty\frac{1}{i^2}+\frac{2\pi(m)}m. \end{align*}Using the fact that $\sum_{i=1}^\infty\frac{1}{i^2}=\frac{\pi^2}6$ and also that $\frac{\pi(m)}m\le\frac{6\log2}{\log m},$ due to a bound established by Erdos, we obtain that \begin{align*} \frac{a_m}m&\le2\left(\frac{\pi^2}6-1-\frac14\right)+2\left(\frac{6\log2}{\log m}\right)\\ &=\frac{\pi^2}3-\frac52+\frac{12\log2}{\log m}\\ &\le\frac45+\frac{12\log2}{\log m}. \end{align*}One can check that $\frac{\pi^2}3-\frac52<\frac45.$ Note that $\log m$ is increasing, so $\frac{a_m}m$ decreases as $m$ increases. Specifically, if we set $m=2^k$, then \begin{align*} \frac{a_m}{m}&\le\frac45+\frac{12\log2}{\log(2^k)}\\ &=\frac45+\frac{12}k. \end{align*}Fore $k>120,$ we have that \begin{align*} \frac{a_m}{m}&<\frac45+\frac{12}{120}\\ &=\frac{9}{10}. \end{align*}In other words, if $m>2^{120},$ then at least ten percent of the elements $n$ of $\{1,2,\cdots,m\}$ are such that $n^2+1$ is squarefree. This clearly implies that there are infinitely many integers $n$ such that $n^2+1$ is squarefree, as desired. $\blacksquare$

I think it is China TST 2015.

Sourorange wrote: I think it is China TST 2015. But the problems haven't been posted on AoPS.

This is a very weak form of Landau's fourth problem. Interestingly, the problem directly follows from Iwaniec's result that there are infinitely many numbers of the form $n^2+1$ which are either prime or semiprime.

Here's a solution with rather abysmal bounding. Consider the density of squarefrees in $\{1^2 + 1, 2^2 + 1, \dots, n^2 + 1\}$. There are $\frac{1}{2} (1 + o(1)) \frac{n}{\ln(n)}$ primes at most $n$ that are $1 \pmod{4}$, for each of which there are at most $2$ residues that square to $-1$. As such, there are at least \begin{align*} &n - \sum_{p \in P} \left\lfloor \frac{2n}{p}\right\rfloor = n - \sum_{p \in P} \frac{2n}{p} + O\left(\frac{n}{\log(n)}\right) \\ &= n - 2n \cdot \left(\frac{1}{2} \log \log n + O(1) \right) + O\left(\frac{n}{\log(n)}\right) \\ &= n - n \cdot \left(\log \log n + C \right) + O\left(\frac{n}{\log(n)}\right) = O(n) \\ \end{align*}for some $C$ less than Merten's constant.

Notice that the number of $n$ s.t.$p^2 \mid n^2+1$ are at most $\sum_{p \leq n} 2 \left\lceil \frac{n}{p^2} \right\rceil \leq \sum_{p \leq n} 2\left(\frac{n}{p^2}+1\right) =2n \sum_{p \leq n}\frac{1}{p^2} + \mathcal{O}\left(\frac{n}{\log{n}}\right)$ so the density of non square free numbers is at most $2 \sum_{p \leq n} \frac{1}{p^2} < 1$ where we use the fact $\sum_{\text{p prime}} \frac{1}{p^2} < \frac{1}{2}$, and therefore the number of numbers such that $n^2+1$ is square-free has positive density.

By Fermat's Christmas Theorem, all primes $p$ dividing $n^2 + 1$ must be $\equiv 1\pmod{4}$. Note that we can ignore $p = 2$ because it will always be true that $\nu_2(n^2 + 1) \leq 1$. Note that $n^2 \equiv -1\pmod{p^2}$ has at most $2$ solutions. This can be proven easily by taking a primitive root $g$ modulo $p^2$(which exists) and letting $n = g^k$. Then the total number of non-squarefree numbers below some arbitrarily large integer $N$ is $\leq$ \[N \cdot \sum_{p = 4k+1} \frac{2}{p^2} \leq 1\]so there are infinitely many squarefree numbers as desired.

That is easy, say an "O" in the diagram below is a square inch O = square OO OO = another square OOO OOO OOO = another square OOOO OOOO OOOO OOOO = yet another square and so on, each is more than one "O" bigger than the previous one (I know my answer is not very good, but I am only doing prealgebra)

Fix large $N$. We will count number of ''bad" $n$ among $\{1,2,\dots,N\}$ (basically when $p^2 \mid n^2+1$ for some prime $p$). See that this number is upperbounded by \[\sum_{p \text{ prime }} 2 \left \lceil \frac{N}{p^2} \right \rceil \leq \sum_{p \text{ prime}} 2 \left(\frac{N}{p^2}+1 \right) \leq 2 \cdot \sum_{p \text{ prime}} \frac{N}{p^2}+O \left(\frac{N}{\log N} \right) < 0.99N\]for large enough $N$ because we are using the well known fact that $\sum_{p \text{ prime}} \frac1{p^2}<\frac12$. $\blacksquare$ Remark: See that in the proof we never used the fact that $p^2 \mid n^2+1 \implies p \not \equiv 3 \pmod 4$ and so we only had ''half" as good as an estimate but it still works.