In mathematics, two integers a and b are said to be coprime (also spelled coprime) or relatively prime if they have no common positive factor other than 1 or, equivalently, if their greatest common divisor is 1.^{[1]} The notation a b is sometimes used to indicate that a and b are relatively prime.^{[2]}.
For example, 6 and 35 are coprime, but 6 and 27 are not, because they are both divisible by 3. The number 1 is coprime to every integer.
A fast way to determine whether two numbers are coprime is given by the Euclidean algorithm.
Euler's totient function (or Euler's phi function) φ(n) for a positive integer n outputs the number of integers between 1 and n which are coprime to n.
Contents
Properties
There are a number of conditions which are equivalent to a and b being coprime:
As a consequence, 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 a and b_{1} are coprime, and a and b_{2} are coprime, then a and b_{1}b_{2} are also coprime (because the product of units is a unit).
Another consequence is that if b^{a1} ≡ 1 mod a, then a and b^{a1} are coprime, hence a and b must also be coprime.
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, which states that if p is prime, and p divides a product bc, then either p divides b or p divides c.
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.)
Full article ▸
