Prime Numbers

Number Theory Level 4

What is the smallest value of $n$ for which $n^2+n+41$ is not a prime number ?

Note: $n$ is a non-negative number.

The answer is 40.

1 solution

A Former Brilliant Member
Jun 18, 2017

The expression $n^2+n+41$ does generate prime numbers for every natural number $n$ from $1$ to $39$ . However, since $n^2+n=n(n+1)$ , it cannot be the case that $n^2+n+41$ is prime when $n+1=41$ ; that is, when $\boxed{n=40}$ because, then, we have $40(41)+41=41^2$ , divisible by $41$ .

Hmmm but this isnt the complete solution.

Guess why?

Md Zuhair - 3 years, 11 months ago

Yeah, he proved that 40 does produce a prime number. Although, he did not prove that 40 in the smallest value. Of course you could check in a program to see if numbers 1-39 produce a prime number but meh.. I'd like an algebraic solution.

maximos stratis - 3 years, 11 months ago

Yes, this is a cop-out solution. It basically says "The first 39 positive integers are not a solution, but 40 is a solution. I'm not gonna explain why the former is true though"

This question can be (properly) solved using quadratic residues , which is the most elementary approach, but not the most elegant approach. A better approach is via quadratic fields.

Relevant article: Prime-Generating Polynomial .

Pi Han Goh - 3 years, 11 months ago

It should probably be stated that n represents a non-negative number.

This could be deduced from the problem, otherwise there are infinitely many solutions for n<0, and therefore no smallest, but it adds clarity.

Fun problem!

Steven Perkins - 3 years, 11 months ago

Prime Numbers

The answer is 40.

1 solution

0 pending reports