In number theory, two integers Template:Mvar and Template:Mvar are coprime, relatively prime or mutually prime if the only positive integer that is a divisor of both of them is 1.<ref>Template:Cite book</ref> Consequently, any prime number that divides Template:Mvar does not divide Template:Mvar, and vice versa. This is equivalent to their greatest common divisor (GCD) being 1.<ref>Template:Harvnb</ref> One says also Template:Mvar is prime to Template:Mvar or Template:Mvar is coprime with Template:Mvar.
The numbers 8 and 9 are coprime, despite the fact that neither—considered individually—is a prime number, since 1 is their only common divisor. On the other hand, 6 and 9 are not coprime, because they are both divisible by 3. The numerator and denominator of a reduced fraction are coprime, by definition.
Notation and testingEdit
When the integers Template:Mvar and Template:Mvar are coprime, the standard way of expressing this fact in mathematical notation is to indicate that their greatest common divisor is one, by the formula Template:Math or Template:Math. In their 1989 textbook Concrete Mathematics, Ronald Graham, Donald Knuth, and Oren Patashnik proposed an alternative notation <math>a\perp b</math> to indicate that Template:Mvar and Template:Mvar are relatively prime and that the term "prime" be used instead of coprime (as in Template:Mvar is prime to Template:Mvar).<ref>Template:Citation</ref>
A fast way to determine whether two numbers are coprime is given by the Euclidean algorithm and its faster variants such as binary GCD algorithm or Lehmer's GCD algorithm.
The number of integers coprime with a positive integer Template:Mvar, between 1 and Template:Mvar, is given by Euler's totient function, also known as Euler's phi function, Template:Math.
A set of integers can also be called coprime if its elements share no common positive factor except 1. A stronger condition on a set of integers is pairwise coprime, which means that Template:Mvar and Template:Mvar are coprime for every pair Template:Math of different integers in the set. The set Template:Math is coprime, but it is not pairwise coprime since 2 and 4 are not relatively prime.
PropertiesEdit
The numbers 1 and −1 are the only integers coprime with every integer, and they are the only integers that are coprime with 0.
A number of conditions are equivalent to Template:Mvar and Template:Mvar being coprime:
- No prime number divides both Template:Mvar and Template:Mvar.
- There exist integers Template:Mvar such that Template:Math (see Bézout's identity).
- The integer Template:Mvar has a multiplicative inverse modulo Template:Mvar, meaning that there exists an integer Template:Mvar such that Template:Math. In ring-theoretic language, Template:Mvar is a unit in the ring Template:Tmath of integers modulo Template:Mvar.
- Every pair of congruence relations for an unknown integer Template:Mvar, of the form Template:Math and Template:Math, has a solution (Chinese remainder theorem); in fact the solutions are described by a single congruence relation modulo Template:Mvar.
- The least common multiple of Template:Mvar and Template:Mvar is equal to their product Template:Mvar, i.e. Template:Math.<ref>Template:Harvnb</ref>
As a consequence of the third point, if Template:Mvar and Template:Mvar are coprime and Template:Math, then Template:Math.<ref>Template:Harvnb</ref> That is, we may "divide by Template:Mvar" when working modulo Template:Mvar. Furthermore, if Template:Math are both coprime with Template:Mvar, then so is their product Template:Math (i.e., modulo Template:Mvar it is a product of invertible elements, and therefore invertible);<ref>Template:Harvnb</ref> this also follows from the first point by Euclid's lemma, which states that if a prime number Template:Mvar divides a product Template:Mvar, then Template:Mvar divides at least one of the factors Template:Mvar.
As a consequence of the first point, if Template:Mvar and Template:Mvar are coprime, then so are any powers Template:Mvar and Template:Mvar.
If Template:Mvar and Template:Mvar are coprime and Template:Mvar divides the product Template:Mvar, then Template:Mvar divides Template:Mvar.<ref>Template:Harvnb</ref> This can be viewed as a generalization of Euclid's lemma.
The two integers Template:Mvar and Template:Mvar are coprime if and only if the point with coordinates Template:Math in a Cartesian coordinate system would be "visible" via an unobstructed line of sight from the origin Template:Math, in the sense that there is no point with integer coordinates anywhere on the line segment between the origin and Template:Math. (See figure 1.)
In a sense that can be made precise, the probability that two randomly chosen integers are coprime is Template:Math, which is about 61% (see Template:Slink, below).
Two natural numbers Template:Mvar and Template:Mvar are coprime if and only if the numbers Template:Math and Template:Math are coprime.<ref>Template:Harvnb</ref> As a generalization of this, following easily from the Euclidean algorithm in base Template:Math:
- <math>\gcd\left(n^a - 1, n^b - 1\right) = n^{\gcd(a, b)} - 1.</math>
Coprimality in setsEdit
A set of integers <math>S=\{a_1,a_2, \dots, a_n\}</math> can also be called coprime or setwise coprime if the greatest common divisor of all the elements of the set is 1. For example, the integers 6, 10, 15 are coprime because 1 is the only positive integer that divides all of them.
If every pair in a set of integers is coprime, then the set is said to be pairwise coprime (or pairwise relatively prime, mutually coprime or mutually relatively prime). Pairwise coprimality is a stronger condition than setwise coprimality; every pairwise coprime finite set is also setwise coprime, but the reverse is not true. For example, the integers 4, 5, 6 are (setwise) coprime (because the only positive integer dividing all of them is 1), but they are not pairwise coprime (because Template:Math).
The concept of pairwise coprimality is important as a hypothesis in many results in number theory, such as the Chinese remainder theorem.
It is possible for an infinite set of integers to be pairwise coprime. Notable examples include the set of all prime numbers, the set of elements in Sylvester's sequence, and the set of all Fermat numbers.
Probability of coprimalityEdit
Given two randomly chosen integers Template:Mvar and Template:Mvar, it is reasonable to ask how likely it is that Template:Mvar and Template:Mvar are coprime. In this determination, it is convenient to use the characterization that Template:Mvar and Template:Mvar are coprime if and only if no prime number divides both of them (see Fundamental theorem of arithmetic).
Informally, the probability that any number is divisible by a prime (or in fact any integer) Template:Mvar is Template:Tmath for example, every 7th integer is divisible by 7. Hence the probability that two numbers are both divisible by Template:Mvar is Template:Tmath and the probability that at least one of them is not is Template:Tmath Any finite collection of divisibility events associated to distinct primes is mutually independent. For example, in the case of two events, a number is divisible by primes Template:Mvar and Template:Mvar if and only if it is divisible by Template:Mvar; the latter event has probability Template:Tmath If one makes the heuristic assumption that such reasoning can be extended to infinitely many divisibility events, one is led to guess that the probability that two numbers are coprime is given by a product over all primes,
- <math>\prod_{\text{prime } p} \left(1-\frac{1}{p^2}\right) = \left( \prod_{\text{prime } p} \frac{1}{1-p^{-2}} \right)^{-1} = \frac{1}{\zeta(2)} = \frac{6}{\pi^2} \approx 0.607927102 \approx 61\%.</math>
Here Template:Mvar refers to the Riemann zeta function, the identity relating the product over primes to Template:Math is an example of an Euler product, and the evaluation of Template:Math as Template:Math is the Basel problem, solved by Leonhard Euler in 1735.
There is no way to choose a positive integer at random so that each positive integer occurs with equal probability, but statements about "randomly chosen integers" such as the ones above can be formalized by using the notion of natural density. For each positive integer Template:Mvar, let Template:Mvar be the probability that two randomly chosen numbers in <math>\{1,2,\ldots,N\}</math> are coprime. Although Template:Mvar will never equal Template:Math exactly, with work<ref>This theorem was proved by Ernesto Cesàro in 1881. For a proof, see Template:Harvnb</ref> one can show that in the limit as <math>N \to \infty,</math> the probability Template:Mvar approaches Template:Math.
More generally, the probability of Template:Mvar randomly chosen integers being setwise coprime is Template:Tmath
Generating all coprime pairsEdit
All pairs of positive coprime numbers Template:Math (with Template:Math) can be arranged in two disjoint complete ternary trees, one tree starting from Template:Math (for even–odd and odd–even pairs),<ref>Template:Citation.</ref> and the other tree starting from Template:Math (for odd–odd pairs).<ref>Template:Citation.</ref> The children of each vertex Template:Math are generated as follows:
- Branch 1: <math>(2m-n,m)</math>
- Branch 2: <math>(2m+n,m)</math>
- Branch 3: <math>(m+2n,n)</math>
This scheme is exhaustive and non-redundant with no invalid members. This can be proved by remarking that, if <math>(a,b)</math> is a coprime pair with <math>a>b,</math> then
- if <math>a>3b,</math> then <math>(a,b)</math> is a child of <math>(m,n)=(a-2b, b)</math> along branch 3;
- if <math>2b<a<3b,</math> then <math>(a,b)</math> is a child of <math>(m,n)=(b, a-2b)</math> along branch 2;
- if <math>b<a<2b,</math> then <math>(a,b)</math> is a child of <math>(m,n)=(b, 2b-a)</math> along branch 1.
In all cases <math>(m,n)</math> is a "smaller" coprime pair with <math>m>n.</math> This process of "computing the father" can stop only if either <math>a=2b</math> or <math>a=3b.</math> In these cases, coprimality, implies that the pair is either <math>(2,1)</math> or <math>(3,1).</math>
Another (much simpler) way to generate a tree of positive coprime pairs Template:Math (with Template:Math) is by means of two generators <math>f:(m,n)\rightarrow(m+n,n)</math> and <math>g:(m,n)\rightarrow(m+n,m)</math>, starting with the root <math>(2,1)</math>. The resulting binary tree, the Calkin–Wilf tree, is exhaustive and non-redundant, which can be seen as follows. Given a coprime pair one recursively applies <math>f^{-1}</math> or <math>g^{-1}</math> depending on which of them yields a positive coprime pair with Template:Math. Since only one does, the tree is non-redundant. Since by this procedure one is bound to arrive at the root, the tree is exhaustive.
ApplicationsEdit
In machine design, an even, uniform gear wear is achieved by choosing the tooth counts of the two gears meshing together to be relatively prime. When a 1:1 gear ratio is desired, a gear relatively prime to the two equal-size gears may be inserted between them.
In pre-computer cryptography, some Vernam cipher machines combined several loops of key tape of different lengths. Many rotor machines combine rotors of different numbers of teeth. Such combinations work best when the entire set of lengths are pairwise coprime.<ref> Klaus Pommerening. "Cryptology: Key Generators with Long Periods". </ref><ref> David Mowry. "German Cipher Machines of World War II". 2014. p. 16; p. 22. </ref><ref> Dirk Rijmenants. "Origins of One-time pad". </ref><ref> Gustavus J. Simmons. "Vernam-Vigenère cipher". </ref>
GeneralizationsEdit
Template:See also This concept can be extended to other algebraic structures than Template:Tmath for example, polynomials whose greatest common divisor is 1 are called coprime polynomials.
Coprimality in ring idealsEdit
Two ideals Template:Mvar and Template:Mvar in a commutative ring Template:Mvar are called coprime (or comaximal) if <math>A+B=R.</math> This generalizes Bézout's identity: with this definition, two principal ideals (Template:Mvar) and (Template:Mvar) in the ring of integers Template:Tmath are coprime if and only if Template:Mvar and Template:Mvar are coprime. If the ideals Template:Mvar and Template:Mvar of Template:Mvar are coprime, then <math>AB=A\cap B;</math> furthermore, if Template:Mvar is a third ideal such that Template:Mvar contains Template:Mvar, then Template:Mvar contains Template:Mvar. The Chinese remainder theorem can be generalized to any commutative ring, using coprime ideals.