Do Prime Numbers Follow a Pattern?

[Raschedian]

Hello everyone!

I was going through a simple high school level mathematics book and got to the following question:

n² - n + 41 is a prime for all positive integers n.

You're supposed to find a counter-example and prove the statement false.

You could of course sit and enter different values for n until you get a composite number and then use that value of n as the counter-example.

But is there a way to find some pattern or rule for prime or composite numbers so that you don't have to do the work manually? This is probably a trivial question but I got curious. Thank you!

 

[phyzguy]

There is no known pattern or rule for calculating prime numbers, but with a little thought you should be able to easily find a counter-example without laboriously going through numbers.

 

[Raschedian]

There is no known pattern or rule for calculating prime numbers, but with a little thought you should be able to easily find a counter-example without laboriously going through numbers.

Thank you!

 

[Mark44]

I was going through a simple high school level mathematics book and got to the following question:

n² - n + 41 is a prime for all positive integers n.

You're supposed to find a counter-example and prove the statement false.

It's pretty easy to find a counterexample for the formula above, if you think about it. A similar formula is the following: n² + n + 41. This one also appears to generate prime numbers. It's a little harder than the first formula to spot why not all of its values are primes.

 

[fbs7]

Uh? Simple proof? Hmm... how come... hmmm... hmmmmm...

Spoiler

Ah! It's the same reason why $n^2-n+11$ also doesn't generate prime numbers! Haha, smart problem!

 

[phyzguy]

Try writing it as n(n-1) + 41. Is there a vale of n that makes it obvious this is not prime?

 

[fresh_42]

I have once checked one of the polynomials up to $n=100$ and there are indeed disproportionately many primes as results. Does anyone know why? I mean in terms of Legendre symbols or so?

 

[fbs7]

Try writing it as n(n-1) + 41. Is there a vale of n that makes it obvious this is not prime?

The way I thought of this was rewriting as $n^2 + (41-n)$

 

[Mark44]

The way I thought of this was rewriting as $n^2 + (41-n)$

Yes, that's probably the most straightforward way.

 

[DrClaude]

The way I thought of this was rewriting as $n^2 + (41-n)$

That's what I thought also, but @phyzguy's approach allowed me to see the solution to

A similar formula is the following: n² + n + 41. This one also appears to generate prime numbers. It's a little harder than the first formula to spot why not all of its values are primes.

 

[fbs7]

Hmm... I'm kinda missing the $n*(n-1)+41$... how does that make it non-prime... hmm... 21*20?... 11*10?...hmm... can't be that... 41*40?... oh.. .41*40+41! hahaha... I got it! ... I'm so slow

It's actually the same thing as $n*(n+1)+41$, I guess!

 

[Mark44]

Hmm... I'm kinda missing the $n*(n-1)+41$... how does that make it non-prime... hmm... 21*20?... 11*10?...hmm... can't be that... 41*40?... oh.. .41*40+41! hahaha... I got it! ... I'm so slow

It's actually the same thing as $n*(n+1)+41$, I guess!

Well, maybe.
As a hint, consider that $n^2 + n + 41 = n^2 + n + 40 + 1$, where the latter expression can be written as a perfect square trinomial for some value of n.

 

[AdamF]

10.

(Didn't read the other comments.)

 

[Mark44]

10.

?

(Didn't read the other comments.)

 

[fresh_42]

?

Yes, a commentary which reminds me not to write what I think.

10.

(Didn't read the other comments.)

Maybe someone should tell him that $10^2\pm 10+41$ are both prime.

 

[AdamF]

I read it as "n^2 - n - 41".

-- The way it's written is more immediate, though.

Reduce the last two terms to zero by setting n equal to the quantity you're subtracting.
In this case, take:
N = 41

 

[alan2]

Just let n=41.

 

[WWGD]

It seems worthwhile checking to see, for a more general expression if you can find a way , a value , to make the expression be even or end in 5, as the simplest cases. Here , if n is odd, the sum is odd, same for ifn is even. Five will not work. Just mentioning as a general technique. Usually going by using the remainder of a well-chosen number should help.

 

[TeethWhitener]

I have once checked one of the polynomials up to $n=100$ and there are indeed disproportionately many primes as results. Does anyone know why? I mean in terms of Legendre symbols or so?

Mathworld:
http://mathworld.wolfram.com/LuckyNumberofEuler.html
has an explanation in terms of Heegner numbers, but I'm not nearly smart enough to understand it

 

[Janosh89]

Nor me!
$\rm The~core~equation~for~~~$x²+x+41
$\rm~~~~~~~~~~~~~~~is~~~~~~~~~~~~~~~~$x²+163
this will be divisible by 163 at n=81
of course, at n=40 , i.e. 40 x 41 [x1]
$~~~~~~~~~~~~$ and n=41$~~~~~~~$ 41 x 42 $~~ "$
the first composites ( of 41) are produced at and then below the square root of the function ( of x)

 

[Mark44]

Nor me!
$\rm The~core~equation~for~~~$x²+x+41
$\rm~~~~~~~~~~~~~~~is~~~~~~~~~~~~~~~~$x²+163

What is a "core equation" and why is $x^2 + 163$ a core equation for $x^2 + x + 41$? Also note that neither $x^2 + x + 41$ nor $x^2 + 163$ is an equation.

this will be divisible by 163 at n=81

What will be divisible by 163? Without some elaboration, it would be difficult to see that $81^2 + 163 = 81^2 + 2(81) + 1 = (81 + 1)^2$, but what does this have to do with $x^2 + x + 41$?

of course, at n=40 , i.e. 40 x 41 [x1]
$~~~~~~~~~~~~$ and n=41$~~~~~~~$ 41 x 42 $~~ "$
the first composites ( of 41) are produced at and then below the square root of the function ( of x)

The square root of what?
Please try to be clearer in your replies.

 

[Janosh89]

I will post, y=x²+163 in future
$81^2+81+41=163×41$
$y=x^2+x+41$
$∴y=163×41~ when~x=81$

 

[HallsofIvy]

alan2, back in post 17 gave the obvious answer: "let x= 41"! If x= 41, $$x^2+ x+ 41= (41)^2+ 41+ 41= 41(4`1+ 41+ 41)= 41(123)$$.

 

[Janosh89]

Yes , it was explicit.