In
mathematics
Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and their changes (cal ...
, two
integer
An integer (from the Latin
Latin (, or , ) is a classical language
A classical language is a language
A language is a structured system of communication
Communication (from Latin ''communicare'', meaning "to share" or "to ...
s and are coprime, relatively prime or mutually prime if the only positive integer that is a
divisor
In mathematics
Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities a ...

of both of them is 1. Consequently, any
prime number
A prime number (or a prime) is a natural number greater than 1 that is not a Product (mathematics), product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime ...
that divides does not divide , and vice versa. This is equivalent to their
greatest common divisor
In mathematics, the greatest common divisor (GCD) of two or more integers, which are not all zero, is the largest positive integer that divides each of the integers. For two integers ''x'', ''y'', the greatest common divisor of ''x'' and ''y'' is ...

(gcd) being 1. One says also '' is prime to '' or '' is coprime with ''.
The numerator and denominator of a
reduced fraction
An irreducible fraction (or fraction in lowest terms, simplest form or reduced fraction) is a fraction
A fraction (from Latin ', "broken") represents a part of a whole or, more generally, any number of equal parts. When spoken in everyday English ...
are coprime. The numbers 14 and 25 are coprime, despite the fact that neither considered individually is a prime number, since 1 is their only common divisor. On the other hand, 14 and 21 are not coprime, because they are both divisible by 7.
Notation and testing
Standard notations for relatively prime integers and are: and . In their 1989 textbook,
Ronald Graham
Ronald Lewis Graham (October 31, 1935July 6, 2020) was an American mathematician
A mathematician is someone who uses an extensive knowledge of mathematics
Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as q ...

,
Donald Knuth
Donald Ervin Knuth ( ; born January 10, 1938) is an American computer scientist
A computer scientist is a person
A person (plural people or persons) is a being that has certain capacities or attributes such as reason, morality, consciousnes ...
, and
Oren Patashnik
Oren Patashnik (born 1954) is an American computer scientist. He is notable for co-creating BibTeX, and co-writing '' Concrete Mathematics: A Foundation for Computer Science''. He is a researcher at the Institute for Defense Analyses, Center for Co ...
proposed that the notation
be used to indicate that and are relatively prime and that the term "prime" be used instead of coprime (as in is ''prime'' to ).
A fast way to determine whether two numbers are coprime is given by the
Euclidean algorithm
In mathematics, the Euclidean algorithm,Some widely used textbooks, such as I. N. Herstein's ''Topics in Algebra'' and Serge Lang's ''Algebra'', use the term "Euclidean algorithm" to refer to Euclidean division or Euclid's algorithm, is an effi ...
and its faster variants such as
binary GCD algorithm
The binary GCD algorithm, also known as Stein's algorithm or the binary Euclidean algorithm, is an algorithm that computes the greatest common divisor
In mathematics
Mathematics (from Ancient Greek, Greek: ) includes the study of such topics ...
or
Lehmer's GCD algorithm
Lehmer's GCD algorithm, named after Derrick Henry Lehmer, is a fast greatest common divisor, GCD algorithm, an improvement on the simpler but slower Euclidean algorithm. It is mainly used for big integers that have a representation as a string of di ...
.
The number of integers coprime with a positive integer , between 1 and , is given by
Euler's totient function
In number theory
Number theory (or arithmetic or higher arithmetic in older usage) is a branch of devoted primarily to the study of the s and . German mathematician (1777–1855) said, "Mathematics is the queen of the sciences—and numbe ...
,
also known as Euler's phi function, .
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 and are coprime for every pair of different integers in the set. The set is coprime, but it is not pairwise coprime since 2 and 4 are not relatively prime.
Properties
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 and being coprime:
*No
prime number
A prime number (or a prime) is a natural number greater than 1 that is not a Product (mathematics), product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime ...
divides both and .
*There exist integers and such that (see
Bézout's identity
In elementary number theory, Bézout's identity (also called Bézout's lemma) is the following theorem
In mathematics
Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical ...
).
*The integer has a
multiplicative inverse
Image:Hyperbola one over x.svg, thumbnail, 300px, alt=Graph showing the diagrammatic representation of limits approaching infinity, The reciprocal function: . For every ''x'' except 0, ''y'' represents its multiplicative inverse. The graph forms a r ...
modulo , meaning that there exists an integer such that . In ring-theoretic language, is a
unit
Unit may refer to:
Arts and entertainment
* UNIT, a fictional military organization in the science fiction television series ''Doctor Who''
* Unit of action, a discrete piece of action (or beat) in a theatrical presentation
Music
* Unit (album), ...
in the
ring of
integers modulo .
*Every pair of
congruence relation
In abstract algebra
In algebra, which is a broad division of mathematics, abstract algebra (occasionally called modern algebra) is the study of algebraic structures. Algebraic structures include group (mathematics), groups, ring (mathematics) ...
s for an unknown integer , of the form and , has a solution (
Chinese remainder theorem
In number theory, the Chinese remainder theorem states that if one knows the remainders of the Euclidean division of an integer
An integer (from the Latin wikt:integer#Latin, ''integer'' meaning "whole") is colloquially defined as a number ...
); in fact the solutions are described by a single congruence relation modulo .
*The
least common multiple
In arithmetic
Arithmetic (from the Ancient Greek, Greek wikt:en:ἀριθμός#Ancient Greek, ἀριθμός ''arithmos'', 'number' and wikt:en:τική#Ancient Greek, τική wikt:en:τέχνη#Ancient Greek, έχνη ''tiké échne', 'a ...

of and is equal to their product , i.e. .
As a consequence of the third point, if ''a'' and ''b'' are coprime and ''br'' ≡ ''bs'' (
mod ''a''), then ''r'' ≡ ''s'' (mod ''a''). That is, we may "divide by ''b''" when working modulo ''a''. Furthermore, if ''b''
1 and ''b''
2 are both coprime with ''a'', then so is their product ''b''
1''b''
2 (i.e., modulo ''a'' it is a product of invertible elements, and therefore invertible); this also follows from the first point by
Euclid's lemma
In number theory, Euclid's lemma is a lemma that captures a fundamental property of prime number
A prime number (or a prime) is a natural number greater than 1 that is not a Product (mathematics), product of two smaller natural numbers. A na ...
, which states that if a prime number ''p'' divides a product ''bc'', then ''p'' divides at least one of the factors ''b'', ''c''.
As a consequence of the first point, if ''a'' and ''b'' are coprime, then so are any powers ''a''
''k'' and ''b''
''m''.
If ''a'' and ''b'' are coprime and ''a'' divides the product ''bc'', then ''a'' divides ''c''. This can be viewed as a generalization of Euclid's lemma.
The two integers ''a'' and ''b'' are coprime if and only if the point with coordinates (''a'', ''b'') in a
Cartesian coordinate system
A Cartesian coordinate system (, ) in a plane
Plane or planes may refer to:
* Airplane
An airplane or aeroplane (informally plane) is a fixed-wing aircraft
A fixed-wing aircraft is a heavier-than-air flying machine
Early fly ...
is "visible" from the origin (0,0), in the sense that there is no point with integer coordinates on the line segment between the origin and (''a'', ''b''). (See figure 1.)
In a sense that can be made precise, the
probability
Probability is the branch of mathematics
Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained ...

that two randomly chosen integers are coprime is , which is about 61% (see , below).
Two
natural number
In mathematics, the natural numbers are those numbers used for counting (as in "there are ''six'' coins on the table") and total order, ordering (as in "this is the ''third'' largest city in the country"). In common mathematical terminology, w ...
s ''a'' and ''b'' are coprime if and only if the numbers 2
''a'' − 1 and 2
''b'' − 1 are coprime. As a generalization of this, following easily from the
Euclidean algorithm
In mathematics, the Euclidean algorithm,Some widely used textbooks, such as I. N. Herstein's ''Topics in Algebra'' and Serge Lang's ''Algebra'', use the term "Euclidean algorithm" to refer to Euclidean division or Euclid's algorithm, is an effi ...
in
base
Base or BASE may refer to:
Brands and enterprises
* Base (mobile telephony provider), a Belgian mobile telecommunications operator
*Base CRM
Base CRM (originally Future Simple or PipeJump) is an enterprise software company based in Mountain Vie ...

''n'' > 1:
:
Coprimality in sets
A
set of integers ''S'' = can also be called ''coprime'' or ''setwise coprime'' if the
greatest common divisor
In mathematics, the greatest common divisor (GCD) of two or more integers, which are not all zero, is the largest positive integer that divides each of the integers. For two integers ''x'', ''y'', the greatest common divisor of ''x'' and ''y'' is ...

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 gcd(4, 6) = 2).
The concept of pairwise coprimality is important as a hypothesis in many results in number theory, such as the
Chinese remainder theorem
In number theory, the Chinese remainder theorem states that if one knows the remainders of the Euclidean division of an integer
An integer (from the Latin wikt:integer#Latin, ''integer'' meaning "whole") is colloquially defined as a number ...
.
It is possible for an
infinite set
In set theory
illustrating the intersection (set theory), intersection of two set (mathematics), sets.
Set theory is a branch of mathematical logic that studies Set (mathematics), sets, which informally are collections of objects. Although any ...
of integers to be pairwise coprime. Notable examples include the set of all prime numbers, the set of elements in
Sylvester's sequenceImage:Sylvester-square.svg, 300px, Graphical demonstration of the convergence of the sum 1/2 + 1/3 + 1/7 + 1/43 + ... to 1. Each row of ''k'' squares of side length 1/''k'' has total area 1/''k'', and all the squares together exactly cover a larger s ...
, and the set of all
Fermat numbers.
Coprimality in ring ideals
Two
ideals
Ideal may refer to:
Philosophy
* Ideal (ethics), values that one actively pursues as goals
* Platonic ideal, a philosophical idea of trueness of form, associated with Plato
Mathematics
* Ideal (ring theory), special subsets of a ring considered ...
''A'' and ''B'' in a
commutative ring
In , a branch of , a commutative ring is a in which the multiplication operation is . The study of commutative rings is called . Complementarily, is the study of s where multiplication is not required to be commutative.
Definition and first e ...
''R'' are called coprime (or ''comaximal'') if ''A'' + ''B'' = ''R''. This generalizes
Bézout's identity
In elementary number theory, Bézout's identity (also called Bézout's lemma) is the following theorem
In mathematics
Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical ...
: with this definition, two
principal ideal
In mathematics
Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). It ...
s (''a'') and (''b'') in the ring of integers Z are coprime if and only if ''a'' and ''b'' are coprime. If the ideals ''A'' and ''B'' of ''R'' are coprime, then ''AB'' = ''A''∩''B''; furthermore, if ''C'' is a third ideal such that ''A'' contains ''BC'', then ''A'' contains ''C''. The
Chinese remainder theorem
In number theory, the Chinese remainder theorem states that if one knows the remainders of the Euclidean division of an integer
An integer (from the Latin wikt:integer#Latin, ''integer'' meaning "whole") is colloquially defined as a number ...
can be generalized to any commutative ring, using coprime ideals.
Probability of coprimality
Given two randomly chosen integers ''a'' and ''b'', it is reasonable to ask how likely it is that ''a'' and ''b'' are coprime. In this determination, it is convenient to use the characterization that ''a'' and ''b'' are coprime if and only if no prime number divides both of them (see
Fundamental theorem of arithmetic
In number theory, the fundamental theorem of arithmetic, also called the unique factorization theorem or the unique-prime-factorization theorem, states that every integer
An integer (from the Latin wikt:integer#Latin, ''integer'' meaning "wh ...
).
Informally, the probability that any number is divisible by a prime (or in fact any integer)
is
; for example, every 7th integer is divisible by 7. Hence the probability that two numbers are both divisible by ''p'' is
, and the probability that at least one of them is not is
. 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 ''p'' and ''q'' if and only if it is divisible by ''pq''; the latter event has probability 1/''pq''. 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,
:
Here ''ζ'' refers to the
Riemann zeta function
The Riemann zeta function or Euler–Riemann zeta function, denoted by the Greek letter
The Greek alphabet has been used to write the Greek language
Greek (modern , romanized: ''Elliniká'', Ancient Greek, ancient , ''Hellēnikḗ'') is ...

, the identity relating the product over primes to ''ζ''(2) is an example of an
Euler productIn number theory, an Euler product is an expansion of a Dirichlet series into an infinite product indexed by prime numbers. The original such product was given for Proof of the Euler product formula for the Riemann zeta function, the sum of all posit ...
, and the evaluation of ''ζ''(2) as ''π''
2/6 is the
Basel problem
The Basel problem is a problem in mathematical analysis
Analysis is the branch of mathematics
Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebr ...
, solved by
Leonhard Euler
Leonhard Euler ( ; ; 15 April 170718 September 1783) was a Swiss mathematician
A mathematician is someone who uses an extensive knowledge of mathematics
Mathematics (from Greek: ) includes the study of such topics as numbers ( and ) ...

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 In number theory
Number theory (or arithmetic or higher arithmetic in older usage) is a branch of devoted primarily to the study of the s and . German mathematician (1777–1855) said, "Mathematics is the queen of the sciences—and number the ...
''. For each positive integer ''N'', let ''P''
''N'' be the probability that two randomly chosen numbers in
are coprime. Although ''P''
''N'' will never equal
exactly, with work one can show that in the limit as
, the probability
approaches
.
More generally, the probability of ''k'' randomly chosen integers being coprime is
.
Generating all coprime pairs

All pairs of positive coprime numbers
(with
) can be arranged in two disjoint complete
ternary tree
:Image:Ternary tree.png, A simple ternary tree of size 10 and height 2.
In computer science, a ternary tree is a tree data structure in which each node has at most three child Node (computer science), nodes, usually distinguished as "left", “mid ...

s, one tree starting from
(for even–odd and odd–even pairs), and the other tree starting from
(for odd–odd pairs). The children of each vertex
are generated as follows:
*Branch 1:
*Branch 2:
*Branch 3:
This scheme is exhaustive and non-redundant with no invalid members.
Applications
In machine design,
an even, uniform
gear
A gear is a rotating
A rotation is a circular movement of an object around a center (or point) of rotation. The plane (geometry), geometric plane along which the rotation occurs is called the ''rotation plane'', and the imaginary li ...

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
Cryptography, or cryptology (from grc, , translit=kryptós "hidden, secret"; and ''graphein'', "to write", or ''-logia
''-logy'' is a suffix in the English language, used with words originally adapted from Ancient Greek ending in (''- ...

,
some
Vernam cipher
Vernam is a surname. Notable people with the surname include:
*Charles Vernam (born 1996), English professional footballer
*Gilbert Vernam (1890–1960), invented an additive polyalphabetic stream cipher and later co-invented an automated one-time ...
machines combined several loops of key tape of different lengths. Many
rotor machine
In cryptography
Cryptography, or cryptology (from grc, , translit=kryptós "hidden, secret"; and ''graphein'', "to write", or ''-logia
''-logy'' is a suffix in the English language, used with words originally adapted from Ancient Gr ...
s combine rotors of different numbers of teeth.
Such combinations work best when the entire set of lengths are pairwise coprime.
[
Gustavus J. Simmons]
"Vernam-Vigenère cipher"
Generalizations
This concept can be extended to other algebraic structures than
; for example,
polynomial
In mathematics
Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). I ...

s whose
greatest common divisor
In mathematics, the greatest common divisor (GCD) of two or more integers, which are not all zero, is the largest positive integer that divides each of the integers. For two integers ''x'', ''y'', the greatest common divisor of ''x'' and ''y'' is ...
is 1 are called
coprime polynomials
In algebra, the greatest common divisor (frequently abbreviated as GCD) of two polynomial
In mathematics
Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, stru ...
.
See also
*
Euclid's orchard
In mathematics, informally speaking, Euclid's orchard is an array of one-dimensional "trees" of unit height planted at the lattice points in one quadrant of a square lattice. More formally, Euclid's orchard is the set of line segments from to , whe ...
*
Superpartient number
In mathematics, a superpartient ratio, also called superpartient number or epimeric ratio, is a rational number that is greater than one and is not superparticular number, superparticular. The term has fallen out of use in modern pure mathematics, ...
Notes
References
*
*
*
*
Further reading
*{{Citation , last=Lord , first=Nick , title=A uniform construction of some infinite coprime sequences , journal=Mathematical Gazette , volume=92 , date=March 2008 , pages=66–70 .
Number theory