Difference between revisions of "Relatively prime"

Line 6: Line 6:
 
[[Euler's totient function]] determines the number of positive integers less than any given positive integer that are relatively prime to that number.
 
[[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 <math>a</math> and <math>b</math> are relatively prime if and only if there exist some <math>x,y\in \mathbb{Z}</math> such that <math>ax+by=1</math> (a special case of [[Bezout's Lemma]].
+
By the [[Euclidean algorithm]], consecutive positive integers are always relatively prime. This is related to the fact that two numbers <math>a</math> and <math>b</math> are relatively prime if and only if there exist some <math>x,y\in \mathbb{Z}</math> such that <math>ax+by=1</math> (a special case of [[Bezout's Lemma]]).
  
 
== See also ==
 
== See also ==

Revision as of 15:41, 12 January 2011

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 $\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 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 $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).

See also

This article is a stub. Help us out by expanding it.