
Nov 20th, 2012, 10:56 PM
#1
Puzzle
1. Show that 30^239 + 239^30 is not prime.
2. Investigate when (p1)^q + q^(p1) 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.

Nov 30th, 2012, 02:40 PM
#2
Re: Puzzle
Highlight over solutions
Part 1:
Fermat's Little Theorem states that a^(p1) := 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 (p1)^q + q^(p1):
a. p = q = 2:
(p1)^q + q^(p1)
= 1^2 + 2^1
= 1 + 2
= 3: not divisible by p
b. p = 2, q != 2
(p1)^q + q^(p1)
= 1^q + q^1
= 1 + q
Since q is prime != 2, q is odd. Therefor 2=p  (p1)^q + q^(p1)
c. p != 2, q = 2 (note that this implies p > 2):
(p1)^q + q^(p1)
= (p1)^2 + 2^(p1)
:= 1^2 + 1 mod p
:= 1 + 1 mod p
:= 2 mod p: Therefor when q = 2, p does not divide (p1)^q + q^(p1)
d. p != 2, q != 2, p != q
(p1)^q + q^(p1)
:= (p1)^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  (p1)^q + q^(p1)
e. p = q, p != 2
(p1)^q + q^(p1)
= (p1)^p + p^(p1)
:= (p1)^p + 0 mod p, since p  p^(p1)
:= (p1)^p mod p. Since p and (p1) are relatively prime, so are (p1)^n and p^m for any positive integers n and m. Therefor p does not divide (p1)^q + q^(p1)
In conclusion, (p1)^q + q^(p1) 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:
(p1)^q + q^(p1) 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 11:31 AM.
Reason: Corrected error in case D

Dec 1st, 2012, 12:09 AM
#3
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.

Dec 1st, 2012, 11:34 AM
#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.

Dec 1st, 2012, 05:12 PM
#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 = (p1)^q mod p and B = q^(p1) 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^(p1) = 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 nonzero, 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

Forum Rules

Click Here to Expand Forum to Full Width
