Coprime Integers - Properties

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 (see Bézout's identity).
• 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 the ring Z/aZ of integers modulo a.
• Every pair of congruence relations 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 theorem; 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 (mod a), then r ≡ s (mod a) (because we may "divide by b" when working modulo a). Furthermore, if b₁ and b₂ are both coprime with a, then so is their product b₁b₂ (modulo a it is a product of invertible elements, and therefore invertible); 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 (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 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. As a generalization of this, following easily from Euclidean algorithm in base n > 1: