Difference between revisions of "Relatively prime"
m |
m |
||
| Line 1: | Line 1: | ||
| − | + | Two positive [[integer | integers]] <math>{m}</math> and <math>{n}</math> are said to be '''relatively prime''' or ''coprime'' if they share no [[common divisor | common divisors]] greater than 1, so <math>\displaystyle\gcd(m,n)=1</math>. Alternatively, <math>{m}</math> and <math>{n}</math> must have no [[prime]] divisors in common. For example, 15 and 14 are relatively prime: the [[prime factorization]] of 15 is <math>3 \cdot 5</math>, the prime factorization of 14 is <math>2 \cdot 7</math>, and no prime factors are shared between the two. | |
| − | |||
| − | Two positive [[integer | integers]] <math>{m}</math> and <math>{n}</math> are said to be '''relatively prime''' if they share no [[common divisor | common divisors]] greater than 1, so <math>\displaystyle\gcd(m,n)=1</math>. Alternatively, <math>{m}</math> and <math>{n}</math> must have no [[prime]] divisors in common. For example, 15 and 14 are relatively prime: the [[prime factorization]] of 15 is <math>3 \cdot 5</math>, the prime factorization of 14 is <math>2 \cdot 7</math>, and no prime factors are shared between the two. | ||
Note that positive integers <math>{m}</math> and <math>{n}</math> are relatively prime if and only if <math>\frac{m}{n}</math> is in lowest terms. | Note that positive integers <math>{m}</math> and <math>{n}</math> are relatively prime if and only if <math>\frac{m}{n}</math> is in lowest terms. | ||
Revision as of 16:01, 29 June 2006
Two positive integers 
and 
are said to be relatively prime or coprime if they share no common divisors greater than 1, so 
. Alternatively, and must have no prime divisors in common. For example, 15 and 14 are relatively prime: the prime factorization of 15 is 
, the prime factorization of 14 is 
, and no prime factors are shared between the two.
Note that positive integers and are relatively prime if and only if 
is in lowest terms.
Relatively prime numbers show up frequently in number theory formulas and derivations. Euler's totient function, for example, determines the number of positive integers less than any given positive integer that are relatively prime to that number. The Chicken McNugget Theorem also involves relatively prime numbers.
It is also worth noting that by the Euclidean algorithm, consecutive positive integers are always relatively prime.
