Based on the previous post: let n = (2[SUP]2p[/SUP] -2[SUP]p[/SUP]+1)/3 where p is a prime number, is it true that 2[SUP]n-1[/SUP] = 1 (mod n) ?

[QUOTE=alpertron;312175]Based on the previous post: let n = (2[SUP]2p[/SUP] -2[SUP]p[/SUP]+1)/3 where p is a prime number, is it true that 2[SUP]n-1[/SUP] = 1 (mod n) ?[/QUOTE]

Nice problem. Proof: let p>2 prime number

Observe that: (2^(2*p)-2^p+1)/3 | 2^(6*p)-1
so it is enough to prove that for p>2: 2^(n-1)==1 mod 2^(6*p)-1
it is equivalent to n-1==0 mod (6*p)
so (2^(2*p)-2^p-2)/3==0 mod (6*p)
(18*p)|2^p*(2^p-1)-2

Let p>3 then it is true mod p (use Fermat's little theorem), 2 also divides, this is trivial since 2^p is even. For 9 use: p=6k+-1 then 2^p=={2,5} mod 9, for the two cases: 2^p*(2^p-1)-2=={0,18}==0 mod 9.
Since 2,9,p are relative prime numbers for p>3 it means that the divisibility is also true for 2*9*p=18*p.
For p=3: 2^(n-1)==1 mod n is also true.

Thanks.

Hi everyone


I know I am a bit late.... BUT I have the answer to your problem:


take N = 2^524287 - 1.



Notice that 524287 = 2^19 - 1, this is a clue for the proof ;)


Indeed, you just need to consider the sequence X(n+1) = 2^X(n) - 1 with X(0) = 19 and proove that all terms of the sequence verify X(n)*X(n+1) divide 2^X(n) - 2.


Have a nice day!

Hi

I would like to know if a^(2^n) mod (2^n-1) = a² when a is between 0 and sqrt(2^n-1) and a is an integer when 2^n-1 is prime and only if it's prime ?

I tried this with some Mersenne exposant and it apparently works.

It can't be used to eliminate non-Mersenne exponant quickly ?

Thanks :D

In My Humble Opinion (IMHO) the even numbers are easier to keep track of

[QUOTE=kijinSeija;574293]Hi

I would like to know if a^(2^n) mod (2^n-1) = a² when a is between 0 and sqrt(2^n-1) and a is an integer when 2^n-1 is prime and only if it's prime ?

I tried this with some Mersenne exposant and it apparently works.

It can't be used to eliminate non-Mersenne exponant quickly ?

Thanks :D[/QUOTE]
That is a PRP test in disguise. From Fermat theorem, a^p=a (mod p) if p is prime. Amplify with a, you get a^(p+1)=a^2 (mod p). Replace p with Mp and you have your test. Replace a with 3 and that's what P95 and gpuOwl are doing.

Yes, it can be used to eliminate composite Mp's, but not "fast". Well, not faster than we are doing already.

[QUOTE=LaurV;574334]That is a PRP test in disguise. From Fermat theorem, a^p=a (mod p) if p is prime. Amplify with a, you get a^(p+1)=a^2 (mod p). Replace p with Mp and you have your test. Replace a with 3 and that's what P95 and gpuOwl are doing.

Yes, it can be used to eliminate composite Mp's, but not "fast". Well, not faster than we are doing already.[/QUOTE]

Hi and thanks for your reply.

And by the way I noticed something interesting : if a+b+c = 2^n-1 you can found number with a²+b²+c² = (4^n-1)/3 and it seems it works with Mersenne number (it seems it doesn't work with composite Mersenne number like 2^11-1 or 2^23-1)

For example 4+2+1 = 7 (2^3-1) and 4²+2²+1² = 21 (4^3-1)/3
another example : 14+9+8 = 31 (2^5-1) and 14²+9²+8² = 341 (4^5-1)/3

There is a way to explain this ? Thanks :)

I'm not sure what you are trying to say here...

4+3+0 = 7 (2^3-1), but 4^2 + 3^2 + 0^2 = 25 which is not (4^3-1)/3

13 + 10 + 8 = 31 (2^5-1) but 13^2 + 10^2 + 8^2 = 333 which is not (4^5-1)/3

So clearly there's something I'm missing.

[QUOTE=slandrum;578931]I'm not sure what you are trying to say here...

4+3+0 = 7 (2^3-1), but 4^2 + 3^2 + 0^2 = 25 which is not (4^3-1)/3

13 + 10 + 8 = 31 (2^5-1) but 13^2 + 10^2 + 8^2 = 333 which is not (4^5-1)/3

So clearly there's something I'm missing.[/QUOTE]

I mean you can find three random numbers (a, b, c) that respect that :

a+b+c = 2^n-1
and a²+b²+c²=(4^n-1)/3

If a+b+c is a prime Mersenne number.

you can't find any numbers for example for a+b+c = 2^11-1 and a²+b²+c² for (4^11-1)/3 it seems it doesn't exist.