Relatively prime
Two positive integers and
are said to be relatively prime or coprime if they share no common divisors greater than 1. Equivalently,
and
must have no prime divisors in common, which is mathematically written
. The positive integers
and
are relatively prime if and only if
is in lowest terms.
Number Theory
Relatively prime numbers show up frequently in number theory formulas and derivations:
Euler's totient function determines the number of positive integers less than any given positive integer that are relatively prime to that number.
By the Euclidean algorithm, consecutive positive integers are always relatively prime. This is related to the fact that two numbers and
are relatively prime if and only if there exist some
such that
.
See also
Template:Wikify This article is a stub. Help us out by expanding it.