Coprime integers

In number theory, two integers a and b are said to be relatively prime, mutually prime,[1] or coprime (also written co-prime) if the only positive integer (factor) that divides both of them is 1. Consequently, any prime number that divides one does not divide the other. This is equivalent to their greatest common divisor (gcd) being 1.[2]

The numerator and denominator of a reduced fraction are coprime. As specific examples, 14 and 15 are coprime, being commonly divisible only by 1, while 14 and 21 are not coprime, because they are both divisible by 7.

Standard notations for relatively prime integers a and b are: gcd(a, b) = 1 and (a, b) = 1. Graham, Knuth and Patashnik have proposed that the notation be used to indicate that a and b are relatively prime and that the term "prime" be used instead of coprime (as in a is prime to b).[3]

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 (or Euler's phi function) φ(n).

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 a and b are coprime for every pair (a, b) of different integers in the set. The set {2, 3, 4} 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 to every integer, and they are the only integers that are coprime with 0.

A number of conditions are equivalent to a and b being coprime:

As a consequence of the third point, if a and b are coprime and brbs (mod a), then rs (mod a).[5] That is, we may "divide by b" when working modulo a. Furthermore, if b1 and b2 are both coprime with a, then so is their product b1b2 (i.e., modulo a it is a product of invertible elements, and therefore invertible);[6] 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 bm.

If a and b are coprime and a divides the product bc, then a divides c.[7] This can be viewed as a generalization of Euclid's lemma.

Figure 1. The numbers 4 and 9 are coprime. Therefore, the diagonal of a 4 × 9 lattice does not intersect any other lattice points

The two integers a and b are coprime if and only if the point with coordinates (a, b) in a Cartesian coordinate system 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 that two randomly chosen integers are coprime is 6/π2 (see pi), 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.[8] As a generalization of this, following easily from the Euclidean algorithm in base n > 1:

Other Languages
العربية: أولية نسبيا
বাংলা: সহ-মৌলিক
Ελληνικά: Σχετικά πρώτοι
emiliàn e rumagnòl: Intēr coprìm
Esperanto: Interprimo
فارسی: متباین
Bahasa Indonesia: Koprima (bilangan)
íslenska: Ósamþátta
italiano: Interi coprimi
മലയാളം: സഹ-അഭാജ്യം
Nederlands: Relatief priem
日本語: 互いに素
Plattdüütsch: Relativ prim
Simple English: Coprime
slovenčina: Nesúdeliteľnosť
slovenščina: Tuje število
srpskohrvatski / српскохрватски: Uzajamno prosti brojevi
粵語: 相對質數
中文: 互質