3
$\begingroup$

From my NT class, someone has thought of proving $x^4+1$ is always a prime number for all positive integers $x$ (or at least that is the equivalent of what they said).
However, it is clearly false for $x$ is odd. For $x$ is even seems like always a prime, however. Does anyone have an idea on how to prove/disprove this?
I first disbelieved it since, well, I thought primes don't follow a pattern.
However, I tried the first few numbers $x=1,2,3$ and got $2,17,82$ (which made me think of the less stronger statement that all evens produce primes).
In other words, is there a proof for $16a^4+1$ is always prime for all $a$?

$\endgroup$
  • 5
    $\begingroup$ There is no nonconstant polynomial $p$ with integer coefficients so that $p(m)$ is prime for every integer $m$. The closest that you can get is a polynomial $q(m_1, \ldots, m_k)$ with some number of integer variables, and integer coefficients, so that the range of $q$ intersected with $\mathbb{N}$ is exactly the set of primes - this follows from work on Hilbert's 10th problem. $\endgroup$ – Carl Mummert Aug 16 '18 at 2:54
  • 4
    $\begingroup$ "However, I tried the first few numbers x=1,2,3 and got 2,17,82 (which made me think of the less stronger statement that all evens produce primes)" You thought of that on the basis of only ONEvalue, x=2????? Having only one example where $2^4+1$ is prime. One example is nowhere near enough to make such absurd general speculations! $\endgroup$ – fleablood Aug 16 '18 at 6:11
7
$\begingroup$

No. Consider $8^4+1=4097=17\cdot 241.$

For a case where you have $16a^4+1$ with $a$ odd, take $10^4+1=73 \cdot 137$.


In fact, you can always rule out such occurrences.

$\endgroup$
3
$\begingroup$

Ahh, you should have tried more. If $f(x)=16x^4+1$, then it is not prime for $x=4,5,6,7,9$ and so on. A list of such numbers can be obtained in milliseconds by a computer.

$\endgroup$
3
$\begingroup$

I think that if there really was a simple arithmetical formula that gave infinitely many primes, even if not all of them, it would have been discovered in the past two hundred years, if not earlier.

Any time you think you have found such a formula, your first instinct should be to go to one of two places: FactorDB or the OEIS.

FactorDB understands one variable and the four basic arithmetic operations, and exponents, too. I put in the query n^4 + 1 (you don't have to use spaces), but the results were not so useful because, as you've already found, only one odd value of $n$ gives a prime.

So next I tried 16n^4 + 1 but then remembered FactorDB doesn't quite understand tacit multiplication. Okay, then 16 * n^4 + 1, the results for that query make it quite clear that a lot of these numbers are divisible by 17.

It is a very attractive formula because these numbers are obviously not divisible by 3 or 5. They are not divisible by 7, 11 or 13 either.

Given an integer $n$ not divisible by 3, we have $n^4 \equiv 1 \pmod 3$, and therefore $16n^4 + 1 \equiv 2 \pmod 3$. Similarly with 5, $n^4 \equiv 1 \pmod 5$, and therefore $16n^4 + 1 \equiv 2 \pmod 5$.

It gets a little more interesting for 7. The squares modulo 7 are 0, 1, 4, 2, so the biquadrates are 0, 1, 2, 4, and since $16 \equiv 2 \pmod 7$, we have $16n^4 + 1$ as one of 1, 2, 3, 5. Similar things happen with 11 and 13.

As you can see from the FactorDB listing (you can increase it to 200 per page), a lot of these number are divisible by 17 according to a fairly regular pattern.

It looks like $n \equiv 1, 4, 13, 16 \pmod{17}$ means that $16n^4 + 1$ is a multiple of 17.

If you still think there could be a simple pattern to which of these numbers is prime, put the query to the OEIS. I tried 1, 2, 3, 8, 10, 14 and it gave me A100317, numbers $n$ such that exactly one of $n - 1$ and $n + 1$ is prime.

Hmm... it could be relevant, though I don't quite see how at the moment. I tried adding 17 and 23 to my query and got no results. A rare strikeout for the OEIS.


Lastly, for what it's worth, $(x^2 - i)(x^2 + i) = x^4 + 1$, where $i$ is the imaginary unit.

$\endgroup$
2
$\begingroup$

One can make infinite families that don't produce primes; $$ (17n+2)^4 + 1 $$ is always divisible by $17,$ but as soon as $n \geq 1$ the result is larger than $17$ and not prime. Also $$ (17n+8)^4 + 1 , $$ $$ (17n+9)^4 + 1 , $$ $$ (17n+15)^4 + 1 . $$

===============================================================

Similar outcome for divisibility by $41$ and $$ (41n+3)^4 + 1 , $$ $$ (41n+14)^4 + 1 , $$ $$ (41n+27)^4 + 1 , $$ $$ (41n+38)^4 + 1 . $$

===============================================================

Similar outcome for divisibility by $73$ and $$ (73n+10)^4 + 1 , $$ $$ (73n+22)^4 + 1 , $$ $$ (73n+51)^4 + 1 , $$ $$ (73n+63)^4 + 1 . $$

Any prime $p \equiv 1 \pmod 8$ has four fourth roots of $-1.$

$\endgroup$
1
$\begingroup$

The smallest counterexample is $a = 4$, or $x = 8$, yielding $4097 = 17 \cdot 241$. There are many small counterexamples as shown by the table below: $$\begin{array}{c|l} a & 16a^4 + 1 \\ \hline 4 & 4097 = 17 \cdot 241 \\ 5 & 10001 = 73 \cdot 137 \\ 6 & 20737 = 89 \cdot 233 \\ 7 & 38417 = 41 \cdot 937 \\ 9 & 104977 = 113 \cdot 929 \\ 11 & 234257 = 73 \cdot 3209 \\ 13 & 456977 = 17 \cdot 26881 \\ \end{array}$$

For the first $10000$ such $a$, $8535$ do not yield a prime, and $1465$ do.

For the first $10^5$ such $a$, $88050$ do not yield a prime, and $11950$ do. This seems to suggest the density of primes decreases with increasing $a$.

$\endgroup$
1
$\begingroup$

If $x\not=0$ is even and $p\mid x^4+1$, then $p\mid(x+2p)^4+1\gt p$, so even if $x^4+1$ is prime, $(x+2p)^4+1$ will not be prime.

This argument can be fairly easily modified to show that no polynomial (with integer coefficients and, of course, of positive degree) is prime for all integer values of $x$.

$\endgroup$
1
$\begingroup$

$x^{4}+1$ is prime for all even $x$ iff $16x^{4}+1$ is prime for all $x$ (except where $x=0$) iff $16(x+1)^{4}+1$ is prime for all $x \in \left \{ 0, 1, 2... \right \}$. This cannot be by the theorem outlined in the question below:

Prove that there is no polynomial $P(x) = a_n x^n + a_{n-1} x^{n-1} + \ldots + a_0 $

(This same reasoning will tend to work whether $x_{n}$ is a multiple of $2$, $3$... Or even if $x_{n}=P(n)$, $P$ a polynomial. i.e. the non-existence of a polynomial prime generating function is not limited to the case of $x$ being a multiple of $2$.)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.