Hacker News Reader

Comment by akrolsmir | Hacker News Reader

Yeah. Quick sketch of proof: Any prime is 1 or 2 mod 3, and 1, 3, 5, or 7 mod 8. Squaring each value means that every p^2 is 1 mod 3 and 1 mod 8, which must be 1 mod 24 (Chinese remainder theorem).

Or you could algebraically bash it out.

View on HN

Ah. Little clever realisations like any prime is 1,3,5 or 7 mod 8, that's something that comes very hard to me even though when I see it it looks so trivially true. Did you just realize that property for solving this question or was the property taught to you (directly or through solving some homework assignment)?

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

Reply on news.ycombinator.com