4 ms·
Here's an "elementary" proof : If n is prime>3 then it's definitely odd. n^2-1 = (n+1).(n-1) But n is odd, so (n+1) and (n-1) are both even. So overall, we
by mdda 12y ago
Here's an "elementary" proof :
If n is prime>3 then it's definitely odd.
n^2-1 = (n+1).(n-1)
But n is odd, so (n+1) and (n-1) are both even. So overall, we have a factor of 4.
But, since one of those two is 2 different from the other, it must also be divisible by 4.
Now, looking at this sideways too, we also have a run of 3 numbers {(n-1), n, (n+1)}. So one of them must be divisible by 3. But n isn't (since it's prime). Therefore at least one of the other two is.
So,overall, we have 2.4.3 as a minimum set of factors...
- baking 12y agoThat's the one I thought of once I wondered how hard it could be. I was more amused by the idea of the question appearing in Businessweek and wondering how many of their readers attempted to answer it versus the average HN reader.
- tinco 12y agoHow do you trivially construct `n^2-1 = (n+1).(n-1)` ? I feel like I'm failing at basic algebra here, but I don't see it.
- pluies 12y ago(n+1).(n-1) = n^2 - n + n - 1 = n^2 - 1