Puzzle-VBForums

1. ## 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.

2. ## 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)).

3. ## Re: Puzzle

Excellent, though there's a minor error in the final case; try p=q=3.

4. ## 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. ## 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.

#### Posting Permissions

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

Featured

Click Here to Expand Forum to Full Width

Survey posted by VBForums.