|Look up coprime in Wiktionary, the free dictionary.|
The numerator and denominator of a
Standard notations for relatively prime integers a and b are: gcd(a, b) = 1 and (a, b) = 1. Graham, Knuth and Patashnik have proposed that the notation be used to indicate that a and b are relatively prime and that the term "prime" be used instead of coprime (as in a is prime to b).
A fast way to determine whether two numbers are coprime is given by the
The number of integers coprime to a positive integer n, between 1 and n, is given by
The numbers 1 and −1 are the only integers coprime to every integer, and they are the only integers that are coprime with 0.
A number of conditions are equivalent to a and b being coprime:
As a consequence of the third point, if a and b are coprime and br ≡ bs (
As a consequence of the first point, if a and b are coprime, then so are any powers ak and bm.
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.
The two integers a and b are coprime if and only if the point with coordinates (a, b) in a