How do I find an integer value for which an expression is non-prime?

Question

I've just begun Robert S. Wolf's, Proof, Logic and Conjecture. At the end of the first chapter there are some exercises to warm you up for the proof techniques he will eventually introduce. I only mention this so that you are aware that I have yet to encounter formal proof techniques.

The first part of the question simply asks you to substitute small values of $n$ into the expression $n^2-n+41$ and to test if these values are prime. I did this for $n=1$ to $12$, and all the values seemed prime. This leads me onto the second part of the question where I am stuck.

I'll paraphrase the question:

(1)(b) Find a positive integer value of $n$ for which the expression $n^2-n+41$ is not a prime number.

---

My attempt

I will decompose the expression $n^2-n+41$ into symbolic and numeric parts i.e. $n^2-n$ and $41$, in order to obtain a better understanding of it.

The symbolic part of the expression $n^2-n$ can be factorised to $n(n-1)$. From this it is apparent that this portion of the expression will only ever return even values, because it will always be of the form where we have an odd number multiplied by an even number. For example: for $n=5$, an odd number, we have $5(5-1)=5(4)=20$; similarly for $n=4$, an even number, we have $4(4-1)=4(3)=12$.

The addition of an odd number and even number returns an odd number, thus the addition of $41$ (an odd number) to $n^2-n$ (an expression which always returns even numbers) will give an odd number for all integer values of $n$.

As $n^2-n+41$ always returns odd numbers, it then stands to reason that if we are to find any non-prime value of this expression it will also be odd.

The only way I could think of doing this was by defining the odd numbers as $2n+1$, (where $2n$ is an even number and $n$ is an integer) and equating this to the expression in the hope that the intersection would return values that are odd and non-prime, however it is not the case that this equivalence returned an integer value of $n$ for which this expression is not prime.

Where have I gone wrong?

Answer 1

How about $n=41$?

In general, if you choose $n$ so that all of the terms in a sum are divisible by the same number, then the whole sum will be divisible by that number.

Edit: My understanding is that your approach was to set $n^2-n+41 = 2n+1$ and look for integer solutions. But this is quite a strong condition: you're saying not just that $n^2-n+41$ is odd, but that it's the particular odd number $2n+1$. This is a quadratic in $n$, so it has at most $2$ solutions - it's not particularly surprising that it doesn't have integer solutions.

But for any integer value of $n$, $n^2-n+41$ is odd. If you just want to express that $n^2-n+41$ is odd, the relevant equation is $n^2 -n +41 = 2k+1$. This equation has exactly one integer solution for every value of $n$: an example is $n = 41$, $k = 840$.

Answer 2

Though $n = 41$ is an obvious solution, your question 1 (b) is really to be able to find for which $n$, the given expression is not prime. (Though it asks 'an integer', we can try to make a generalization to find all integers).

One approach would be to write it as $n^2 - (n - 41)$. If we make $(n - 41)$ a square, then obviously the given expression factorizes.

So $\color{blue}{n = 41, 42, 45, 50, 57}$ and so on are values of $n$ for which the given expression is not prime. I think Alex has answered the rest.

Answer 3

Here is another simple solution.

We want to find some $n$ for which $n^2 - n + 41$ is not prime. Obviously n = $41$ is a trivial solution as pointed by Alex.

For $n = 41k$, where $k \in {\mathbb N}$, the given expression will have $41$ as a factor. This case is not included in my above answer, though it overlaps at some points (where for example $n = 41\cdot42$).

An answer is a place to ask a question, but would be interesting to find all $n$ for which $n^2 - n + 41$ (The Euler Polynomial) is prime.

Answer 4

Standard form: $$\quad n^2-n=41=2k+1 \implies n^2-n+40-2k\quad =\space n^2-n-(2k-40)=0$$

$$n =\frac{-b\pm\sqrt{b^2-4ac}}{2a} =\frac{1\pm\sqrt{1+4(1)(2k-40)}}{2(1)} =\frac{1 + \sqrt{8k-159}}{2}$$

Some of the [infinite?] integer solutions $\space(k,n)\space$ to this are $$(20,1)\quad (21,2)\quad (23,3)\quad (26,4)\quad (30,5)\quad (35,6)\quad (41,7)\quad (48,8)\quad (56,9)\quad (65,10)\cdots $$

But none of the $n$-values are meaningful except that they match the original equation. For instance $\quad f(n)=2k+1=f(1)=2(20)+1=41.\quad$ What we really need is a way to pridict which $n$-values yield composite numbers and this is not it..

By inspection we can see that $\quad 41^2-41+41=41^2.\quad $ and, up to $50,\space$ the composites are

$$F(41)=41^2\quad F(42)=41\cdot 43\quad F(45)= 43\cdot 47\quad f(50)=47\cdot53$$

We can see no pattern here so the only way we can know that $f(n)$ is composite is to let $n$ be any multiple. of $41$.

Answer 5

Look for one.

If you want to find a number with a certain property, and the property is relatively easy to check, it's often a good idea to just try a bunch of numbers, systematically or at random. You might get lucky!

This approach sounds stupid, but it's one of the most powerful techniques in mathematics, and it's led to some really big results.

---

For example, as $p$ varies over the primes, the first few values of $2^p - 1$ are 3, 7, and 31—all primes. People wanted to know if there's a prime $p$ for which $2^p - 1$ is composite, so they looked for one. In 1536, someone named Hudalricus Regius (Ulrich Rieger, in German) succeeded with $p = 11$. Over the next few centuries, some of the greatest mathematicians on Earth—including Pierre de Fermat, Leonhard Euler, and François Lucas—joined a ridiculous-looking parade of people plugging in bigger and bigger primes $p$ and working out whether $2^p - 1$ was prime. Fermat's work, part of a larger quest to learn about perfect numbers, led to a major result: Fermat's little theorem. Lucas's work led to the less fundamental but still fascinating Lucas-Lehmer test, a primality test that works only on numbers of the form $2^p - 1$ (for $p$ prime).

---

Here's another example. The Riemann zeta function has a bunch of predictable zeros (the negative even numbers), and a bunch of wildly unpredictable ones. The first few unpredictable zeros are $$0.5 + i\;14.134\ldots,\quad 0.5 + i\;21.022\ldots,\quad 0.5 + i\;25.010\ldots.$$ People want to know whether there's a zero of the zeta function whose real part isn't 0.5, so they're looking for one. From the 1970s through the 1990s, a mathematician named Andrew Odlyzko used supercomputers to check trillions of zeros. He didn't find any with real parts other than 0.5, but he did find substantial evidence for a conjecture that suggests deep connections between the Riemann zeta function and the math of quantum mechanics.

---

Sophisticated reasoning is sometimes the best way to find a number, but you should never underestimate the power of good old-fashioned looking for it. In your case, a hand search is quite feasible. In a typical modern programming language, a computer search takes minutes to write, and milliseconds to execute. I'm pretty sure it was the first thing Wolf expected you to try.