Difference between revisions of "Relatively prime"
m |
Jeanius123 (talk | contribs) m (→Number Theory) |
||
| 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. | ||
| − | 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>. | + | Consecutive positive integers except <math>1</math> and <math>2</math> 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>. | 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>. | ||
Revision as of 02:30, 29 October 2016
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 are relatively prime to that number.
Consecutive positive integers except 
and 
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 
.
See also
This article is a stub. Help us out by expanding it.
