HOME

TheInfoList




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 ...

divisor
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 ...

greatest common divisor
(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 ...

Ronald Graham
,
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 a\perp b 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 ...

least common multiple
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 ...

probability
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 ...

base
''n'' > 1: : \gcd\left(n^a - 1, n^b - 1\right) = 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 ...

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 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) p is 1/p; for example, every 7th integer is divisible by 7. Hence the probability that two numbers are both divisible by ''p'' is 1/p^2, and the probability that at least one of them is not is 1-1/p^2. 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, : \prod_ \left(1-\frac\right) = \left( \prod_ \frac \right)^ = \frac = \frac \approx 0.607927102 \approx 61\%. 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 ...

Riemann zeta function
, 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 ) ...

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 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 6/\pi^2 exactly, with work one can show that in the limit as N \to \infty, the probability P_N approaches 6/\pi^2. More generally, the probability of ''k'' randomly chosen integers being coprime is 1/.


Generating all coprime pairs

All pairs of positive coprime numbers (m, n) (with m > n) 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 ...

ternary tree
s, one tree starting from (2,1) (for even–odd and odd–even pairs), and the other tree starting from (3,1) (for odd–odd pairs). The children of each vertex (m,n) are generated as follows: *Branch 1: (2m-n,m) *Branch 2: (2m+n,m) *Branch 3: (m+2n,n) 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 ...

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 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 (''- ...

cryptography
, 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 \mathbb; 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 ...

polynomial
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