Results 1 to 5 of 5

Thread: Puzzle

  1. #1

    Thread Starter
    Only Slightly Obsessive jemidiah's Avatar
    Join Date
    Apr 2002
    Posts
    2,431

    Puzzle

    1. Show that 30^239 + 239^30 is not prime.

    2. Investigate when (p-1)^q + q^(p-1) is divisible by p, for primes p and q.

    Fermat's Little Theorem may be helpful.
    The time you enjoy wasting is not wasted time.
    Bertrand Russell

    <- Remember to rate posts you find helpful.

  2. #2
    Hyperactive Member Lenggries's Avatar
    Join Date
    Sep 2009
    Posts
    353

    Re: Puzzle

    Highlight over solutions

    Part 1:

    Fermat's Little Theorem states that a^(p-1) := 1 mod p. for 1 <= a < p. Let p = 31, which is prime, and a = 239, then 239^30 := 1 mod p.

    Further, 30^239 := -1^239 := -1 mod 31.

    Therefor, 30^239 + 239^30 := -1 + 1 := 0 mod 31. Thus, 31 divides 30^239 + 239^30, and so 30^239 + 239^30 is not prime.


    Part 2:

    Consider 5 cases for (p-1)^q + q^(p-1):
    a. p = q = 2:
    (p-1)^q + q^(p-1)
    = 1^2 + 2^1
    = 1 + 2
    = 3: not divisible by p

    b. p = 2, q != 2
    (p-1)^q + q^(p-1)
    = 1^q + q^1
    = 1 + q
    Since q is prime != 2, q is odd. Therefor 2=p | (p-1)^q + q^(p-1)

    c. p != 2, q = 2 (note that this implies p > 2):
    (p-1)^q + q^(p-1)
    = (p-1)^2 + 2^(p-1)
    := -1^2 + 1 mod p
    := 1 + 1 mod p
    := 2 mod p: Therefor when q = 2, p does not divide (p-1)^q + q^(p-1)

    d. p != 2, q != 2, p != q
    (p-1)^q + q^(p-1)
    := (p-1)^q + 1 mod p, per Fermat's Little Theorem
    := -1^q + 1 mod p
    := -1 + 1 mod p, since q is odd
    := 0 mod p. Therefor p | (p-1)^q + q^(p-1)

    e. p = q, p != 2
    (p-1)^q + q^(p-1)
    = (p-1)^p + p^(p-1)
    := (p-1)^p + 0 mod p, since p | p^(p-1)
    := (p-1)^p mod p. Since p and (p-1) are relatively prime, so are (p-1)^n and p^m for any positive integers n and m. Therefor p does not divide (p-1)^q + q^(p-1)

    In conclusion, (p-1)^q + q^(p-1) for primes p and q is divisible by p iff q != 2 and p != q

    incidentally, examining the same five cases leads to another conclusion:
    (p-1)^q + q^(p-1) is prime iff (q = 2) AND (p = 2 OR p is the first of a twin prime (aka p+2 is prime)).
    Last edited by Lenggries; Dec 1st, 2012 at 12:31 PM. Reason: Corrected error in case D

  3. #3

    Thread Starter
    Only Slightly Obsessive jemidiah's Avatar
    Join Date
    Apr 2002
    Posts
    2,431

    Re: Puzzle

    Excellent, though there's a minor error in the final case; try p=q=3.
    The time you enjoy wasting is not wasted time.
    Bertrand Russell

    <- Remember to rate posts you find helpful.

  4. #4
    Hyperactive Member Lenggries's Avatar
    Join Date
    Sep 2009
    Posts
    353

    Re: Puzzle

    D'oh! Alright, I think I've got it right this time (although it is definitely not an elegant proof). I corrected my own solution in post #2. Please review.

  5. #5

    Thread Starter
    Only Slightly Obsessive jemidiah's Avatar
    Join Date
    Apr 2002
    Posts
    2,431

    Re: Puzzle

    Cool, looks good

    Your proof can perhaps be made more "elegant" with some rearrangement of the presentation, maybe like the following:


    Let A = (p-1)^q mod p and B = q^(p-1) mod p.
    The sum is divisible by p if and only if A+B = 0 (mod p).
    In general, A = (-1)^q, which is never zero mod p.

    If q = p, B = 0^(p-1) = 0, so A+B = 0 if and only if A = 0, but this never happens. So, not divisible in this case.
    If q != p, from FLT, B = 1.
    ...If q=2, A=1, so A+B = 2. Since q=2 != p, this is non-zero, so not divisible in this case.
    ...If q!=2, A=-1, so A+B = 0. So, divisible in this case.

    In all, divisible if and only if 2 != q, q != p.
    The time you enjoy wasting is not wasted time.
    Bertrand Russell

    <- Remember to rate posts you find helpful.

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  



Click Here to Expand Forum to Full Width