Prime Generating Function

Number Theory Level 4

Find the smallest positive integer $n$ for which the function $f(n)=n^2+n+41$ is composite.

The answer is 40.

2 solutions

Chew-Seong Cheong
May 18, 2015

Since $41$ is a prime, for $f(n) = n^2+n+41$ to be a composite, $n^2 + n = n(n+1)$ must be divisible by $41$ . As $41$ is a prime, it cannot be a multiple of any $n<41$ , therefore, $n(n+1)$ is not a multiple of $41$ for $n<40$ . Therefore, the smallest $n$ that satisfies the condition is $n = \boxed{40}$ .

Moderator note:

Not quite right. You have only shown that $n=40$ is possible, you didn't show that it is a minimum value.

In response to the Challenge Master: Proving that $n = 40$ is the least integer is surprisingly difficult, as demonstrated here . It would probably be easier to just brute force our way through the numbers $1$ to $39.$ :)

Brian Charlesworth - 6 years ago

Why does 41 being prime imply that n^2+n must be divisible by 41 for n^2+n+41=f(n) to be composite? This is only true if we specify that f(n) is divisible by 41. For example, 3 is prime and 5 is not divisible by 3, but 5+3 is composite.

Maggie Miller - 5 years, 11 months ago

Because $41$ is a prime and $n$ an integer, we have no way of factorize $f(n) = n^2 + n + 41$ . For your example, you cannot get $n^2+n = 5$ or $3$ . For example, $n^2+n+3\quad \Rightarrow n_{min} = 2$ and $n^2+n+5\quad \Rightarrow n_{min} = 4$ . This actually generalizes it. $f(n) = n^2 + n + p \quad \Rightarrow n_{min} = p-1$ .

Chew-Seong Cheong - 5 years, 11 months ago

I don't see anything wrong. Since $41$ is a prime and $n$ is an integer, we cannot factorize $f(n)=n^2+n+41$ . So $f(n)$ is a composite if and only if $n(n+1)$ is divisible by $41$ . It is impossible to have an $n<41$ which divides $41$ because $41$ is a prime. Therefore $(n+1)=41$ must be smallest divisor of $41$ for $n<41$ and $n=40$ .

Chew-Seong Cheong - 5 years, 11 months ago

This result was founded by Euclid that in $n^2 + n + 41$ is prime from n = 0 to 39. So minimum is 40.

Dev Sharma - 5 years, 9 months ago

Giovanni Cozzolongo
Jul 18, 2017

Let's see what happens with small prime numbers: for $n^2+n+2$ we have $n=1$ , for $n^2+n+3$ we have $n=2$ , for $n^2+n+5$ we have $n=4$ , for $n^2+n+7$ we have $n=6$ , etc. It seems to be $40$ . Let's check this potential solution: $f(40)=1681=41^2$ , then it is composite. But now we should show that it is the minimum value or just brute force through the numbers.

Prime Generating Function

The answer is 40.

2 solutions

Moderator note:

0 pending reports