# (open) The most basic math proof I've ever seen

• Indirect Proof
• fresh_42
In summary, the conversation discusses a proof by Euclid about the number of primes, which uses the concept that you cannot derive false from true. The proof involves considering a finite set of primes and finding a number that is not divisible by any of them, leading to the conclusion that the set cannot contain all prime numbers. The conversation also mentions the difficulty of teaching this proof to young children and the assumptions made in the proof.
fresh_42
Mentor
2023 Award
Well, it is what I consider the most basic proof I've ever seen. I like it for several reasons: it is so simple. that you can convince a preschool kid, it uses one of the most fundamental principles at all: you cannot derive false from true, and it is old enough to count as such:

No, sorry kids, not Pythagoras. Euclid's (##\approx 300\, BC##) proof about the number of primes.

For any finite set ##\{p_1,\ldots,p_r\}## of primes, consider the number ##n = p_1p_2 \cdots p_r + 1.## This ##n## has a prime divisor ##p##. But ##p## is not one of the ##p_k## : otherwise ##p## would be a divisor of ##n## and of the product ##p_1p_2 \cdots p_r##, and thus also of the difference ##n − p_1p_2 \cdots p_r = 1,## which is impossible. So a finite set ##\{p_1,\ldots,p_r\}## cannot be the collection of all prime numbers.

Can you phrase the statement which is proven, and rephrase this proof, such that
• it is clearly an indirect proof
• it is clearly a proof by contradiction
Can you tell the tiny difference? It is not a difference in logic, but in wording.

Can you find all the hidden assumptions in the above proof?
Hint: There are many.

etotheipi, BvU and berkeman
One thing I noticed is a preschool kid is going to ask you what a prime number is but maybe a fourth-grader will understand.

The set of primes is assumed to have all primes in the interval of 2 thru n right? so in this case, if 2 were missing then the prime product+1 would be even implying 2 is missing from the set.

jedishrfu said:
One thing I noticed is a preschool kid is going to ask you what a prime number is but maybe a fourth-grader will understand.

The set of primes is assumed to have all primes in the interval of 2 thru n right? so in this case, if 2 were missing then the prime product+1 would be even implying 2 is missing from the set.
Yes, preschool was a bit ambitious. I didn't know the English term for the first 4 school years. As soon as they know how to multiply small numbers, this proof can be taught. Maybe with a bit more effort than the one above, but it is basically possible,

No, the set of primes could be any. Only finiteness is required.

jedishrfu said:
In the US, multiplication tables up to 10x10 are taught in fourth grade (my own experience circa 1960s)

The age doesn't play a role as long as curiosity on the child's side and patience on the adult's sde is there. I once taught a six year old negative numbers and by seven she could solve ##\sqrt{-4}##.

jedishrfu
Cantor's diagonal argument.

Every number has a prime divisor is one of the assumptions.

• Math Proof Training and Practice
Replies
61
Views
6K
• Math Proof Training and Practice
Replies
100
Views
8K
• Calculus and Beyond Homework Help
Replies
3
Views
768
• General Math
Replies
35
Views
3K
• Math Proof Training and Practice
Replies
67
Views
8K
• Topology and Analysis
Replies
2
Views
467
• Math Proof Training and Practice
Replies
97
Views
19K
• Math Proof Training and Practice
Replies
52
Views
10K
• General Math
Replies
16
Views
3K
• Math Proof Training and Practice
Replies
77
Views
13K