# Can I prove n^2 - n + 1 prime for all even n? [duplicate]

I was playing around with numbers the other day and realized that the first few values for $$n(n - 1) + 1$$ are prime. Now, I also quickly realized that not all values are prime ($$n = 5$$ results in 21, which is not prime), but I also noticed that all of the values for which the formula doesn't result in a prime are odd. I wrote up a quick python script, and since checking $$n < 100,000,000$$ hasn't provided an even counterexample, I was wondering if I could somehow prove or disprove the hypothesis that, for all even $$n$$, $$n^2 - n + 1$$ is prime.

I am aware of Goldbach's proof (mention of it) that for any polynomial, not all of its outputs can be prime, but I don't think that applies if the input is restricted to to just even integers.

Python 3.6.7 code I used:

from math import sqrt
from itertools import count, islice

n=0
m=100000000
q=0
p=1
j=0

for n in islice(count(1), m):
if (n % 2):
p = 0
else:
q = n * (n - 1) + 1
p = n > 1 and all(n % j for j in islice(count(2), int(sqrt(n) + 1)))
if (p): print(n, p)



Link to source of method of checking primality.

## marked as duplicate by Bill Dubuque prime-numbers StackExchange.ready(function() { if (StackExchange.options.isMobile) return; $('.dupe-hammer-message-hover:not(.hover-bound)').each(function() { var$hover = $(this).addClass('hover-bound'),$msg = $hover.siblings('.dupe-hammer-message');$hover.hover( function() { $hover.showInfoMessage('', { messageElement:$msg.clone().show(), transient: false, position: { my: 'bottom left', at: 'top center', offsetTop: -7 }, dismissable: false, relativeToBody: true }); }, function() { StackExchange.helpers.removeMessages(); } ); }); }); May 13 at 20:44

• $n=10?{{{{}}}}$ – Lord Shark the Unknown May 13 at 20:37
• Goldbach's proof applies to $f(2n)$ too. – Bill Dubuque May 13 at 20:40
• Or $n=8$. $\quad$ – lulu May 13 at 20:40
• checking wether an integer is prime by using float point arithmetic is a bit risky – Adren May 13 at 20:40
• If $p(n)$ is a polynomial with prime values at all the even integers then $q(n)=p(2n)$ is prime for all integers. – lulu May 13 at 20:42

This is not true. A simple search in Python gives counterexamples of $$n=8, 10, 12, 14, 20, 24, 26, 30, 32, 36, 38, 40, 44, 46, 48, 50, 52, 54, 56, 62, 64, 66, 68,\dots$$ which have corresponding composite values of $$n^2-n+1=3\cdot19, 7\cdot13, 7\cdot19, 3\cdot61, 3\cdot127, 7\cdot79, 3\cdot7\cdot31, 13\cdot67, 3\cdot331, 13\cdot97, \dots$$

Here is the code I used by the way:

#Returns a list of all primes less than or equal to Max
def ListPrimes(Max):
if Max <= 1:
return []
Primes = [True for i in range(Max+1)]

for PrimeIndex in range(2, Max+1):
if (Primes[PrimeIndex] == True):
Primes[PrimeIndex]=PrimeIndex
PrimeIndex2 = PrimeIndex * 2
while(PrimeIndex2 <= Max):
Primes[PrimeIndex2] = False
PrimeIndex2 += PrimeIndex
return [p for p in Primes if p!= False][2:]

print([i for i in range(2,100,2) if not ((i*i-i+1) in ListPrimes(10000))])

• Thanks, I was wondering if I was missing something. – IronEagle May 14 at 14:42