# How to arrive at infinite primes proof?

I know Euclid's proof of there being infinite number of primes. I want to let my brother (age 15) arrive at that proof by himself. He knows definition of a prime number (number divisible only by 1 and itself).

First when I asked him how many prime numbers are there, he said there must be an infinite number of them. Why? Because it's not possible to know which one is the largest. Why? ... blank.

Then I told him that since larger a number becomes, more numbers are there below it. So chances of a larger number N being divisible by at least one of the N-2 numbers increases as N-2 larges with N. He agreed with this logic.

Then I asked him if he could generate a prime number larger than any two given given primes (and a third constant) using some simple function of them. I was trying to make him arrive at $prime1*prime2 + 1$ formula. I gave him two primes 2 and 5 and asked to think of some examples. He summed them -> 7 is a prime. Then I asked him to use 1 also, he said 251 is a prime. Then he got bored.

What approach can I use to intuitively arrive at the proof?

-
It is not true that the product of two primes plus one is a prime! For example, $3*5+1 =16$, which is not prime. It is also not true that the product of the first $n$ primes plus $1$ is prime. This is a common misconception about Euclid's proof. See mathoverflow.net/questions/11398/… –  Steven Gubkin Jul 25 '14 at 16:50
@StevenGubkin thanks for pointing out the flaw! –  user13107 Jul 25 '14 at 16:53

It might not be possible to get your brother to arrive at the proof himself, no matter how much you scaffold it. ("You can lead a horse to water" and all that.) If he's into maths and appreciates a good proof, you might get the desired enthusiasm by just showing him the proof!

That said, here's an idea. Forget primes for a moment, and think about divisibility. If you multiply several numbers together (where all are greater than 1), and then add 1, is the result divisible by any of them? No. Why not? Because you'll always have that 1 you added as the remainder!

So, the challenge for your brother. You've got "all of the primes". We know that every number greater than 1 is either prime, or is divisible by (a unique list of) primes. But using what we just did, is it possible to make a number that can't be divided by any of our prime numbers?

Euclid's proof: multiply "all of the primes" together and add 1. So either the fundamental theorem of arithmetic is wrong (oh horror!), or our list of "all the primes" must be missing at least one prime number. And since this goes for any finite list that claims to contain "all the primes", there must be infinitely many primes. QED.

(He does know the unique factorisation theorem, right? I'm just checking, because you pretty much need to be aware of it to tackle Euler's proof.)

-

I don't really answer the question but: why do you want your brother to come to the answer right now?

Now, your brother understands that, to prove that the set of prime numbers is infinite, you can assume it is finite. And, from this pool of prime numbers, you can construct a new one that is not in the family. Why don't you let your brother play with that idea for a short time (a couple of days or weeks)? Present the question to him as a challenge and tease him regularly to be sure he keep thinking about it. Except at school or for career-related reasons, there are no deadline in mathematics to solve a problem.

If your brother is genuinely interested by maths, he will probably enjoy this challenge. If he is not, or his motivation gets down, you may motivate him with a reward. A small reward, since you probably don't want him to work for a reward. So, the reward should not be money or gift, but maybe an intellectual reward: explaining about the twin conjecture "You came up with a proof. Great! Do you know about twin primes? Bla bla bla", or a magic trick involving prime numbers,...

Finally, please keep in mind this is not a big deal if he finally does not arrive to the complete proof. Finding a proof is fine, but searching and finally enjoying the beauty of someone else's brillant reasoning is great too! How many people could have came by themself to Cantor's diagonal argument? Isn't it a great proof that most mathematics enthusiasts enjoy?

-
+1 for "why right now?" –  apnorton Jul 26 '14 at 3:26

I think using actual small primes actually detracts from finding the solution. If you are thinking about finding a number that is not divisible by 2,3, or 5, it is easy to come up with one (11) without having to use a formula.

Thus, I would get him thinking about primes more symbolically.

Given 3 primes, $p_1, p_2, p_3$ what is their LCM? What is their GCD?

What are the LCM and GCD of $p_1^2, p_1p_2, p_1p_3$?

What are all the factors of $p_1p_2p_3$? (for this one, you might need to do an example with small primes first, but the idea is for him to eventually "see it" using the variables)

If this all makes sense, then I would say he would be primed (no pun intended) to think about the problem of "can you think of an expression using $p_1, p_2, p_3$ that is guaranteed not to be divisible by any of $p_1, p_2$ or $p_3$?"

That said, I think most of use have to have a number of clever proofs shown to us before we are ready to discover them on our own.

-