In
number theoryNumber theory is a branch of pure mathematics devoted primarily to the study of the integers. Number theorists study prime numbers as well...
, a branch of
mathematicsMathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
, two
integerThe integers are formed by the natural numbers together with the negatives of the nonzero natural numbers .They are known as Positive and Negative Integers respectively...
s
a and
b are said to be
coprime (also spelled
coprime) or
relatively prime if the only positive integer that evenly divides both of them is 1. This is the same thing as their
greatest common divisorIn mathematics, the greatest common divisor , also known as the greatest common factor , or highest common factor , of two or more nonzero integers, is the largest positive integer that divides the numbers without a remainder.For example, the GCD of 8 and 12 is 4.This notion can be extended to...
being 1. In addition to
and
the notation
a b is sometimes used to indicate that
a and
b are relatively prime.
For example, 14 and 15 are coprime, being commonly divisible by only 1, but 14 and 21 are not, because they are both divisible by 7. The numbers 1 and −1 are coprime to every integer, and they are the only integers to be coprime with 0.
A fast way to determine whether two numbers are coprime is given by the
Euclidean algorithmIn mathematics, the Euclidean algorithm is an efficient method for computing the greatest common divisor of two integers, also known as the greatest common factor or highest common factor...
.
The number of integers coprime to a positive integer
n, between 1 and
n, is given by
Euler's totient functionIn number theory, the totient \varphi of a positive integer n is defined to be the number of positive integers less than or equal to n that are coprime to n In number theory, the totient \varphi(n) of a positive integer n is defined to be the number of positive integers less than or equal to n that...
(or Euler's phi function)
φ(
n).
Properties
There are a number of conditions which are equivalent to
a and
b being coprime:
 No prime number
A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. A natural number greater than 1 that is not a prime number is called a composite number. For example 5 is prime, as only 1 and 5 divide it, whereas 6 is composite, since it has the divisors 2...
divides both a and b.
 There exist integers x and y such that ax + by = 1 (see Bézout's identity
In number theory, Bézout's identity for two integers a, b is an expressionwhere x and y are integers , such that d is a common divisor of a and b. Bézout's lemma states that such coefficients exist for every pair of nonzero integers...
).
 The integer b has a multiplicative inverse modulo a: there exists an integer y such that by ≡ 1 (mod a). In other words, b is a unit
In mathematics, an invertible element or a unit in a ring R refers to any element u that has an inverse element in the multiplicative monoid of R, i.e. such element v that...
in the ringIn mathematics, a ring is an algebraic structure consisting of a set together with two binary operations usually called addition and multiplication, where the set is an abelian group under addition and a semigroup under multiplication such that multiplication distributes over addition...
Z/aZ of integers moduloIn mathematics, modular arithmetic is a system of arithmetic for integers, where numbers "wrap around" after they reach a certain value—the modulus....
a.
 Every pair of congruence relation
In abstract algebra, a congruence relation is an equivalence relation on an algebraic structure that is compatible with the structure...
s for an unknown integer x, of the form x ≡ k (mod a) and x ≡ l (mod b), has a solution, as stated by the Chinese remainder theoremThe Chinese remainder theorem is a result about congruences in number theory and its generalizations in abstract algebra.In its most basic form it concerned with determining n, given the remainders generated by division of n by several numbers...
; in fact the solutions are described by a single congruence relation modulo ab.
As a consequence of the third point, if a
and b
are coprime and br
≡ bs
(modIn mathematics, modular arithmetic is a system of arithmetic for integers, where numbers "wrap around" after they reach a certain value—the modulus....
a
), then r
≡ s
(mod a
) (because 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} (modulo a
it is a product of invertible elements, and therefore invertible); this also follows from the first point by Euclid's lemmaIn mathematics, Euclid's lemma is an important lemma regarding divisibility and prime numbers. In its simplest form, the lemma states that a prime number that divides a product of two integers must divide one of the two integers...
, 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
^{}l
.
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 systemA Cartesian coordinate system specifies each point uniquely in a plane by a pair of numerical coordinates, which are the signed distances from the point to two fixed perpendicular directed lines, measured in the same unit of length...
is "visible" from the origin (0,0), in the sense that there is no point with integer coordinates between the origin and (a
, b
). (See figure 1.)
In a sense that can be made precise, the probabilityProbability is ordinarily used to describe an attitude of mind towards some proposition of whose truth we arenot certain. The proposition of interest is usually of the form "Will a specific event occur?" The attitude of mind is of the form "How certain are we that the event will occur?" The...
that two randomly chosen integers are coprime is 6/π^{2} (see pi' is a mathematical constant that is the ratio of any circle's circumference to its diameter. is approximately equal to 3.14. Many formulae in mathematics, science, and engineering involve , which makes it one of the most important mathematical constants...
), which is about 61%. See below.
Two natural numberIn mathematics, the natural numbers are the ordinary whole numbers used for counting and ordering . These purposes are related to the linguistic notions of cardinal and ordinal numbers, respectively...
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 Euclidean algorithmIn mathematics, the Euclidean algorithm is an efficient method for computing the greatest common divisor of two integers, also known as the greatest common factor or highest common factor...
in baseIn mathematical numeral systems, the base or radix for the simplest case is the number of unique digits, including zero, that a positional numeral system uses to represent numbers. For example, for the decimal system the radix is ten, because it uses the ten digits from 0 through 9.In any numeral...
n
> 1:

Cross notation, group
If n
≥1 and is an integerThe integers are formed by the natural numbers together with the negatives of the nonzero natural numbers .They are known as Positive and Negative Integers respectively...
, the numbers coprime to n
, taken moduloIn mathematics, modular arithmetic is a system of arithmetic for integers, where numbers "wrap around" after they reach a certain value—the modulus....
n
, form a groupIn mathematics, a group is an algebraic structure consisting of a set together with an operation that combines any two of its elements to form a third element. To qualify as a group, the set and the operation must satisfy a few conditions called group axioms, namely closure, associativity, identity...
with multiplication as operation; it is written as (Z/nZ)
^{×} or
Z_{n}^{*}.
Generalizations
Two ideals
A and
B in the
commutative ringIn ring theory, a branch of abstract algebra, a commutative ring is a ring in which the multiplication operation is commutative. The study of commutative rings is called commutative algebra....
R are called
coprime (or
comaximal) if
A +
B =
R. This generalizes
Bézout's identityIn number theory, Bézout's identity for two integers a, b is an expressionwhere x and y are integers , such that d is a common divisor of a and b. Bézout's lemma states that such coefficients exist for every pair of nonzero integers...
: with this definition, two
principal idealIn ring theory, a branch of abstract algebra, a principal ideal is an ideal I in a ring R that is generated by a single element a of R.More specifically:...
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 theoremThe Chinese remainder theorem is a result about congruences in number theory and its generalizations in abstract algebra.In its most basic form it concerned with determining n, given the remainders generated by division of n by several numbers...
is an important statement about coprime ideals.
The concept of being relatively prime can also be extended to any
finite set of integers
S = {
a_{1},
a_{2}, ....
a_{n}} to mean that the
greatest common divisorIn mathematics, the greatest common divisor , also known as the greatest common factor , or highest common factor , of two or more nonzero integers, is the largest positive integer that divides the numbers without a remainder.For example, the GCD of 8 and 12 is 4.This notion can be extended to...
of the elements of the set is 1. If every pair in a (finite or
infinite) set of integers is relatively prime, then the set is called pairwise relatively prime.
Every pairwise relatively prime finite set is relatively prime; however, the converse is not true: {6, 10, 15} is relatively prime, but not pairwise relative prime (in fact, each pair of integers in the set has a nontrivial common factor).
Probabilities
Given two randomly chosen integers
and
, it is reasonable to ask how likely it is that
and
are coprime. In this determination, it is convenient to use the characterization that
and
are coprime if and only if no prime number divides both of them (see
Fundamental theorem of arithmeticIn number theory, the fundamental theorem of arithmetic states that any integer greater than 1 can be written as a unique product of prime numbers...
).
Intuitively, the probability that any number is divisible by a prime (or any integer),
is
(for example, every 7th integer is divisible by 7.) Hence the probability that two numbers are both divisible by this prime is
, and the probability that at least one of them is not is
. Now, for distinct primes, these divisibility events are mutually independent. (This would not, in general, be true if they were not prime.) (For the case of two events, a number is divisible by
p and
q if and only if it is divisible by
pq; the latter has probability 1/
pq.) Thus the probability that two numbers are coprime is given by a product over all primes,

Here
ζ refers to the
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 name arose from the case of the Riemann zetafunction, where such a product representation was proved by Leonhard Euler.Definition:...
, and the evaluation of
ζ(2) as
π^{2}/6 is the
Basel problemThe Basel problem is a famous problem in mathematical analysis with relevance to number theory, first posed by Pietro Mengoli in 1644 and solved by Leonhard Euler in 1735. Since the problem had withstood the attacks of the leading mathematicians of the day, Euler's solution brought him immediate...
, solved by
Leonhard EulerLeonhard Euler was a pioneering Swiss mathematician and physicist. He made important discoveries in fields as diverse as infinitesimal calculus and graph theory. He also introduced much of the modern mathematical terminology and notation, particularly for mathematical analysis, such as the notion...
in 1735. In general, the probability of
k randomly chosen integers being coprime is 1/
ζ(
k).
There is often confusion about what a "randomly chosen integer" is. One way of understanding this is to assume that the integers are chosen randomly between 1 and an integer
N. Then, for each upper bound
N, there is a probability
P_{N} that two randomly chosen numbers are coprime. This will never be exactly
, but in the limit as
,
.
Generating all coprime pairs
All pairs of coprime numbers
can be generated in a parent3 children9 grandchildren... family tree starting from
(for evenodd or oddeven pairs) or from
(for oddodd pairs), with three branches from each node. The branches are generated as follows:
Branch 1:
and
Branch 2:
and
Branch 3:
and
This family tree is exhaustive and nonredundant with no invalid members.