Conjectured Primality Test for 2^p-1, (2^p+1)/3 and (2^2^n+1) - Page 5

alpertron · 2006-05-30, 12:52

For Mersenne primes we have:

$q = 2^p-1$ where both $p$ and $q$ are primes.

From Fermat's Little Theorem we have $a^{q-1} \equiv 1 \pmod q$

The question now is to find $r \equiv a^{(q-1)/p} \pmod q$

From both equations we have:

$r^p \equiv 1\pmod q$

This diophantine equation has at most $p$ roots because the polynomial modulo a prime has degree $p$ . It's easy to see that all roots have the form $2^n\pmod q$ for $0\le n<p$ because:

$(2^n)^p \equiv (2^p)^n \equiv 1^n \equiv 1\pmod q$

Notice that the numbers $2^n\pmod q$ in the given range of $n$ are all different because $2^n < q$ .

Since we found $p$ roots these are the complete set of possible values of $r$ . Of course $r$ is one of these roots.

So r must be a power of 2 modulo q as stated in the conjecture.

alpertron · 2006-05-30, 15:13

For prime numbers of the form $q=(2^p+1)/3$ where $p$ is prime:

From Fermat's Little Theorem we have $a^{q-1} \equiv 1\pmod q$

The question now is to find $r = a^{(q-1)/p}$

$r^p \equiv 1\pmod q$

The polynomial $r^p - 1$ modulo a prime has at most $p$ roots because its degree is $p$ . It's easy to see that the roots have the form $2^{2n}\pmod q$ for $0\le n<p$ because:

$(2^{2n})^p \equiv (2^{2p})^n \equiv ((2^{2p}-1)+1)^n \equiv ((2^p-1)(2^p+1)+1)^n \equiv 1^n \equiv 1$ .

The penultimate step is correct because $2^p+1 \equiv 0\pmod q$ .

Now notice that $2^p+1 \equiv 0$ , so $2^p \equiv -1$ . Then $2^{2n} \equiv -2^{2n-p}$

So the roots have the form $2^{2n}$ or $-2^{2n-p}$

Since all exponents are in the range $0\le n<p$ , all values are different.

Since we found $p$ roots these are the complete set of possible values of $r$ . Of course $r$ is one of these roots.

So $r$ must be a power of 2 or the negative of a power of 2. In the last case the result mod $q$ will be odd (because odd - even = odd).

AntonVrba · 2006-05-30, 16:12

The Conjecture could be generalised

Let p be a prime integer and
Q = (b^p-1)/(b-1) or Q=(b^p+1)/(b+1)

Let x=(Q-1)/p and y be an integer GCD[y,b]==1

y^x = r (mod Q)

if b even and r is odd then r=Q-r

if b odd and r is even then r=Q-r

Q is prime iff r==b^z , z a integer.

alpertron · 2006-05-30, 16:26

The new conjecture appears to be wrong.

Let b=3 and p=5. We get q=(3⁵+1)/(3+1) = 61. So all numbers are prime.

Now let y = 4, so gcd(y, b) = 1 as stated.

x = (q-1)/p = (61-1)/5 = 12
r = y^x = 4^12 = 20 (mod 61)

Since b is odd and r is even we take r = 61-20 = 41 which is not a power of 3.

ewmayer · 2006-05-30, 18:21

Editorial Note: I've merged all these related threads into a single one. -EWM

T.Rex · 2006-05-30, 19:07

Quote:

Originally Posted by ewmayer

Editorial Note: I've merged all these related threads into a single one. -EWM

Hummm. I'm not sure this is a good idea.
The first posts talk about a conjecture about a test equivalent to LLT but based on Cycles of the LLT, and about an "idea" that could speed up proving a Mersenne number is composite. Then Anton and I found other examples (for Wagstaff and Fermat numbers) of a LLT-like test using Cycles.
Now, starting with post #46 of Anton, it seems we are starting another discussion about another conjecture, not based on LLT, and with no relationship with first posts.
So I would like this thread to be separated into 2 threads. Do you agree ?
Tony

alpertron · 2006-05-30, 19:33

Tony is right. The latest posts use pseudoprimality tests and are related to a conjecture that states that the Mersenne numbers and the numbers of the form (2^p+1)/3 are primes if they pass these tests.

This is not related in any way to LLT.

AntonVrba · 2006-05-30, 20:05

Quote:

Originally Posted by alpertron

The new conjecture appears to be wrong.

Let b=3 and p=5. We get q=(3⁵+1)/(3+1) = 61. So all numbers are prime.

Now let y = 4, so gcd(y, b) = 1 as stated.

x = (q-1)/p = (61-1)/5 = 12
r = y^x = 4^12 = 20 (mod 61)

Since b is odd and r is even we take r = 61-20 = 41 which is not a power of 3.

Oh Oh - the generalised form is a bit more dificult but you might have noticed that 20+61=81 which is a power of three.

and y=7 then r=7^12 = 34 (mod 61)
and 61-34 = 27

and for y=19 then r=3

alpertron · 2006-05-30, 20:14

You can use the same steps that I've given above in order to show that:

For prime Q = (b^p-1)/(b-1) you get r = bⁿ (mod Q)

For prime Q = (b^p+1)/(b+1) you get r = b²ⁿ (mod Q) or r = -b^2n-p (mod Q)

AntonVrba · 2006-05-30, 20:14

Quote:

Originally Posted by T.Rex

Now, starting with post #46 of Anton, it seems we are starting another discussion about another conjecture, not based on LLT, and with no relationship with first posts.
So I would like this thread to be separated into 2 threads. Do you agree ?
Tony

Fully agree - sorry for starting the second thread so soon.

T.Rex · 2006-05-31, 17:15

Quote:

Originally Posted by AntonVrba

Mersenne:
Conjecture:
Let p be a prime integer and M = (2^p-1).

S(0) = (M-10)/3 and
S(i+1) = S(i)^2 - 2 (mod M) ;

M is prime iff S(p-1) == S(0) .

How did you find this starting value (M-10)/3 ???
About the S(0)=(9+1/9) I proposed, with: S(i+1)=S(i)^2-2 (mod M_q) as usual, there is a proof saying: if M_q is prime then S(q-1)=S(0) .
Do you have such a proof ?

Tony

2006-05-30, 12:52	#45
alpertron Aug 2002 Buenos Aires, Argentina 2·683 Posts	For Mersenne primes we have: $q = 2^p-1$ where both $p$ and $q$ are primes. From Fermat's Little Theorem we have $a^{q-1} \equiv 1 \pmod q$ The question now is to find $r \equiv a^{(q-1)/p} \pmod q$ From both equations we have: $r^p \equiv 1\pmod q$ This diophantine equation has at most $p$ roots because the polynomial modulo a prime has degree $p$ . It's easy to see that all roots have the form $2^n\pmod q$ for $0\le n<p$ because: $(2^n)^p \equiv (2^p)^n \equiv 1^n \equiv 1\pmod q$ Notice that the numbers $2^n\pmod q$ in the given range of $n$ are all different because $2^n < q$ . Since we found $p$ roots these are the complete set of possible values of $r$ . Of course $r$ is one of these roots. So r must be a power of 2 modulo q as stated in the conjecture. Last fiddled with by alpertron on 2006-05-30 at 12:55

2006-05-30, 16:12	#47
AntonVrba Jun 2005 2·7² Posts	The Conjecture could be generalised Let p be a prime integer and Q = (b^p-1)/(b-1) or Q=(b^p+1)/(b+1) Let x=(Q-1)/p and y be an integer GCD[y,b]==1 y^x = r (mod Q) if b even and r is odd then r=Q-r if b odd and r is even then r=Q-r Q is prime iff r==b^z , z a integer. Last fiddled with by AntonVrba on 2006-05-30 at 16:47

2006-05-30, 20:14	#53
alpertron Aug 2002 Buenos Aires, Argentina 2×683 Posts	You can use the same steps that I've given above in order to show that: For prime Q = (b^p-1)/(b-1) you get r = bⁿ (mod Q) For prime Q = (b^p+1)/(b+1) you get r = b²ⁿ (mod Q) or r = -b^2n-p (mod Q) Last fiddled with by alpertron on 2006-05-30 at 20:15

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Modifying the Lucas Lehmer Primality Test into a fast test of nothing	Trilo	Miscellaneous Math	25	2018-03-11 23:20
Conjectured Primality Test for Specific Class of Mersenne Numbers	primus	Miscellaneous Math	1	2014-10-12 09:25
Conjectured Primality Test for Specific Class of k6^n-1	primus	Computer Science & Computational Number Theory	16	2014-08-15 01:15
there is another way to test the primality of a no	shawn	Miscellaneous Math	5	2007-07-17 17:55
A primality test for Fermat numbers faster than Pépin's test ?	T.Rex	Math	0	2004-10-26 21:37

2006-05-30, 15:13	#46
alpertron Aug 2002 Buenos Aires, Argentina 2·683 Posts	For prime numbers of the form $q=(2^p+1)/3$ where $p$ is prime: From Fermat's Little Theorem we have $a^{q-1} \equiv 1\pmod q$ The question now is to find $r = a^{(q-1)/p}$ $r^p \equiv 1\pmod q$ The polynomial $r^p - 1$ modulo a prime has at most $p$ roots because its degree is $p$ . It's easy to see that the roots have the form $2^{2n}\pmod q$ for $0\le n<p$ because: $(2^{2n})^p \equiv (2^{2p})^n \equiv ((2^{2p}-1)+1)^n \equiv ((2^p-1)(2^p+1)+1)^n \equiv 1^n \equiv 1$ . The penultimate step is correct because $2^p+1 \equiv 0\pmod q$ . Now notice that $2^p+1 \equiv 0$ , so $2^p \equiv -1$ . Then $2^{2n} \equiv -2^{2n-p}$ So the roots have the form $2^{2n}$ or $-2^{2n-p}$ Since all exponents are in the range $0\le n<p$ , all values are different. Since we found $p$ roots these are the complete set of possible values of $r$ . Of course $r$ is one of these roots. So $r$ must be a power of 2 or the negative of a power of 2. In the last case the result mod $q$ will be odd (because odd - even = odd).

2006-05-30, 16:26	#48
alpertron Aug 2002 Buenos Aires, Argentina 556₁₆ Posts	The new conjecture appears to be wrong. Let b=3 and p=5. We get q=(3⁵+1)/(3+1) = 61. So all numbers are prime. Now let y = 4, so gcd(y, b) = 1 as stated. x = (q-1)/p = (61-1)/5 = 12 r = y^x = 4^12 = 20 (mod 61) Since b is odd and r is even we take r = 61-20 = 41 which is not a power of 3.

2006-05-30, 18:21	#49
ewmayer ∂²ω=0 Sep 2002 República de California 103·113 Posts	Editorial Note: I've merged all these related threads into a single one. -EWM

2006-05-30, 19:33	#51
alpertron Aug 2002 Buenos Aires, Argentina 2526₈ Posts	Tony is right. The latest posts use pseudoprimality tests and are related to a conjecture that states that the Mersenne numbers and the numbers of the form (2^p+1)/3 are primes if they pass these tests. This is not related in any way to LLT.