# Systematic approach to proofs involving prime numbers

I've been reading through a textbook that contains some problems involving prime numbers, like these:

1) Prove or disprove: $2^n + 1$ is prime for all nonnegative integer $n$.

2) Show that for any integer $n$ greater or equal to $5$, the integers $n$, $n + 2$ and $n + 4$ cannot be all primes.

I wonder what's the approach here to tackle these problems. For example, when working with proofs that involve odd/even numbers, those can be represented as $2k$ or $2k + 1$ and I can work with that to create an equation and demonstrate the proof.

How to approach problems like the quoted ones? I mean, the first one I can do in my head, the second one is a bit harder and I wouldn't know where to start.

For the first one (and problem stated this way), you usually just have to find a counter-example.

For the second one, you can explicitly make the computation:

$$N=n+(n+2)+(n+4)=3n+6=3(n+2).$$

So if $n\ge 5$, then $3\mid N$, therefore, $N$ can not be a prime number.

There is no systematic approach to problems dealing with prime numbers though.

• I accept this answer as it is the most pragmatic one and helped me to understand that I need to gain more experience in number theory. – Max Jun 30 '17 at 8:05

The first question. I'm sure most users on here pretty experienced with mathematics and specifically number theory knew right away that you should disprove the claim, i.e. it is false. The reason we strongly believe it is false is that if it were true, it would give a lot of structure to primes. A general rule of thumb is that the primes lack any easy structure to find. In particular, there is no known way to generate prime numbers (the first question would give a way to do so if it were true).

The second question. When asked to prove that something is not prime, you must of course show that something divides it. For more elementary questions, this is usually not too challenging. For this example, you can show that $$3$$ must divide one of the numbers. But all similar problems basically come down to finding a specific divisor (which is usually small).

• Thank you for your anser, it gives me good food for thought. – Max Jun 30 '17 at 8:04
1. Take a look at $n=3$.
2. Take a look at the remainder of $n, n+2$ and $n+4$ when divided by $3$.

HINT:

For the first, see If $2^n+1$ is prime, why must $n$ be a power of $2$?

For the second, $$n(n+2)(n+4)=n(n+2)\{(n+1)+3\}=\underbrace{n(n+1)(n+2)}_{\text{product of three consecutive integers}}+3n(n+1)$$

• What does this answer have to do with the question? The question isn't asking about the product of $n,n+2, n+4$... – 5xum Jun 30 '17 at 7:29
• @5xum, I've shown that $3| n(n+2)(n+4)$ Hence at least(in fact exactly) one of the three multiplicands will be so – lab bhattacharjee Jun 30 '17 at 7:30
• Thank you for your answer, it gives me good pointers on how to learn more and proceed. – Max Jun 30 '17 at 8:05

Multiple methods are possible. You can even have a certain "style".

1) has some good examples above, structure of the prime implied is really good. Finding a counter example in your head, another good approach.

2) As mentioned elsewhere, if you want to prove something isn't prime, you want to find something that divides it. If you are given a list of integers, you often want to look at its remainders with respect to some other integer.

Putting together a toolbox of Rules of Thumb is very helpful in such problems.

One Rule of thumb, every prime over 5 is one less or more than a multiple of 6. If you can prove that one of n,n+2, or n+4 is not one more or less than a multiple of 6, then you are done. You can go in order for that. n has to be one less than or more than a multiple of six are the triple wont work, n is composite. If it's one less than a multiple of 6, then adding 4 will make it 3 plus a multiple of 6, so n+4 will be divisible by 3. If it's one more than a multiple of 6, then n+2 will be divisible by 3.

5xum's answer is nice. Every number is either a multiple of 3, or one more or less than a multiple of 3. If n is a a multiple of 3, the theorem is proved. If n is one less than a multiple of 3 then n=3k-1 for some integer k. Then n+4=3(k+1). So you get a multiple of 3. If n is one more than a multiple of 3, then n=3k+1 for some integer k. So n+2=3(k+1). So no matter what your n, one of n, n+2, and n+4 is divisible by 3 and therefor not prime.

You can take a similar approach here: How do you know that n(n+1)(2n+1) is always divisible by 6? Well, if n is even then the product is too. If n is odd, then n+1 must be even, and so is the product. So we know our product is divisible by 2. Now can you see how n(n+1)(n+2) must be divisible by 3? Let's suppose neither n or n+1 is divisible by 3. Then n+2 is. Then so is 2n+4. Take 3 away and you have 2n+1. Three less than a multiple of three must be a multiple of 3, so 2n+1 is divisible by 3. The product is divisible by 2 and 3, so it must be divisible by 6.

Rules of thumb help develop intuition, a very important quality in a mathematician. For example out of n,n+2, and n+4. Suppose n and n+2 are both prime. This happens, the pairs when this happens are called Twin Primes. No one knows if there are an infinite number of Twin Primes. You never hear of triplet primes. Is that just a coincidence? Intuition probably tells you no and indicates an opportunity to explore the issue.

I had a math teacher in high school. He said "If you don't know 5 ways of solving a problem then you didn't understand it well enough." There's no wrong way to prove a theorem. You can get very creative with it. Mathematics offers much more latitude than many would have you believe.

Keep working problems. Keep being curious. Develop intuition by building that tool box. Follow your curiosity. Figure out ways to tweak your problems so that the techniques you have used before no longer apply.