# Diophantine Equation & Primes

Standard

I stumbled upon following statement on some webpage (don’t have link):

There exist infinitely many integers $n$ such that $n^2 +1$ divides $n!$.

I tried proving it, though not able to prove it but here are my insights:

• Proof by contradiction (the way we show infinite primes) doesn’t work here.
• I need to prove that $\frac{n!}{n^2+1} = k \in \mathbb{N}$ for infinitely many values of $n$, so I should try to express $n^2+1$ in product form (since numerator is already in product form). After writing denominator in product form,  find a condition satisfied by infinitely many values of $n$, which generates infinitely many natural numbers as outcomes of $\frac{n!}{n^2+1}$.

First idea that came to my mind, for factoring the denominator was in terms Gaussian Integers (numbers of form $a+ib$ where $a,b$ are integers and $i = \sqrt{-1}$), but I am not able to proceed in this direction further.

Second idea to generate factors of denominator was to analyze Diophantine equation (i.e. we are concerned with only integer solutions of given equation), of form: $x^2 + 1 = Dy^2$

Here is a theorem from Diophantine equation, which can help me generate factors:

Lemma: Let $p$ be a prime. The diophantine equation: $x^2 - py^2 = -1$ is solvable if and only if $p=2$ or $p\equiv 1 \pmod 4$

Proof: If the considered equation has a solution $(x,y)$, then $p| x^2+1$. Hence either  $p=2$ or  $p \equiv 1 \pmod 4$.

For $p=2$$x=y=1$ is a solution.

We show that there is a solution for each prime $p=4t+1$. Let us study the existence of an integral solution $(x_0,y_0)$ to the wee known diophantine equation: $x_0^2 - py_0^2 = 1$.

Observe that $x_0$ is odd [otherwise, $y_0^2 \equiv py_0^2 \equiv 3 \pmod 4$, but no square leaves a remainder 3 when divided by 4]. Thus in the relation:

$x_0^2 - 1 = (x_0-1)(x_0+1) = py_0^2$

factors $x_0+1$ and $x_0-1$ have greatest common divisor 2, and consequently one of them is a doubled square (to be denoted by $2x^2$) and the other one $2p$ times a square (to be denoted by $2py^2$).

The case $x_0+1 = 2x^2$ and $x_0-1 = 2py^2$ is impossible because it leads to a smaller solution of diophantine equation: $x^2-py^2=1$. [method of infinite descent]

It follows that $x_0-1=2x^2$ , and $x_0+1 = 2py^2$, therefore $x^2-py^2 = -1$

——

Now we return back to main statement.

——

Let $n^2+1 = pm^2$, where $m \in \mathbb{N}$ and $p$ is a prime of  form $p=2$ or $p \equiv1 \pmod 4$.

Now let us consider another result:

Lemma: There are infinitely number of primes of the form $4n+1$.

ProofSuppose $n>1$ is an integer. Let $p$ be the smallest prime divisor of $N$.

We define $N=(n!)^2 +1$.

Since $N$ is odd, $p$ cannot be equal to $2$. It is clear that $p$ is bigger than $n$ (otherwise $p \mid 1$ ).

We know that $p$ has the form $4k+1$ or $4k+3$. Since $p\mid N$ we have:

$(n!)^2 \equiv -1 \pmod p \$

$\Rightarrow (n!)^{p-1} \equiv (-1)^{ \frac{p-1}{2} } \pmod p$.

Using Fermat’s little Theorem we get $(-1)^{ \frac{p-1}{2} } \equiv 1 \pmod p$.

If $p$ was of the form $4k+3$ then $\frac{p-1}{2} =2k+1$ is odd and therefore we obtain $-1 \equiv 1 \pmod p$ or $p \mid 2$ which is a contradiction since $p$ is odd.

Hence, $p$ is of the form $4k+1$, now we can repeat the procedure replacing $n$ with $p$ and produce an infinite sequence of primes of the form $4k+1$.

——

From above lemma, we can say that, $n^2+1 = pm^2$ for infinitely many values of $p$

I have expressed denominator in product form, what remains to prove is that the expression $\frac{n!}{pm^2}$  simplifies to give a natural number as answer.

Now this appears to me as a dead end.

If you discover/know the proof of starting statement please give its outline in comments.

But, the motive of this post is to show the beautiful flowers I observed while searching for a path which leads to given statement.

### 4 responses

1. Pingback: Hello 2017 | Gaurish4Math

2. Pingback: Numbers and Logic | Gaurish4Math