Coprime Integers

Coprime Integers

In number theory, a branch of mathematics, two integers a and b are said to be coprime (also spelled co-prime) or relatively prime if the only positive integer that evenly divides both of them is 1. This is the same thing as their greatest common divisor being 1. In addition to and the notation a b is sometimes used to indicate that a and b are relatively prime.

For example, 14 and 15 are coprime, being commonly divisible by only 1, but 14 and 21 are not, because they are both divisible by 7. The numbers 1 and −1 are coprime to every integer, and they are the only integers to be coprime with 0.

A fast way to determine whether two numbers are coprime is given by the Euclidean algorithm.

The number of integers coprime to a positive integer n, between 1 and n, is given by Euler's totient function (or Euler's phi function) φ(n).