In number theory, two integers a and b are
said to be relatively prime, mutually prime,
or coprime if the only positive integer that
evenly divides both of them is 1. That is,
the only common positive factor of the two
numbers is 1. This is equivalent to their
greatest common divisor being 1. The numerator
and denominator of a reduced fraction are
coprime. In addition to and the notation 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 algorithm.
The number of integers coprime to a positive
integer n, between 1 and n, is given by Euler's
totient function φ(n).
A set of integers can also be called coprime
if its elements share no common positive factor
except 1. A set of integers is said to be
pairwise coprime if a and b are coprime for
every pair of different integers in it.
Properties
There are a number of conditions which are
equivalent to a and b being coprime:
No prime number divides both a and b.
There exist integers x and y such that ax
+ by = 1.
The integer b has a multiplicative inverse
modulo a: there exists an integer y such that
by ≡ 1. In other words, b is a unit in the
ring Z/aZ of integers modulo a.
Every pair of congruence relations for an
unknown integer x, of the form x ≡ k and
x ≡ l, has a solution, as stated by the
Chinese remainder theorem; in fact the solutions
are described by a single congruence relation
modulo ab.
The least common multiple of a and b is equal
to their product ab, i.e. LCM(a, b) = ab.
As a consequence of the third point, if a
and b are coprime and br ≡ bs, then r ≡ s.
Furthermore, if b1 and b2 are both coprime
with a, then so is their product b1b2; this
also follows from the first point by Euclid's
lemma, 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
ak and bl.
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 in a Cartesian
coordinate system is "visible" from the origin,
in the sense that there is no point with integer
coordinates between the origin and.
In a sense that can be made precise, the probability
that two randomly chosen integers are coprime
is 6/π2, which is about 61%. See below.
Two natural numbers a and b are coprime if
and only if the numbers 2a − 1 and 2b − 1
are coprime. As a generalization of this,
following easily from Euclidean algorithm
in base n > 1:
Coprimality in sets
A set of integers S = {a1, a2, .... an} can
also be called coprime or setwise coprime
if the greatest common divisor of all the
elements of the set is 1. If every pair in
a set of integers is coprime, then the set
is said to be pairwise coprime. 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 6, 10, 15 are coprime,
but they are not pairwise coprime because
the gcd(6, 10) = 2, gcd(10, 15) = 5 and gcd(6,
15) = 3.
The concept of pairwise coprimality is important
as a hypothesis in many results in number
theory, such as the Chinese remainder theorem.
Infinite set examples
The set of all primes is pairwise coprime,
as is the set of elements in Sylvester's sequence,
and the set of all Fermat numbers.
Coprimality in ring ideals
Two ideals A and B in the commutative ring
R are called coprime if A + B = R. This generalizes
Bézout's identity: with this definition,
two principal ideals and 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 is an important
statement about coprime ideals.
Cross notation, group
If n≥1 and is an integer, the numbers coprime
to n, taken modulo n, form a group with multiplication
as operation; it is written as× or Zn*.
Probabilities
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.
Informally, the probability that any number
is divisible by a prime 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 identity relating the product over primes
to ζ(2) is an example of an Euler product,
and the evaluation of ζ(2) as π2/6 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
N, let PN be the probability that two randomly
chosen numbers in are coprime. Although PN
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 1/ζ(k).
Generating all coprime pairs
All pairs of positive coprime numbers can
be arranged in two disjoint complete ternary
trees, one tree starting from , and the other
tree starting from . 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.
See also
Superpartient number
References
Further reading
Lord, Nick, "A uniform construction of some
infinite coprime sequences", Mathematical
Gazette 92: 66–70 .
