-
Nov 20th, 2012, 11:56 PM
#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.
The time you enjoy wasting is not wasted time.
Bertrand Russell
<- Remember to rate posts you find helpful.
-
Nov 30th, 2012, 03:40 PM
#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)).
Last edited by Lenggries; Dec 1st, 2012 at 12:31 PM.
Reason: Corrected error in case D
-
Dec 1st, 2012, 01: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, 12:34 PM
#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, 06: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 = (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
-
Forum Rules
|
Click Here to Expand Forum to Full Width
|