MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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};
share|cite|improve this question
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.