In
mathematics
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
, two
integer
An integer is the number zero (), a positive natural number (, , , etc.) or a negative integer with a minus sign (−1, −2, −3, etc.). The negative numbers are the additive inverses of the corresponding positive numbers. In the language ...
s and are coprime, relatively prime or mutually prime if the only positive integer that is a
divisor
In mathematics, a divisor of an integer n, also called a factor of n, is an integer m that may be multiplied by some integer to produce n. In this case, one also says that n is a multiple of m. An integer n is divisible or evenly divisible by ...
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 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 because the only ways ...
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 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
An irreducible fraction (or fraction in lowest terms, simplest form or reduced fraction) is a fraction in which the numerator and denominator are integers that have no other common divisors than 1 (and −1, when negative numbers are considered). ...
are coprime, by definition.
Notation and testing
Standard notations for relatively prime integers and are: and . In their 1989 textbook ''
Concrete Mathematics
''Concrete Mathematics: A Foundation for Computer Science'', by Ronald Graham, Donald Knuth, and Oren Patashnik, first published in 1989, is a textbook that is widely used in computer-science departments as a substantive but light-hearted treatme ...
'',
Ronald Graham
Ronald Lewis Graham (October 31, 1935July 6, 2020) was an American mathematician credited by the American Mathematical Society as "one of the principal architects of the rapid development worldwide of discrete mathematics in recent years". He ...
,
Donald Knuth
Donald Ervin Knuth ( ; born January 10, 1938) is an American computer scientist, mathematician, and professor emeritus at Stanford University. He is the 1974 recipient of the ACM Turing Award, informally considered the Nobel Prize of computer sc ...
, 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 Center for Communications Research, La Jol ...
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 of two nonnegative integers. Stein's algorithm uses simpler arithmetic operations than the conv ...
or
Lehmer's GCD algorithm
Lehmer's GCD algorithm, named after Derrick Henry Lehmer, is a fast 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 digits relative to some ...
.
The number of integers coprime with a positive integer , between 1 and , is given by
Euler's totient function, also known as Euler's phi function, .
A
set
Set, The Set, SET or SETS may refer to:
Science, technology, and mathematics Mathematics
*Set (mathematics), a collection of elements
*Category of sets, the category whose objects and morphisms are sets and total functions, respectively
Electro ...
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 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 because the only ways ...
divides both and .
*There exist integers and such that (see
Bézout's identity
In mathematics, Bézout's identity (also called Bézout's lemma), named after Étienne Bézout, is the following theorem:
Here the greatest common divisor of and is taken to be . The integers and are called Bézout coefficients for ; they ...
).
*The integer has a
multiplicative inverse
In mathematics, a multiplicative inverse or reciprocal for a number ''x'', denoted by 1/''x'' or ''x''−1, is a number which when Multiplication, multiplied by ''x'' yields the multiplicative identity, 1. The multiplicative inverse of a rat ...
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'' (alb ...
in the
ring
Ring may refer to:
* Ring (jewellery), a round band, usually made of metal, worn as ornamental jewelry
* To make a sound with a bell, and the sound made by a bell
:(hence) to initiate a telephone connection
Arts, entertainment and media Film and ...
of
integers modulo .
*Every pair of
congruence relation
In abstract algebra, a congruence relation (or simply congruence) is an equivalence relation on an algebraic structure (such as a group, ring, or vector space) that is compatible with the structure in the sense that algebraic operations done wi ...
s for an unknown integer , of the form and , has a solution (
Chinese remainder theorem); in fact the solutions are described by a single congruence relation modulo .
*The
least common multiple
In arithmetic and number theory, the least common multiple, lowest common multiple, or smallest common multiple of two integers ''a'' and ''b'', usually denoted by lcm(''a'', ''b''), is the smallest positive integer that is divisible by bo ...
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
Mod, MOD or mods may refer to:
Places
* Modesto City–County Airport, Stanislaus County, California, US
Arts, entertainment, and media Music
* Mods (band), a Norwegian rock band
* M.O.D. (Method of Destruction), a band from New York City, US ...
''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 algebra and number theory, Euclid's lemma is a lemma that captures a fundamental property of prime numbers, namely:
For example, if , , , then , and since this is divisible by 19, the lemma implies that one or both of 133 or 143 must be as we ...
, 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 would be "visible" via an unobstructed line of sight from the origin (0,0), in the sense that there is no point with integer coordinates anywhere 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 concerning numerical descriptions of how likely an Event (probability theory), event is to occur, or how likely it is that a proposition is true. The probability of an event is a number between 0 and ...
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 ordering (as in "this is the ''third'' largest city in the country").
Numbers used for counting are called ''Cardinal n ...
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 ''n'' > 1:
:
Coprimality in sets
A
set
Set, The Set, SET or SETS may refer to:
Science, technology, and mathematics Mathematics
*Set (mathematics), a collection of elements
*Category of sets, the category whose objects and morphisms are sets and total functions, respectively
Electro ...
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.
It is possible for an
infinite set
In set theory, an infinite set is a set that is not a finite set. Infinite sets may be countable or uncountable.
Properties
The set of natural numbers (whose existence is postulated by the axiom of infinity) is infinite. It is the only set th ...
of integers to be pairwise coprime. Notable examples include the set of all prime numbers, the set of elements in
Sylvester's sequence
In number theory, Sylvester's sequence is an integer sequence in which each term of the sequence is the product of the previous terms, plus one. The first few terms of the sequence are
:2, 3, 7, 43, 1807, 3263443, 10650056950807, 11342371305542184 ...
, and the set of all
Fermat numbers
In mathematics, a Fermat number, named after Pierre de Fermat, who first studied them, is a positive integer of the form
:F_ = 2^ + 1,
where ''n'' is a non-negative integer. The first few Fermat numbers are:
: 3, 5, 17, 257, 65537, 42949672 ...
.
Coprimality in ring ideals
Two
ideals ''A'' and ''B'' in a
commutative ring ''R'' are called coprime (or ''comaximal'') if ''A'' + ''B'' = ''R''. This generalizes
Bézout's identity
In mathematics, Bézout's identity (also called Bézout's lemma), named after Étienne Bézout, is the following theorem:
Here the greatest common divisor of and is taken to be . The integers and are called Bézout coefficients for ; they ...
: with this definition, two
principal ideal
In mathematics, specifically ring theory, a principal ideal is an ideal I in a ring R that is generated by a single element a of R through multiplication by every element of R. The term also has another, similar meaning in order theory, where ...
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 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 mathematics, the fundamental theorem of arithmetic, also called the unique factorization theorem and prime factorization theorem, states that every integer greater than 1 can be represented uniquely as a product of prime numbers, up to the ord ...
).
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 (zeta), is a mathematical function of a complex variable defined as \zeta(s) = \sum_^\infty \frac = \frac + \frac + \frac + \cdots for \operatorname(s) > ...
, the identity relating the product over primes to ''ζ''(2) is an example of an
Euler product In 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 the sum of all positive integers raised to a certain power as proven by Leonhard Eu ...
, and the evaluation of ''ζ''(2) as ''π''
2/6 is the
Basel problem
The Basel problem is a problem in mathematical analysis with relevance to number theory, concerning an infinite sum of inverse squares. It was first posed by Pietro Mengoli in 1650 and solved by Leonhard Euler in 1734, and read on 5 December 1735 ...
, solved by
Leonhard Euler
Leonhard Euler ( , ; 15 April 170718 September 1783) was a Swiss mathematician, physicist, astronomer, geographer, logician and engineer who founded the studies of graph theory and topology and made pioneering and influential discoveries in ma ...
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, natural density (also referred to as asymptotic density or arithmetic density) is one method to measure how "large" a subset of the set of natural numbers is. It relies chiefly on the probability of encountering members of the de ...
''. 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
![Coprime8](https://upload.wikimedia.org/wikipedia/commons/2/26/Coprime8.svg)
All pairs of positive coprime numbers
(with
) can be arranged in two disjoint complete
ternary tree
:
In computer science, a ternary tree is a tree data structure in which each node has at most three child nodes, usually distinguished as "left", “mid” and "right". Nodes with children are parent nodes, and child nodes may contain references ...
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 circular machine part having cut teeth or, in the case of a cogwheel or gearwheel, inserted teeth (called ''cogs''), which mesh with another (compatible) toothed part to transmit (convert) torque and speed. The basic ...
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'', "study", respectively), is the practice and study of techniques for secure communication in the presence of adver ...
, 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, a rotor machine is an electro-mechanical stream cipher device used for encrypting and decrypting messages. Rotor machines were the cryptographic state-of-the-art for much of the 20th century; they were in widespread use in the 19 ...
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, a polynomial is an expression consisting of indeterminates (also called variables) and coefficients, that involves only the operations of addition, subtraction, multiplication, and positive-integer powers of variables. An exa ...
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.
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 , ...
*
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. The term has fallen out of use in modern pure mathematics, but continues to be use ...
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