Hacker News Reader

Comment by baking | Hacker News Reader

"For any prime number larger than 3, prove that p^2-1 is always divisible by 24."

That seems like an easy interview question.

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.

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

If not hiring people like me is your goal..

edit: I sincerely hope you were making a joke.

What is my middle name?

That's a fairly easy question as well. Every single person in my immediate vicinity knows it. My daughter who is less than 36 months old knows it.

Don't you?

If you are hiring math PhD's I would think most of them would find the question almost insulting, or at least assume that you had tougher questions to throw at them once they spit that one out.

You are absolutely right. I didn't read the context of the question. I have left my comment un-edited to remind me not be such a smarta$$.

Reply on news.ycombinator.com