User pedja - MathOverflow

Primality criteria for specific class of Wagstaff numbers ?

2012-03-16T05:28:51Z

I asked this question on mathstackexchange but didn't get any answer .

Definition :

Let $W_p$ be a Wagstaff number of the form :

$W_p=\frac{2^p+1}{3}$ , with $p\equiv 1 \pmod 4$

Next , define sequence $S_i$ as :

$S_i =8S^4_{i-1}-8S^2_{i-1}+1 $ , with $ S_0=\frac{3}{2} $

How to prove following statement :

Conjecture :

$W_p$ is a prime iff $S_{\frac{p-1}{2}} \equiv \frac{3}{2} \pmod {W_p}$

I checked statement for following Wagstaff primes :

$W_5 , W_{13} , W_{17} , W_{61} , W_{101} , W_{313} , W_{701} , W_{1709} , W_{2617} , W_{10501} , W_{42737} ,W_{95369} , W_{138937} ,W_{267017}$

Also , for $~p < 15000~$ there is no composite $W_p$ that satisfies relation from conjecture .

P.S.

I am interested in hints (not full solution) .

Lucasian Criteria for the Primality of Repunit numbers

2012-04-20T07:37:19Z

Def 1.

Let's define repunit number $R_n$ in base $10$ as :

$R_n=\frac{10^n-1}{9}$ , with $n \geq 1$

Def 2.

Next , define polynomial $P_n(x)$ as :

$P_n(x)=2^{-n} \cdot \left(\left (x-\sqrt{x^2-4} \right )^n+\left (x+\sqrt{x^2-4}\right )^n \right )$

Def 3.

Let's define sequence $S_i$ as :

$S_i=P_{10}(S_{i-1})$ with $S_0=15127$

Conjecture :

$R_n ; (n > 5) ~\text{is a prime iff }~ S_{n-1}\equiv S_0 \pmod {R_n} $

I have checked statement for following repunit primes :

$R_{19} , R_{23} , R_{317} , R_{1031} , R_{49081} $

Question :

I am interested in approaches which can be used to prove this conjecture .

P.S.

One can formulate similar conjectures for repunits in all other bases .

Conjecture on Primality of Wagstaff Numbers

2012-03-30T09:13:02Z

This question is related to my previous question .

Definition :

Let $W_p$ be a Wagstaff number of the form :

$W_p=\frac{2^p+1}{3}$ , where $p$ is a prime number .

Definition :

Let's define starting seed $S$ as :

$S = 3 ~\text{ if }~ p\equiv 1 \pmod 4 $

$S=11 ~\text{ if }~ p\equiv 1 \pmod 6 $

$S=27 ~\text{ if }~ p\equiv 11 \pmod {12} \text{ and } p \equiv 1,9 \pmod {10}$

$S=33 ~\text{ if }~ p\equiv 11 \pmod {12} \text { and } p \equiv 3,7 \pmod {10} $

Definition :

Let's define sequence $S_i$ as :

$S_i=S^4_{i-1}-4 \cdot S^2_{i-1}+2 ~\text{ with }~ S_0=S$

Conjecture :

$W_p ~; (p>3) ~\text{ is a prime iff }~ S_{\frac{p-1}{2}} \equiv S \pmod {W_p}$

I checked statement for following Wagstaff primes :

$W_5 , W_7 , W_{11} ,W_{13} , W_{17} , W_{19} , W_{23} , W_{31} , W_{43} ,W_{61} , W_{79} , W_{101} ,W_{127} , W_{167} , W_{191} , W_{199} ,W_{313} , W_{347} ,$ $W_{701} , W_{1709} ,W_{2617} , W_{3539} , W_{5807} , W_{10501} ,W_{10691} , W_{11279} ,W_{12391} , W_{14479} ,W_{42737} ,W_{83339} ,W_{95369} ,$ $W_{127031} , W_{138937} , W_{141079} , W_{267017} , W_{269987} ,W_{374321}$

According to this criteria probable prime $W_{117239}$ is a composite number .

Also , for $p < 15000$ there is no composite $W_p$ that satisfies relation from conjecture .

Question : Are there similar primality criteria for Wagstaff numbers in the literature ?

P.S.

According to this Wikipedia article the fastest algorithm for proving the primality of Wagstaff numbers is ECCP .

Primality criteria for Fermat numbers using quartic recurrence equation

2012-03-23T10:05:22Z

Let's define sequence $S_i$ as :

$ S_i= S^4_{i-1}-4\cdot S^2_{i-1}+2 ~\text{with}~ S_0=8$

I have found that :

$F_2 \mid S_1 , ~F_3 \mid S_3 ,~F_4 \mid S_7 $

where $F_2 , F_3 , F_4 $ are Fermat numbers .

Conjecture :

$ F_n = 2^{2^n}+1 ,(n \geq 2) ~\text{is a prime iff}~F_n \mid S_{2^{n-1}-1}$

In this document you can find my proof of this conjecture .

Question :

Is my proof acceptable ? Are there similar criteria in the literature ?

Primality criterion for generalized Fermat numbers similar to the LLT ?

2012-03-18T06:28:21Z

I asked this question on mathstackexchange but didn't get any answer .

Definition 1 :

Let $F_n(b) $ be a generalized Fermat number of the form :

$F_n(b) = b^{2^n}+1 $ , where $b$ is a positive even integer .

Definition 2 :

Let $T_n(S_{i-1}) $ be a Chebyshev polynomial of the first kind , i.e.

$T_n(S_{i-1}) = 2^{-1} \cdot \left(\left(S_{i-1}+\sqrt{S^2_{i-1}-1}\right)^n+\left(S_{i-1}-\sqrt{S^2_{i-1}-1}\right)^n\right ) $

How to prove following statements :

Example 1 :

Let's define sequence $S_i $ as :

$ S_i = T_{78} (S_{i-1} ) \text{ with } S_{0} = 6 $

I have found that :

$ F_1(156) \mid S_2 , ~ F_4(156) \mid S_{30} , ~ F_5(156) \mid S_{62} $

Also , no composite $ F_n(156) $ up to $n= 10 $ divides corresponding $S_i $ .

Conjecture :

$F_{n}(156) , (n \geq 1) \text{ is a prime iff } F_n(156) \mid S_{2^{n+1}-2} $

Example 2 :

Let's define sequence $S_i $ as :

$ S_i = T_{18} (S_{i-1} ) \text{ with } S_{0} = 8 $

I have found that :

$ F_2(288) \mid S_{17} , ~ F_3(288) \mid S_{37} , ~ F_4(288) \mid S_{77} $

Also , no composite $F_{n}(288) $ up to $ n=10 $ divides corresponding $S_i $ .

Conjecture :

$F_{n}(288) , (n \geq 1) \text{ is a prime iff } F_n(288) \mid S_{5 \cdot 2^n-3} $

Example 3 :

Let's define sequence $S_i $ as :

$S_i = T_{2222}(S_{i-1}) \text{ with } S_{0}=4 $

I have found that :

$ F_1(4444) \mid S_{2} , ~ F_2(4444) \mid S_{6} , ~ F_4(4444) \mid S_{30} $

Also , no composite $F_{n}(4444) $ up to $n=10 $ divides corresponding $S_i $ .

Conjecture :

$F_{n}(4444) , (n \geq 1 ) \text{ is a prime iff } F_n(4444) \mid S_{2^{n+1}-2} $

P.S.

I am interested in hints (not full solution) .

Are these polynomials irreducible over ring Z of integers ?

2011-11-10T08:40:04Z

Is it true that polynomials of the form :

$ f(x)= x^n+x^{n-1}+...+x^{k+1}+ax^k+ax^{k-1}+...a$

where $gcd(n+1,k+1)=1$ and $ a\in \mathbb{Z^{+}} $

are irreducible over ring $\mathbb{Z} $ of integers ?

Neither of Eisenstein's criterion and Cohn's criterion cannot be applied on the polynomials of this form. I have checked a lot of cases and it seems to be true.

Answer by pedja for infinite number of prime pairs

2011-09-06T08:48:40Z

maybe there is,it is not proved yet. It is a particular case of a general conjecture concerning linear equations in primes :

Conjecture : Let $a$ and $b$ two integers such that $a>0$, the product $ab$ is even and $a$ and $b$ are coprime. Then the equation $p' =ap+b$ has infinitely many solutions in pairs of prime $(p,p')$.

infinite number of prime pairs

2011-09-05T12:21:13Z

Is there infinite number of prime pairs `$(p_k,p_n)$ that satisfy equality $p_n=2p_k-3$

Comment by pedja

2012-04-20T12:55:58Z

@MarkSapir Starting seed $S_0$ isn't chosen randomly...

Comment by pedja

2012-04-20T10:31:25Z

@FranzLemmermeyer You can formulate same criterion for Mersenne numbers if you set $S_i=P_2(S_{i-1})$ , $S_0=34$ , and $n>5$

Comment by pedja

2012-04-20T08:11:21Z

@MarkSapir Because this test is fast and deterministic...

Comment by pedja

2012-04-06T04:14:23Z

@EmilJerabek On my computer Java implementation of this test is approximately $1.5$ time faster than Java implementation of Inkeri's test...

Comment by pedja

2012-04-01T04:50:45Z

codereview.stackexchange.com/…

Comment by pedja

2012-03-23T11:58:00Z

I didn't know that such test exists . As you can see my test uses lesser number of iterations .

Comment by pedja

2011-11-10T09:37:01Z

yes $k$ must be greater than $1$

Comment by pedja

2011-11-10T09:35:28Z

yes but $a_1=1$ and I am asking what if $a_1=a >1$

Comment by pedja

2011-11-10T09:32:36Z

in example above $a_0=a=21$

Comment by pedja

2011-11-10T09:29:41Z

no, $a_1$ is coefficient of the linear term...example: $ x^2+3x+3 $ where $ a_1=a=3 $

Comment by pedja

2011-11-10T09:20:47Z

you are right.what if $ a_1 \neq 1 $ and $a$ is odd number greater than $1$ ?

Comment by pedja

2011-11-10T09:10:20Z

@Carnahan,what if a is odd and greater than 1

Comment by pedja

2011-09-14T05:55:13Z

@WillJagy,Thanks for advice

Comment by pedja

2011-09-14T05:30:46Z

@WillJagy,I passed the exams which are called "algebra","calculus 1","calculus 2" at the university of electrical engineering

Comment by pedja

2011-09-09T10:23:08Z

GH,Richards (1974) proved that the first and second Hardy-Littlewood conjectures are incompatible with each other