(Re: 30-second mental proof, with visualization, that 2[sup]n[/sup] - 1 can be prime only if n is prime.
Wanna play along? Open the spoilers step by step, and see how quickly you can see where I’m going with this!
By contraposition, the statement “2[sup]n[/sup] - 1 is prime only if n is prime” (which is to be proved) is equivalent to:
[spoiler]If n is composite then 2[sup]n[/sup] - 1 is composite. We will prove this.
If n is composite, then it can be represented as . . .[/spoiler]
. . . the product jk of two integers j and k (each > 1), and 2[sup]n[/sup] - 1 can be written as 2[sup]jk[/sup] - 1. Now, visualize that number written in base 2 . . .
2[sup]n[/sup] - 1 or 2[sup]jk[/sup] - 1, written in base 2, is just a string of n (or jk) 1’s. Example: 2[sup]24[/sup] - 1 is 111111111111111111111111. If n (or jk) is composite . . .
. . . then those jk 1’s can be grouped into j groups of k digits, or k groups of j digits. Example: 2[sup]24[/sup] - 1 can be written as
111111 111111 111111 111111 – or as: 1111 1111 1111 1111 1111 1111.
Do you see the proof yet?
Take 111111 111111 111111 111111 for example. This is clearly divisible by 111111, and thus is composite.
And similarly, writing 2[sup]jk[/sup] - 1 as j groups of k digits, it is clearly divisible by one group of k digits, or 2[sup]k[/sup] - 1. Or, writing it as k groups of j digits, divisible by one group of j digits,
or 2[sup]j[/sup] - 1.