Show that for any prime greater than 3 that is divisible by 24.
This was the first exercise that I was able to solve independently during my first year of mathematics classes. Coincidentally, it is also the only exercise whose solution I remember in its entirety. For these sentimental reasons, and the fact that it's an accessible puzzle that others may find enjoyable, the proof is presented below.
What it means to be divisible by 24 is that the prime factorization of a number contains at least one 3, and at least three 2s. In the light of factorization, it may make sense to try to factor . And indeed, it can be written as . Note that since is greater than 3, it is not equal to 2. And by its primality, it is indivisible by any other prime, including 2. That is to say that is odd and, by extension, both and are even. And since they are consecutive even numbers and every other even number is a multiple of 4, exactly one of them must be divisible by 4. Since either or is a multiple of 4, and the other is a multiple of 2, their product must be divisible by . That means that we just need to show that one of the factors is divisible by 3 to complete the proof. It follows from similar reasoning. Since any three consecutive integers contains exactly one multiple of three, either , or is divisible by 3. Because is greater than 3 and prime, it can't be , which leaves one of the two factors of . End of proof!
When reading the proofs of others it can often be completely unclear why the given steps are taken, as if they are provided by divine inspiration. Above, it may be natural to try to factor an expression when we are studying its divisibility, but things will not be as evident in general. The number of potential operations at any point of a proof will be so large that simply trying all possible sequences of transformations until the desired result is obtained is infeasible for all but the simplest theorems, even for modern super computers. While trial and error is certainly a core principle of proof construction, it will have to be guided by a strong intuition and comprehensive knowledge of techniques and transformations that have worked well in the past. There are efforts underway to equip automated theorem provers with neural networks to emulate this intuition, but when it comes to proofs, humans reign supreme. For now.
On a personal note: after struggling a lot with the step change in difficulty coming into university, I remember being really proud of finally figuring out a proof on my own and feeling that maybe I could do this after all. And for that, I will always remember this exercise fondly.