## Prime chains x-->Ax+B

Expand Messages
• I wanted long chains of primes of the following kind. Want P to be prime. Want Q=4P+1 to be prime. And continue: R=4Q+1 prime, S=4R+1 prime, etc. I also was
Message 1 of 143 , Nov 11 7:50 PM
• 0 Attachment
I wanted long chains of primes of the following kind.
Want P to be prime. Want Q=4P+1 to be prime. And continue:
R=4Q+1 prime, S=4R+1 prime, etc.
I also was interested in the same thing but with -1's instead of +1's.

Examples:
+chainlength=3: 3, 13, 53
-chainlength=3: 3, 11, 43
But: There are no other 3-long-chains if the initial P is among the first 2000 primes.

This led me to prove the following easy once you see it THEOREM:
The above two examples are the unique 3-long 4x+1 and 4x-1
chains. There are no others.

PROOF:
f(x)=4x+1 always leads to a multiple of 3 after at most 2 iterations
(and ditto for 4x-1); this is seen by working mod 3; and this prevents 3 primes
in a chain unless one of the primes actually IS 3.
QED

Doh...

Similar proofs show that x-->Ax+B prime-chains are bounded in length
under various conditions:
* if B=0 then obviously not even 1 step is possible
* if B and A have a common divisor then obviously not even 1 step is possible
* if A and B have same parity then obviously not even 1 step is possible
starting from an odd prime
* otherwise if gcd(B,A-1)=1 then the linear congruential sequence generator
x-->Ax+B (mod M) will be full period M for any prime M dividing A-1
hence the chain length cannot be longer than M primes in a row...
So...

THEOREM: the only possible unboundedly long x-->Ax+B prime chains must
have B a multiple of every prime divisor of A-1,
and B nonzero, gcd(A,B)=1, and the parities of A,B must differ.

For example 2x+1, 2x-1, 3x+2, 3x+4, 3x-2, 4x+3, and 4x-3:
Fairly long chains of these sorts:

2x-1: start with 1531 or 6841, get 5 primes. With 16651 get 7 primes.
3x+2: start with 1129, get 5 primes; or 10009, get 6 primes.
5x+4: start with 263 or 1217, get 5 primes; with 5333 get 7 primes.
5x-2: start with 1229 to get 5 primes; or 4337 to get 8 primes.

One might CONJECTURE that the necessary conditions of the theorem also
suffice. It would be better to make such a conjecture after getting rather more
numerical evidence than this, though.

--
Warren D. Smith
and
math.temple.edu/~wds/homepage/works.html
• ... Suppose that we want to start with a square and get a square. Then we must solve the Diophantine equation y^2 = a*x^2 + b For any pair (a,b), Dario will
Message 143 of 143 , Jan 7, 2011
• 0 Attachment