Coprime

In mathematics, the integers a and b are said to be coprime or relatively prime if they have no common factor other than 1 and −1, or equivalently, if their greatest common divisor is 1.

Related Topics:
Mathematics - Integers - Factor - Greatest common divisor

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

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; 0 is coprime only to 1 and −1.

Related Topics:
6 - 35 - 27 - 1 - 0

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

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) of a positive integer n is the number of integers coprime to integers from 1 to n - 1.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~