# Coprime

 related topics {math, number, function}

In mathematics, two integers a and b are said to be coprime (also spelled co-prime) 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  $\perp$  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 brbs (mod a), then rs (mod a) (because we may "divide by b" when working modulo a). Furthermore, if a and b1 are coprime, and a and b2 are coprime, then a and b1b2 are also coprime (because the product of units is a unit).

Another consequence is that if ba-1 ≡ 1 mod a, then a and ba-1 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.)