mersenneforum.org

mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Homework Help (https://www.mersenneforum.org/forumdisplay.php?f=78)
-   -   Generalized Mersenne Primes (https://www.mersenneforum.org/showthread.php?t=17340)

Unregistered 2012-10-27 16:04

Generalized Mersenne Primes
 
I believe that I remember a theorem having to do with Generalized Mersenne primes of the form: (a^n+b^n)/(a+b).
The theorem states that if (a^n+b^n)/(a+b) is prime, then n must also be prime.
Does anyone know a reference that has a proof of this?
Thanks.

Batalov 2012-10-27 18:18

For even values of n, this doesn't divide. For them, there's no denominator, but the logic below still applies.

For odd values of n: Suppose you have a composite n = k*m, with k>=3. Then,
(a[SUP]n[/SUP]+b[SUP]n[/SUP])/(a+b) = (a[SUP]km[/SUP]+b[SUP]km[/SUP])/(a+b) =
= (a[SUP]k[/SUP]+b[SUP]k[/SUP])/(a+b)*(a[SUP](k-1)m[/SUP] - b[SUP]m[/SUP]*a[SUP](k-2)m[/SUP] + b[SUP]2m[/SUP]*a[SUP](k-3)m[/SUP] + ... + b[SUP](k-1)m[/SUP])
where (a[SUP]k[/SUP]+b[SUP]k[/SUP])/(a+b) is > 1. QED, composite.

For proper Mersenne numbers a+b = 2+(-1) = 1, which makes for an interesting case - there's no denominator.

When b=1, a[SUP]n[/SUP]+b[SUP]n[/SUP] is a proper Fermat number, and for b>1 and odd (prime) n, (a[SUP]n[/SUP]+b[SUP]n[/SUP])/(a+b) has the property that you sought for.

science_man_88 2012-10-27 18:28

[QUOTE=Unregistered;316166]I believe that I remember a theorem having to do with Generalized Mersenne primes of the form: (a^n+b^n)/(a+b).
The theorem states that if (a^n+b^n)/(a+b) is prime, then n must also be prime.
Does anyone know a reference that has a proof of this?
Thanks.[/QUOTE]

[CODE](15:18)>for(a=1,100,
for(b=a,100,
for(n=1,100,
if(((a^n+b^n)/(a+b))%1.==0 &&isprime((a^n+b^n)/(a+b)) && !isprime(n),
print(((a^n+b^n)/(a+b))","a","b","n);)
)
)
)
[/CODE]

[QUOTE]14321,6,26,4
280097,12,69,4
4481,14,18,4
134417,24,57,4[/QUOTE]
shows that n=4 has counterexamples.

Batalov 2012-10-27 19:14

For even values of n (and not coprime a,b), indeed, you can arrive to some convenient cancellations (a+b will have to be 2*gcd(a,b)[SUP]n[/SUP], where n will be a power of two) and get an extended Generalized Fermat in disguise.
E.g. (6^4+26^4)/(6+26) is xGF'(3,13,4).

Batalov 2012-10-27 19:31

P.S. Correction re: [I]2[/I]*gcd(). Not always 2, of course. 2 will frequent, because there are very many prime xGF'(a,b,4) (=(a^4+b^4)/2) with odd a and odd b. Tons. When a+b is 2[SUP]x[/SUP], you can finish the counterexample by multiplying a and b by 2[SUP]x-1[/SUP] or similar. Ugh, I need some coffee.

Unregistered 2012-10-30 14:47

Thanks so much for your replies. Very helpful.
Batalov, if I understand your arguments, if n is odd and composite then (a^n+b^n)/(a+b) must also be composite. Can this be extended to any composite n with an odd factor? If so, then only n that are powers of two could possibly result in a prime. I have found some counterexamples and have observed that a and b are never coprime. Can you think of an argument to support this observation about coprimes? Thanks.

science_man_88 2012-10-31 14:16

[QUOTE=Unregistered;316416]Thanks so much for your replies. Very helpful.
Batalov, if I understand your arguments, if n is odd and composite then (a^n+b^n)/(a+b) must also be composite. Can this be extended to any composite n with an odd factor? If so, then only n that are powers of two could possibly result in a prime. I have found some counterexamples and have observed that a and b are never coprime. Can you think of an argument to support this observation about coprimes? Thanks.[/QUOTE]

well assume gcd(a,b)=c then the equation comes to:

(a^n+b^n)/(a+b) = c^n*(d^n+e^n)/c*(d+e) =c^(n-1)*(d^n+e^n)/(d+e) so if (d^n+e^n)/(d+e) is integer so is (a^n+b^n)/(a+b) but with a integer divisor >1 so it's not prime.


All times are UTC. The time now is 03:09.

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.