undefined | Better HN

0 pointstinco12y ago0 comments

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)?

0 comments

4 comments · 1 top-level

mdda12y ago· 3 in thread

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...

baking12y ago

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.

tincoOP12y ago

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.

pluies12y ago

(n+1).(n-1) = n^2 - n + n - 1 = n^2 - 1

j / k navigate · click thread line to collapse