# Does the given operation on pairs of primes always repeat?

Let $p$ and $q$ be two distinct primes. The set $$A(p,q) =\{m+n : mp+nq=1 \textrm{ and } m,n \in \mathbb{Z}\}$$ is an arithmetic progression. Its step size $p-q$ is coprime to a fixed $m+n$ because $$m(p-q)+q(m+n)= mp + nq = 1$$ Therefore, by Dirichlet's theorem on arithmetic progressions, there are an infinite number of primes in $A(p,q)$. Define $f(p,q)$ be the first two primes in $A(p,q)$.

Two examples: $f(3, 5)=(3, 5)$ and $f(3, 17)=(5, 19)$.

What happens when you repeatedly apply $f$ to a pair of primes? I have been able to show that if the pairs start to repeat, it must form a 2-cycle or a fixed point. But I have been unable to show that it must repeat.

What follows is the Mathematica 8 code I have used to test this idea. Its runtime varies wildly, but it always halts.

(* firstTwo is the first two primes on the AP *)
firstTwo[start_, delta_] := Module[{temp, a = start, b = delta, p1, p2},
If[b < 0, b = -b];
While[a < 0, a = a + b];
While[a > 0, a = a - b];
a = a + b;
While[Not[PrimeQ[a]], a = a + b];
p1 = a;
a = a + b;
While[Not[PrimeQ[a]], a = a + b];
p2 = a;
Return[{p1, p2}];
];

f[{p_, q_}] := Module[{g, m, n},
{g, {m, n}} = ExtendedGCD[p, q];
Return[firstTwo[m + n, p - q]];
];

pair = {NextPrime[RandomInteger[10^300]], NextPrime[RandomInteger[10^300]]}
While[True,
nextPair = f[pair];
Print[pair, "->", nextPair];
If[nextPair == prevPair, Break[]];
{pair, prevPair} = {nextPair, pair};
]

• For the first million or so pairs of small primes, how do the stepsize and smallest positive member grow in an iteration? How long an iteration is needed before a cycle occurs? I imagine you will get some good conjectures out of such data. I foolishly predict that the proportion of increase will happen in C out of $\phi(p-q)$ cases for some small value of C. – The Masked Avenger Aug 10 '13 at 17:09