## Divide by 24

Posted by DP on April 18, 2011 – 9:40 am

Can you prove that p^2 – 1 is always divisible by 24 for any prime number (p) greater than 3?

Posted by DP on April 18, 2011 – 9:40 am

Can you prove that p^2 – 1 is always divisible by 24 for any prime number (p) greater than 3?

April 18th, 2011 at 2:58 pm

All primes greater than 3 can be expressed as 6n ± 1 for any integer n.

So p^2 – 1 = 36n^2 ± 12n = 12n * (3n ± 1)

(3n ± 1) is always even, so the term is divisible by 24.

April 18th, 2011 at 3:04 pm

Hi WIz. LOL, you didn’t do it that way last time, even though that’s what I had expected.

April 18th, 2011 at 3:41 pm

I must be getting old – I can’t even remember this puzzle coming up before, much less how I did it.

So how did I do it then?

April 18th, 2011 at 4:30 pm

Hi WIz. I can’t find them, but I had posted two problems on the old site. The first was to show that all primes > 3 were of the form 6n ± 1. Then I immediately followed up with the one posted here.

As I know how to do it, I’ll let it live a bit longer. But I think that the divisibility by 24 should come as a surprise to most people – so it is a nice problem.

April 20th, 2011 at 2:52 pm

The solution is suprisingly simple, but difficult to see at first. Once you see it, you’ll all wonder why you weren’t the first to solve it this way. I’d like to leave this one for another day or two to see if anyone solves it the way I’m thinking.

April 20th, 2011 at 9:21 pm

p^2 – 1 = (p-1)(p+1). As p is an odd prime, p-1 and p+1 are both divisible by 2. But every other number that is divisible by 2 is also divisible by 4. So (p-1)(p+1) is divisible by 2*4 = 8.

Also as p is prime and > 3, it cannot be divisible by 3. But every third number is divisible by 3, so either p-1 or p+1 is divisible by 3. So (p-1)(p+1) is divisible by 3.

Altogether (p-1)(p+1) = p^2 -1 is divisible by 24.

That’s pretty much how Wiz did it last time.

April 21st, 2011 at 9:41 am

That’s the one. Pretty much how I would have solved this one, so I won’t spend any more time repeating Chris. It really is simple once you see how it is done.

April 21st, 2011 at 9:54 am

How about this… to get a prime number, you can just do (1*2*3*4*5*….*n)-1. Or n!-1. So p=n!-1. Since 4!=24, then any factorial of a number thats greater than or equal to 4 will be divisible by 24.

April 21st, 2011 at 10:25 am

Horbz. It took me a minute to follow you. Not everything you said is wrong. Let me see if I get what you are saying.

we know: p^2 – 1 = (p-1)(p+1)

you say: p = n!-1

so: p^2 – 1 = (n!-2)(n!)

and if n! = 24, then (n!-2)(n!) is surely divisible by 24 => p^2 – 1 is divisible by 24. So n must be greater than 3, making p at least 23.

The problem with your solution is that it doesn’t cover all primes greater than 3. It only accounts for primes that are expressed by n!-1, where n>3.

April 21st, 2011 at 12:06 pm

Hi Horbz. I wonder if you’re thinking of Wilson’s theorem: If and only if p is prme, then (p-1)! = -1 (mod p).

Your assertion that n! – 1 is prime isn’t true. e.g 5! -1 = 119 = 7*17 and 8! -1 = 40319 = 23*1735. But much more importantly, as DP says, your expression doesn’t include for all primes.

April 23rd, 2011 at 12:54 am

i think we cant express all the prime numbes geater 3 with 6n ± 1

ex: 319= (6*53)+1 but it is completely divisible by 11.

April 23rd, 2011 at 3:50 am

Hi ram. All prime numbers greater than 3 are of the form 6n ± 1. But, that doesn’t mean that all numbers of that form are prime.

There is no simple formula (and possibly canot be) that only generates prime numbers.

April 24th, 2011 at 1:44 am

Something funny going on about the way these posts are posted (or not).

Post 11 above seems to be a reply to someone (ram) for whom no post is shown.

In other puzzles I’ve seen the last post number change (up and down) when there is no new post, with earlier posts being inserted later or deleted later.

What’s going on?

April 24th, 2011 at 5:42 am

Hi Wiz. ram’s post

~~is~~was awaiting approval. I can see it because I’m an author.April 25th, 2011 at 12:24 pm

Hi Chris,

ram’s post took more than 2 days to appear, and 3 subsequent posts appeared in the meantime.

There seems to be an ongoing problem with some posts being delayed and hence the flow of discussion being disrupted.

My posts usually (but not always) appear immediately so I suppose that this problem has mainly to do with new contributors being checked for possible spam.

Maybe this site needs more approvers to provide faster turnaround?

April 25th, 2011 at 2:47 pm

Hi Wiz. Wih the exception of Rajesh Lal, only the author of the blog can approve suspect spam. If he doesn’t check frequently, then we get the delays. Because I’m an author, I can see all (I assume) pending posts.

Even some of my posts get the “awaiting moderation” delay – especially if they contain a link.

April 25th, 2011 at 4:25 pm

Wiz,

I try to keep up with approving posts on my posted problems, but when the weekends hit it gets a little tough to be on all the time. That is why it took a couple days for ram’s post to show.

It happens all the time on other problems. You are correct that it is for new people to make sure they aren’t posting spam.

The only reason I ever see my posts not appear right away are if I am not signed in, and type my e-mail incorrectly. Then it thinks I’m a new DP.

I don’t know how else to get pending posts approved any faster. Might need to take that up with Rajesh.

April 25th, 2011 at 6:04 pm

Rajesh, are you there? We never seem to hear from you.

I suggest a few more approvers to speed up turnaround of posts and turn this good site into a great one. Nerdy types that sit in front of their computer all day and never go out would be ideal. Me, I’d be no good – I’m away for long spells too often.

BTW, are you the cool dude in the thumbnail pic at the top of each page?

April 26th, 2011 at 6:00 am

Hi Wiz. I expect that Rajesh is quite busy. I’ll ask him if it’s possible (and if he’s willing) to elevate me. I’m a nerdy type that sits in front of his computer 16/7

April 26th, 2011 at 2:10 pm

Hi WIz. Rajesh has very kindly promoted me to an administrator . I’ve just cleared out all the junk from behind the scenes – there was tons of it.

At the moment, there are no pending comments.

April 26th, 2011 at 11:04 pm

Hi Chris,

Congratulations on a well-deserved promotion! You should put your mug shot up there alonside Rajesh Lal (if that’s who it is).

How do the rest of us get our pics on our posts?

April 27th, 2011 at 4:12 am

Hi Wiz. Thanks.

I hven’t the faintest idea how to put a picture in the box. I’m pretty sure that is a picture of Rajesh, but it is very low resolution.

I’ve also asked him if he can enable superscripts and subscripts for everyone. It doesn’t seem to have happened yet – maybe only authors can do it. But I can do it – proof: e

^{πi}+ 1 = 0, ecstasy. I wasted a good half-hour revising some of my recent posts just to take advantage of that.If you want to try, I did that example with e<sup>πi</sup> + 1 = 0

Subscripts use “sub” rather than “sup”. e.g. x

_{i}July 29th, 2012 at 8:02 am

1st ans is wrong and no one has corrected it

I did not see any one pointing to mistake correction

So p^2 – 1 = 36n^2 ± 12n = 12n * (3n ± 1)

(3n ± 1) is always even, so the term is divisible by 24.

the 2nd line should be

either n or (3n ± 1) is always even.

(for n even 3n+/-1 is odd)

this completes the proof

July 29th, 2012 at 8:35 am

Hi Kali. Wow! you really are on the ball. Even after you pointed it out, it took me quite a few seconds to see the mistake. I guess that I was subconsciously transferring the oddness of p to n.

Thank you

December 11th, 2013 at 7:54 am

A neater solution is provided by the Carmichael lambda theorem:

a^λ(m) = 1 mod (m), when gcd(a,m) = 1 and λ(m) is the Carmichael lambda function.

λ(24) = λ(2^3 * 3) = lcm(λ(2^3),λ(3)) = lcm(2,2) = 2.

In fact that shows a^2 – 1 is divisible by 24 if a isn’t divisible by 2 or 3.