In mathematics, the integers a and b are said to be coprime or relatively prime if they have no common factor other than 1 or, equivalently, if their greatest common divisor is 1.
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) of a positive integer n is the number of integers between 1 and n which are coprime to n.
Reference:
http://en.wikipedia.org/wiki/Coprime
