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...
That'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.
Comments
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...
That'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.
How 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.
(n+1).(n-1) = n^2 - n + n - 1 = n^2 - 1