Difference between revisions of "Relatively prime"
(added "greater than 1" to definition and altered another internal link) |
m |
||
(20 intermediate revisions by 13 users not shown) | |||
Line 1: | Line 1: | ||
− | + | Two [[positive]] [[integer]]s <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. That is, their [[greatest common divisor]] is <math>\gcd(m, n) = 1</math>. Equivalently, <math>m</math> and <math>n</math> must have no [[prime]] divisors in common. The 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. | |
− | + | == 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 <math>p</math> divides both <math>n</math> and <math>n+1</math>, then it must divide their difference <math>(n+1)-n = 1</math>, which is impossible since <math>p > 1</math>. | |
− | + | Two integers <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]]). The [[Euclidean Algorithm]] can be used to compute the coefficients <math>x,y</math>. | |
− | + | For two relatively prime numbers, their [[least common multiple]] is their product. This pops up in [[Chinese Remainder Theorem]]. | |
+ | == See also == | ||
* [[Number theory]] | * [[Number theory]] | ||
* [[Greatest common divisor]] | * [[Greatest common divisor]] | ||
− | * [[ | + | * [[Chicken McNugget Theorem]] |
+ | |||
+ | {{stub}} | ||
+ | [[Category:Definition]] | ||
+ | [[Category:Number theory]] |
Latest revision as of 15:51, 25 February 2020
Two positive integers and
are said to be relatively prime or coprime if they share no common divisors greater than 1. That is, their greatest common divisor is
. Equivalently,
and
must have no prime divisors in common. 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 is relatively prime to that number.
Consecutive positive integers are always relatively prime, since, if a prime divides both
and
, then it must divide their difference
, which is impossible since
.
Two integers and
are relatively prime if and only if there exist some
such that
(a special case of Bezout's Lemma). The Euclidean Algorithm can be used to compute the coefficients
.
For two relatively prime numbers, their least common multiple is their product. This pops up in Chinese Remainder Theorem.
See also
This article is a stub. Help us out by expanding it.