My younger son is doing a little review work in Art of Problem Solving’s Introduction to Number Theory book. This book is a wonderful way for kids to learn all sorts of interesting properties of numbers. Today he told me that he was looking at a section on “primes and composites.”
So, we talked and the conversation led to a discussion about why there were infinitely many primes.
He remembered the “add one” piece of the proof that there are infinitely many primes, but what that “add one” bit was a key idea wasn’t something that he understood. So we talked some more:
I love how he found his way back to the proof and realized why the “add one” part was important. It was also pretty cool to see that he wasn’t bothered by the fact that the infinite list he was making might not have all of the primes – it was still infinite!
Fun morning 🙂
Mike's Math Page 
Recently I learned the proof that there are infinitely many composite numbers. Assume that there is a finite list (with at least two elements, say 4 and 6). Multiply them all together and don’t add 1. The result is a larger composite number!
It’s not quite as deep as Najunamar’s theorem, namely that every even prime is the sum of two odd numbers.