# 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.)

Full article ▸

 related documents Real analysis P-complete Tree (graph theory) Nial Epimorphism Chomsky hierarchy Codomain Consistency Quotient group Referential transparency (computer science) Local field Dual number Lagrange inversion theorem Mathematical singularity Zorn's lemma Statistical independence Arithmetic shift Associativity Linear cryptanalysis Group isomorphism Elementary group theory Examples of groups Functional analysis Arithmetic function Legendre symbol Intermediate value theorem Venn diagram Grep Axiom of pairing Distributivity