11
$\begingroup$

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 $\text{prime}_1 \times \text{prime}_2 + 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?

Improve this question
$\endgroup$
4
  • 18
    $\begingroup$ 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/… $\endgroup$
    – Steven Gubkin
    Commented Jul 25, 2014 at 16:50
  • 1
    $\begingroup$ You should ask Euclid how he came up with it in the first place. Probably no big deal. $\endgroup$
    – Benoît Kloeckner
    Commented Nov 24, 2015 at 14:36
  • $\begingroup$ It's worth noting that this isn't the only natural place to arrive for a proof that there are infinitely many primes. One which seems intuitive to me is that every number is divisible by a prime. $\frac{1}2$ of them are divisible by $2$. Then $\frac{1}3$ of the remaining ones are divisible by $3$. Then $\frac{1}5$ of the remaining ones are divisible by $5$. But we can't exhaust every number by taking a fraction of the remaining numbers repeatedly. (Though, admittedly, this proof is considerably harder to formalize) $\endgroup$
    – Milo Brandt
    Commented Nov 27, 2015 at 17:35
  • $\begingroup$ One major point is that the demonstration uses proof by contradiction. If someone has never seen, used, practiced, or had explained proof by contradiction, then they are enormously unlikely to invent this entire method of proof on their own. Even when I lay out a complete proof by contradiction to my college algebra students it's the thing that they're most likely to complain about as hurting their brains. $\endgroup$
    – Daniel R. Collins
    Commented Dec 3, 2015 at 22:37

4 Answers 4

Reset to default
14
$\begingroup$

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 Euclid's proof.)

Improve this answer
$\endgroup$
5
  • $\begingroup$ In the last paragraph, do you mean Euclid or Euler? $\endgroup$
    – Joonas Ilmavirta
    Commented Nov 22, 2015 at 11:18
  • $\begingroup$ @JoonasIlmavirta: Oops. Fixed. $\endgroup$
    – Tim Pederick
    Commented Nov 24, 2015 at 9:35
  • 4
    $\begingroup$ I don't think Euclid's proof needs the unique factorization theorem. It needs that every integer greater than $1$ has a prime factor, but I don't think it needs any more than that. $\endgroup$
    – Andreas Blass
    Commented Nov 24, 2015 at 9:44
  • $\begingroup$ @AndreasBlass: Well, I don't know if there is a named theorem that covers half of the fundamental theorem of algebra (i.e. the existence, but not uniqueness, of a prime factorisation). So I just name-dropped that theorem instead (by two different names, apparently)... $\endgroup$
    – Tim Pederick
    Commented Nov 24, 2015 at 9:47
  • $\begingroup$ @Tim One can whittle down Euclid's idea to the essence of the matter - see my answer. $\endgroup$
    – Bill Dubuque
    Commented Dec 2, 2015 at 23:08
13
$\begingroup$

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?

Improve this answer
$\endgroup$
1
  • 3
    $\begingroup$ +1 for "why right now?" $\endgroup$
    – apnorton
    Commented Jul 26, 2014 at 3:26
6
$\begingroup$

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.

Improve this answer
$\endgroup$
0
$\begingroup$

First, we find an integer universally coprime to any prime $\,p.\,$ A moments thought yields the solution $\color{#c00}1$.

Next, we generalize to larger solutions. Since the coprimality of $\,n\,$ to $\,p\,$ depends only its remainder modulo $\,p,\,$ the above solution generalizes to $\, \color{#c00}1+mp,\,$ for any integer $\,m.$

To generalize that to multiple primes $\,p_1,\ldots,p_k\,$ we replace $\,mp\,$ by $\,mp_1\cdots p_k\,$ to obtain an integer that leaves remainder $\color{#c00}1$ when divided by every $\,p_i,\,$ yielding Euclid's classical result.

With appropriate hints, each of the above steps can be motivated quite naturally.

Remark $\ $ In fact one could just as easily motivate a more general solution. Euclid employed $\,1 + p_1\cdots p_n$ is coprime to $\,c = p_1\cdots p_n.\,$ Stieltjes noted the generalization that, furthermore, $\ \color{#c00}{p_1\cdots p_k} +\, \color{#0a0}{p_{k+1}\cdots p_n}\,$ is coprime to $\,c\,$ too, which motivates the following

Key Idea $\, $ Coprimes to $\,c\,$ arise by partitioning into $\rm\color{#c00}{two}\ \color{#0a0}{summands}$ all prime factors of $\,c,\,$ i.e.

Theorem $\,\ \ \color{#c00}a+\color{#0a0}b\ $ is coprime to $\ c\:$ if every prime factor of $\,c\,$ divides $\,a\,$ or $\,b,\,$ but not both.

Proof $\ $ If not then $\,a+b\,$ and $\,c\,$ have a common prime factor $\,p.\,$ By hypothesis $\,p\mid a\,$ or $\,p\mid b.\,$ Wlog, say $\,p\mid b.\,$ Then $\,p\mid (a+b)-b = a,\,$ so $\,p\,$ divides both $\,a,b,\,$ contra hypothesis. $ $ QED

Notice that Euclid's idea is just the special case $\,k=0.$

This extra generality proves quite useful in many applications, e.g. see this answer.

One can generalize further, e.g. from $\,p_i$ distinct primes to pairwise coprimes.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.