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]]}
    nextPair = f[pair];
    Print[pair, "->", nextPair];
    If[nextPair == prevPair, Break[]];
    {pair, prevPair} = {nextPair, pair};
  • $\begingroup$ 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. $\endgroup$ – The Masked Avenger Aug 10 '13 at 17:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.