2

how to prove this:

$$ \text{if } n! + n^2 + 1 \text{ is prime then } n^2 + 1 \text { is also prime}$$

I was thinking that n! is definitely not prime since it can be written as $n\times (n-1)....2\times 1$. So $n^2 + 1$ is not prime. In other words, n! does not have the same factor as $n^2 + 1$, and I don't know how to prove the following.

user577215664
  • 40,625
Zhenqing Xu
  • 201
  • 4
    Suppose it is not. Then $n^2 + 1$ has a factor that is less than or equal to $n.$ But, if such a factor existed it would also divide $n!$ hence $n! + n^2 + 1$ could not be prime. – Doug M Jan 22 '18 at 18:56
  • Suppose that $n!+n^2+1$ is prime. Then in particular $2,3,4,5,\dots,n$ do not divide evenly into $n!+n^2+1$. Clearly, though, each of $2,3,4,5,\dots,n$ divide evenly into $n!$. What does this imply about whether or not any of $2,3,4,\dots,n$ divide evenly into $n^2+1$? What possible candidates for factors of $n^2+1$ exist? – JMoravitz Jan 22 '18 at 18:57
  • "So $n^2+1$ is not prime" $2^2+1=5$ is prime. $4^2+1=17$ is prime. Several other examples exist. – JMoravitz Jan 22 '18 at 18:59

1 Answers1

5

Suppose $n^2+1=uv$ is composite ($u,v$ proper factors).

As $n^2+1$ is not a square (being between $n^2$ and $(n+1)^2=n^2+2n+1$), we have $u\ne v$, and without loss of generality assume $u\lt v$. Then $u\le n$ and, because $u\mid n^2+1$ and $u\mid n!$, we have $u\mid n!+n^2+1$ so $n!+n^2+1$ cannot be prime.