It was once asked on the Math GRE -- what's the greatest common divisor of p4-1 over all primes p > 5? It's an odd way to formulate the question, but it's simple enough.
First, remember the possibly familiar fact that for primes p > 3, p2-1 is a multiple of 24. This is simple enough -- we can write p2-1 = (p-1)(p+1). Since p is odd, both of these factors are divisible by 2, and one of them is divisible by 4. So p2 - 1 is a multiple of 8. (This is true for all odd numbers, not just primes.) Furthermore, since p isn't a multiple of 3, either p-1 or p+1 is. So p2 - 1 is divisible by 8 and by 3, therefore by 24.
This suggests an approach to the analogous problem for fourth powers, which is basically taken from the original post. A bit of numerical experimentation gives 74-1 = 2400, 114 - 14640, 134 - 1 = 28560, ... -- all of these are divisible by 240. So you start to suspect that 240 might be the answer. And it turns out that it is; we can write
p4 - 1 = (p-1)(p+1)(p2+1).
Now, what power of 2 appears in the prime factorization of p4-1? Each of the three factors on the right-hand side is even; furthermore one of p-1 or p+1 must be divisible by 4, so there are at least four occurrences of 2.
Similarly, either p-1 or p+1 is divisible by 3.
And p4 - 1 is divisible by 5 by Fermat's little theorem. (A brute-force analysis is also possible -- if p is congruent to 1 mod 5 then p-1 is divisible by 5, if p is congruent to 4 mod 5 then p+1 is divisible by 5, and is p is congruent to ± 2 mod 5 then p2 + 1 is divisible by 5.)
So p4 - 1 is divisible by 24 31 51, which is 240, for all primes p > 5. We can easily see that, say, gcd(114-1, 134 - 1) = 240. So 240 is the answer.
The original post which I found this from asked two questions:
- can this be done in a less ad hoc manner?
- are there generalizations?
The method generalizes pretty easily to other powers; by a similar analysis, the gcd of p6 - 1 over primes p > 7 is 504. For eighth powers, 480. For tenth powers, 264. (In all cases, when taking nth powers we require p > n+1.)
There's no pattern obvious in these numbers, though. But they turn out to be related to the Bernoulli numbers. If you know more about this sort of thing that I do you might try to prove (or disprove) that:
(I have not made any attempt at all to determine if this is known. Feel free to point out if it is!)Conjecture. gcd(pa - 1), taken over primes p > a+1, is the denominator of Ba/(2a), where Ba are the Bernoulli numbers.
4 comments:
You should ask Tanya Khovanova, she likes puzzles like this and may know the answer, or figure it out.
Peter J. Cameron's comment, on Sloane's table, almost proves the desired result. Let me spell this out a little. Let G be the GCD of p^n-1, where p runs over all sufficiently large primes.
Now, the condition
(0) m divides G
is equivalent to
(1) m divides p^n-1, for all sufficiently large p
is equivalent to
(2) for every unit u in the ring Z/m, we have u^n=1.
This latter is because, by Dirichlet's theorem, every unit in Z/m occurs as the image of some prime in Z. Carmichael defines lambda(m) to be the exponent of (Z/m)^*. In other words, (2) is equivalent to
(3) lambda(m) divides n.
Now, Cameron's comment is that (3) is equivalent to
(4) m divides lambda^*(n), where lambda^*(n) is the sequence defined from denominators of Bernouli numbers.
So m divides G if and only if m divides lambda^*(n) and thus G=lambda^*(n). In short, the GCD of p^n-1, where p ranges over sufficiently large primes, is lambda^*(n).
The first thing that worries me is that it is not clear to me whether just taking p to be larger than n is sufficiently large. I also don't know why Cameron's comment is true.
The missing link appears to be the von on Staudt-Clausen theorem, namely that the denominator of the a-th Bernoulli number is equal to the product of the primes dividing a-1.
If we work one prime at a time in David's argument: For q an odd prime, then q^b divides the gcd if and only if (q-1)*q^(b-1) divides a. This is since we know explicitly (q-1)*q^(b-1)=lambda(q^b).
Using the above quoted theorem, this is equivalent to q^b dividing the denominator of B_a/(2a). To complete the desired result, we have to do a similar analysis at the prime 2, which is slightly different since lambda(2^m)=2^(m-2) for m>2, but similar.
buy bactrim without prescription buy bactrim online buy bactrim buy bactrim es online without prescription buy bactrim without a prescription overnight buy bactrim f
[url=http://bactrim.eventbrite.com/]buy bactrim without prescription [/url]
glucophage side effects glucophage metformin when to take glucophage doses glucophage side effect glucophage kidney pain glucophage recall how to take glucophage
[url=http://takeglucophage.eventbrite.com/]glucophage odor cause [/url]
proscar and propecia prostate cancer resistance to proscar generic for proscar proscar finasteride proscar pi proscar without a prescription proscar for hair loss
[url=http://proscar.eventbrite.com/]proscar and psa levels [/url]
impotence solutions levitra users how does levitra work impotence drug name acquisto levitra levitra buy generic levitra
[url=http://virb.com/yalevi]levitra website [/url]
http://proscar.eventbrite.com/
Post a Comment