Editing Coprime integers (section)

== 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 {{mvar|a}} and {{mvar|b}} being coprime:
*No [[prime number]] divides both {{mvar|a}} and {{mvar|b}}.
*There exist integers {{mvar|x, y}} such that {{math|1=''ax'' + ''by'' = 1}} (see [[Bézout's identity]]).
*The integer {{mvar|b}} has a [[modular multiplicative inverse|multiplicative inverse]] modulo {{mvar|a}}, meaning that there exists an integer {{mvar|y}} such that {{math|''by'' ≡ 1 (mod ''a'')}}. In ring-theoretic language, {{mvar|b}} is a [[unit (ring theory)|unit]] in the [[ring (mathematics)|ring]] {{tmath|\Z/a\Z}} of [[modular arithmetic|integers modulo]] {{mvar|a}}.
*Every pair of [[congruence relation]]s for an unknown integer {{mvar|x}}, of the form {{math|''x'' &equiv; ''k'' (mod ''a'')}} and {{math|''x'' &equiv; ''m'' (mod ''b'')}}, has a solution ([[Chinese remainder theorem]]); in fact the solutions are described by a single congruence relation modulo {{mvar|ab}}.
*The [[least common multiple]] of {{mvar|a}} and {{mvar|b}} is equal to their product {{mvar|ab}}, i.e. {{math|1=lcm(''a'', ''b'') = ''ab''}}.<ref>{{harvnb|Ore|1988|loc=p. 47}}</ref>

As a consequence of the third point, if {{mvar|a}} and {{mvar|b}} are coprime and {{math|''br'' &equiv; ''bs'' (mod ''a'')}}, then {{math|''r'' &equiv; ''s'' (mod ''a'')}}.<ref>{{harvnb|Niven|Zuckerman|1966|loc=p. 22, Theorem 2.3(b)}}</ref> That is, we may "divide by {{mvar|b}}" when working modulo {{mvar|a}}. Furthermore, if {{math|''b''<sub>1</sub>, ''b''<sub>2</sub>}} are both coprime with {{mvar|a}}, then so is their product {{math|''b''<sub>1</sub>''b''<sub>2</sub>}} (i.e., modulo {{mvar|a}} it is a product of invertible elements, and therefore invertible);<ref>{{harvnb|Niven|Zuckerman|1966|loc=p. 6, Theorem 1.8}}</ref> this also follows from the first point by [[Euclid's lemma]], which states that if a prime number {{mvar|p}} divides a product {{mvar|bc}}, then {{mvar|p}} divides at least one of the factors {{mvar|b, c}}.

As a consequence of the first point, if {{mvar|a}} and {{mvar|b}} are coprime, then so are any powers {{mvar|a<sup>k</sup>}} and {{mvar|b<sup>m</sup>}}.

If {{mvar|a}} and {{mvar|b}} are coprime and {{mvar|a}} divides the product {{mvar|bc}}, then {{mvar|a}} divides {{mvar|c}}.<ref>{{harvnb|Niven|Zuckerman|1966|loc=p.7, Theorem 1.10}}</ref> This can be viewed as a generalization of Euclid's lemma.

[[Image:coprime-lattice.svg|thumb|right|300px|Figure 1. The numbers 4 and 9 are coprime. Therefore, the diagonal of a 4 × 9 lattice does not intersect any other [[square lattice|lattice points]]]]

The two integers {{mvar|a}} and {{mvar|b}} are coprime if and only if the point with coordinates {{math|(''a'', ''b'')}} in a [[Cartesian coordinate system]] would be  "visible" via an unobstructed line of sight from the origin {{math|(0, 0)}}, in the sense that there is no point with integer coordinates anywhere on the line segment  between the origin and {{math|(''a'', ''b'')}}. (See figure 1.)

In a sense that can be made precise, the [[probability]] that two randomly chosen integers are coprime is {{math|6/''π''<sup>2</sup>}}, which is about 61% (see {{slink||Probability of coprimality}}, below).

Two [[natural number]]s {{mvar|a}} and {{mvar|b}} are coprime if and only if the numbers {{math|2<sup>''a''</sup> − 1}} and {{math|2<sup>''b''</sup> − 1}} are coprime.<ref>{{harvnb|Rosen|1992|loc=p. 140}}</ref> As a generalization of this, following easily from the [[Euclidean algorithm]] in [[Radix|base]] {{math|''n'' > 1}}:

: <math>\gcd\left(n^a - 1, n^b - 1\right) = n^{\gcd(a, b)} - 1.</math>