Skip to content

Finding Coprime Pairs

April 29, 2018
tags: , , , , , , ,


Deferring or avoiding randomization

Great Discoveries in STEM source

Claude Bachet de Méziriac was a French mathematician of the early 1600s. He is the first person we know to have posed and solved the problem, given relatively prime (also called coprime) integers {x} and {y}, of finding integers {a} and {b} such that {ax + by = 1}.

Today we revisit some questions about generating coprime pairs deterministically.

Étienne Bézout later observed that for all cases of {\gcd(x,y) = d} there are integers {a,b} such that {ax + by = d}. The convention of naming this identity for Bézout now extends to the {d = 1} case, so that {a} and {b} are called the Bézout coefficients of {x} and {y}. If we count {1} and {-1} as being coprime with every integer (including zero) then {x,y} are coprime if and only if {a,b} making {ax + by = 1} exist.

Bachet de Méziriac is known mostly for two books. One in 1612 was a compilation whose title translates to Pleasant and Delectable Problems Fashioned By Numbers and which inspired subsequent books on mathematical recreations. The other was his translation of the Arithmetica of Diophantus from Greek into Latin. It made a marginal contribution to number theory: it contributed the margin in which Pierre Fermat wrote the statement of his famous theorem.

Coprime Pairs

Say we are given a fairly large integer {N} and wish to find coprime pairs {x,y} near it. It is of course easier to find them by random guessing than to find primes. The primes up to {N} have density only about {1/\ln(N)} but the chance of finding a coprime pair approaches about 61%. More exactly it approaches {6/\pi^2} which is the reciprocal of {\zeta(2)}.

The connection extends to other values of the zeta function. Let us take the naturally-extended Bachet condition to be the definition of {k} integers {x_1,\dots,x_k} being relatively prime: there exist integers {a_1,\dots,a_k} such that {a_1 x_1 + \cdots a_k x_k = 1}. The probability that drawing each {x_i} from {[N]} uniformly at random (with replacement) satisfies this condition approaches {1/\zeta(k)} as {N \rightarrow \infty}.

We can use Bachet’s condition to extend the logic for {k = 1}. We might have no idea what it should mean for one number {x_1} to be “coprime” but {a_1 x_1 = 1} is satisfiable for integer {a_1} only when {x_1 = 1} and {x_1 = -1}. The probability of drawing {1} from {[N]} goes to zero, which is consonant with the series for {\zeta(1)} diverging to {\infty}.

For {k = 0} it is less clear whether to apply the convention that an empty sum is zero. This would be consonant with the literal reading of “{\zeta(0)}” as {\sum_{n=1}^\infty \frac{1}{n^0} = 1 + 1 + 1 + \cdots = \infty} but not with the analytic continuation {\zeta(0) = -\frac{1}{2}}. The latter would give {1/\zeta(0) = -2} as a “probability.” We wonder idly whether Bachet’s condition helps toward a liberalized interpretation that would further give a sensible relation to {\zeta(s)} for fractional real values of {s} and then to complex ones.

But we digress. We want to generate coprime pairs efficiently and deterministically without any guessing.

Finding Primes and Coprime Pairs

The PolyMath8 project on “Bounded gaps between primes” generated many interesting sub-projects. Some of them address the issue that if {N} is in the middle of a large gap between primes then simple search up or down will fail. We have blogged about the discovery that searches for primes to use in RSA keys follow the same trajectory to find the same primes so often that simple {\gcd} calls break many keys.

There are various ways to weaken the problem. We can ask to find an integer near {N} that is a prime power. We can ask to find, say, a set {S} of 100 numbers near {N} such that at least 67 of them are prime. Note that we do not allow randomness in the solution to find {S}.

In general we want to improve randomized assertions of the form, “there is probability at least {r} of finding {X} with property {P}” to “we build a relatively small set {S} of which at least {r|S|} of the members have property {P}.” We can then decide whether drawing randomly from {S} or searching through {S} is a better policy, informed by factors such as the relative cost of testing {P}.

We have before talked about the W-trick of number theory. It maps {f_b(x) = Wx+b} where {W} is the product of all primes below a small threshold {w} and {b} is coprime to {W} (often just {b = 1}). The inverse image of the primes under {f_b} is free of biases modulo {p < w}.

This comment by Ben Green neatly expresses the analytical motivation, as does section 4 of this paper. The freedom from bias simplifies reasoning about the distribution of primes while {f_b^{-1}} preserves arithmetic progressions. We are interested in using it and similar tricks to create sets {S} as above—or sets with many coprime pairs—in conjunction with other assumptions.

Making Numbers Coprime Again

Here is our first new situation and problem. Suppose that we have two boxes that contain the numbers {x} and {y} secretly. We want to make them into co-prime numbers. We are allowed to map {x} to {x+\Delta} and map {y} to {y+\Delta'}. But we cannot see the values of {x} and {y}.

This is not easy it seems. We can weaken the goal a bit: Give a series of translations {\Delta} and {\Delta'} so that for most of them the numbers map to co-prime numbers. Note we do not allow randomness in the solution.

However, suppose that we can compute the sum {x+y=z} exactly. Then there is a method for solving this problem that is quite simple:

Pick a prime {p} that is fixed. Then find {n} so that {p^{n} > z+1}. Add {\Delta = p^{n}-z-1} to {x} and add {1} to {y}. This makes them co-prime.

The reason is simple. Note the two numbers are now

\displaystyle p^{n}-y-1 \text{ and } y+1.

Let {q} divide both of these numbers. Since both are positive {q} must be a prime—the original {x} and {y} could have been both zero. Now {q} must divide {p^{n}}. This implies that {q} is equal to {p}. And so{p} must have originally divided both {x} and {y}. So we can see now that if we move {x} and {y} to {x+i} and {y} it is the case that for most {i} in say {[1,10]} the numbers are co-prime if we select {p=13}.

Modeling Two-of-Three Coprimality

In our second situation, we are implicitly given a pair of numbers {x_1,x_2} for which we cannot determine their values. We can, however, get some partial information about them and can change them to {y,z} in a certain controlled fashion. This still may not be enough to guarantee that {y} and {z} are coprime.

So we apply our weakened goal: We want to generate a set {S} of pairs {y_j,z_j} such that at least two-thirds of the pairs in {S} are co-prime. We want the method of generating the pairs to be easy to compute and deterministic. We will do this with {|S| = 3} but hint at what is needed to expand to larger sets {S}.

Definition 1 The “2-of-3 model” problem is the following. We assume that we have two natural numbers {x_{1}} and {x_{2}}, but we have no idea what their values are. We do know the following:

  • The value of an even number {M \gg 1} which is fixed.

  • The value of the sum {x_{1} + x_{2}}.

  • There is {w_{1}} so that {x_{1} = 1 + Mw_{1}} and a {w_{2}} so that {x_{2}= 3 + Mw_{2}}.

Finally we can replace {x_{i}} by {x_{i} + M\Delta_{i}} for {i=1,2}. The goal is to find

\displaystyle \Delta_{1}^{(j)} \text{ and } \Delta_{2}^{(j)},

for {j=1,2,3} so that for at least two values of {j} the values

\displaystyle x_{1} + M\Delta_{1}^{(j)} \text{ and } x_{2} + M\Delta_{2}^{(j)}. \ \ \ \ \ (1)

are co-prime. Moreover, we want to be able to find the values {\Delta_{i}} in polynomial time.

We’ve chosen some specific constants and terms but the pattern is meant to be generalizable. For the above settings we prove:

Theorem 2 There is a polynomial time algorithm that solves the 2-of-3 model problem.

Proof: Find a prime {p} so that {p \gg 1} and {p-1} is divisible by {M}. This is possible since there are primes in such an arithmetic progression. Now we claim that there is a {\Delta} so that

\displaystyle x_{1} + x_{2} + M\Delta = 4p^{n}.

Moreover we can find this {\Delta} in polynomial time. Note that {\Delta} exists since

\displaystyle 1 + Mw_{1} + 3 + Mw_{2} + M\Delta = 4p^{n},

which is equivalent to

\displaystyle M(w_{1} + w_{2} + \Delta) = 4(p^{n}-1).

But {p^{n}-1} is divisible by {M} since {M} divides {p-1}. Thus {\Delta} exists and is easy to compute. Now let {\Delta_{1}} and {\Delta_{2}} be so that

\displaystyle \Delta = \Delta_{1} + \Delta_{2}.

Suppose that {x_{1} + M\Delta_{1}} and {x_{2} + M\Delta_{2}} have a prime {q} that divides both. Clearly {q} must be odd and thus it must divide {p^{n}} and so {q=p}. But for most splits of {\Delta} we get that this is impossible. \Box

Open Problems

What more can be said about these weaker problems of generating primes and coprime pairs?


The above results are by Dick and this post marks his return after the heart surgery six weeks ago.


The upcoming “Golden STOC” in Los Angeles will be wrapped in a 5-day TheoryFest along lines of last year’s. It will include an inaugural meeting of the TCS Women initiative. Information on travel scholarships to the TheoryFest for female graduate students. We have noticed some recent revived interest in our post a year ago on gender bias, and there is also our theme that CS has seen over its history numerous “Absolute Firsts” for women: “first X” rather than “first woman X.”

from → All Posts, History, Ideas, Oldies, primes, Results, trick
5 Comments leave one →
  1. Bruno permalink
    April 30, 2018 3:50 am

    Note that Bézout’s identity is (usually) called [Théorème de Bachet-Bézout](https://fr.wikipedia.org/wiki/Th%C3%A9or%C3%A8me_de_Bachet-B%C3%A9zout) in French.

    Reply
  2. Will permalink
    May 1, 2018 11:49 am

    I think that the problem of finding solutions to ax+by=1 and its solution goes back at least to Qin Jiushao’s “Mathematical Treatise in Nine Chapters” (1247). From Encyclopedia Britannica (https://www.britannica.com/science/East-Asian-mathematics): “His solution is known today as the Chinese remainder theorem. He dealt with the case when moduli are relatively prime, and he then reduced the case when they are not by first eliminating common factors. The first case is easily solved when x can be found that satisfies the congruence xa ≡ 1 (mod b), a and b being two given relatively prime numbers (suppose a < b). Qin gave an algorithm for this, using a sequence of quotients in searching for the greatest common divisor of a and b, which is also the sequence of convergents for the continued fraction for b/a. Having them, he was then able to compute x."

    Reply
  3. S permalink
    May 1, 2018 3:03 pm

    This was a very interesting post. Best wishes to Prof. Lipton.

    In fact, the problem of finding solutions to ax + by = c goes back at least to Aryabhata in the 5th century, who posed and solved it. Many later Indian mathematicians elaborated, extended and refined this method (called kuṭṭaka). You can read more about it here: https://en.wikipedia.org/w/index.php?title=Ku%E1%B9%AD%E1%B9%ADaka&oldid=836706571

    There’s an entire robust mathematical tradition of over a 1000 years before the early 1600s that this post starts with; it would be nice if history of mathematics did not ignore Indian / Chinese / other mathematical cultures around the world.

    Reply

Trackbacks

  1. Probability of coprime sets | simulation and exact
  2. Coprime calc – The nth Root

Leave a Reply

Discover more from Gödel's Lost Letter and P=NP

Subscribe now to keep reading and get access to the full archive.

Continue reading