4 ms·
"For any prime number larger than 3, prove that p^2-1 is always divisible by 24." That seems like an easy interview question.
by baking 12y ago
"For any prime number larger than 3, prove that p^2-1 is always divisible by 24."
That seems like an easy interview question.
- akrolsmir 12y agoYeah. 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.
- tinco 12y agoAh. 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)?
- mdda 12y agoHere'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
- tinco 12y agoIf not hiring people like me is your goal.. edit: I sincerely hope you were making a joke.
- ZenPro 12y agoWhat 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?
- baking 12y agoIf 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.
- ZenPro 12y agoYou 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$$.