Relatively prime

Two positive integers $m$ and $n$ are said to be relatively prime or coprime if they share no common divisors greater than 1. That is, their greatest common divisor is $\gcd(m, n) = 1$ . Equivalently, $m$ and $n$ must have no prime divisors in common. The positive integers $m$ and $n$ are relatively prime if and only if $\frac{m}{n}$ 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 is relatively prime to that number.

Consecutive positive integers are always relatively prime, since, if a prime $p$ divides both $n$ and $n+1$ , then it must divide their difference $(n+1)-n = 1$ , which is impossible since $p > 1$ .

Two integers $a$ and $b$ are relatively prime if and only if there exist some $x,y\in \mathbb{Z}$ such that $ax+by=1$ (a special case of Bezout's Lemma). The Euclidean Algorithm can be used to compute the coefficients $x,y$ .

For two relatively prime numbers, their least common multiple is their product. This pops up in Chinese Remainder Theorem.

Page

Toolbox

Search

Relatively prime

Number Theory

See also