Subscribe via feed.

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?


This post is under “Tom” and has 25 respond so far.
If you enjoy this article, make sure you subscribe to my RSS Feed.

25 Responds so far- Add one»

  1. 1. Wizard of Oz Said:

    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.

  2. 2. Chris Said:

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

  3. 3. Wizard of Oz Said:

    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?

  4. 4. Chris Said:

    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.

  5. 5. DP Said:

    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.

  6. 6. Chris Said:

    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.

  7. 7. DP Said:

    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.

  8. 8. Horbz Said:

    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.

  9. 9. DP Said:

    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.

  10. 10. Chris Said:

    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.

  11. 11. ram Said:

    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.

  12. 12. Chris Said:

    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.

  13. 13. Wizard of Oz Said:

    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?

  14. 14. Chris Said:

    Hi Wiz. ram’s post is was awaiting approval. I can see it because I’m an author.

  15. 15. Wizard of Oz Said:

    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?

  16. 16. Chris Said:

    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.

  17. 17. DP Said:

    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.

  18. 18. Wizard of Oz Said:

    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?

  19. 19. Chris Said:

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

  20. 20. Chris Said:

    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.

  21. 21. Wizard of Oz Said:

    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?

  22. 22. Chris Said:

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

  23. 23. Kali Prasad Tripathy Said:

    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

  24. 24. Chris Said:

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

  25. 25. Chris Said:

    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.

Post a reply




PHP Warning: PHP Startup: Unable to load dynamic library 'C:\Program Files (x86)\Parallels\Plesk\Additional\PleskPHP5\ext\php_mssql.dll' - The specified module could not be found. in Unknown on line 0 PHP Warning: PHP Startup: Unable to load dynamic library 'C:\Program Files (x86)\Parallels\Plesk\Additional\PleskPHP5\ext\php_pdo_mssql.dll' - The specified module could not be found. in Unknown on line 0