Difference between revisions of "Relatively prime"
(caps sensitive links...) |
I like pie (talk | contribs) (Wikified, please confirm that no more wikification is needed and delete tag) |
||
| 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 | + | 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. Equivalently, <math>{m}</math> and <math>{n}</math> must have no [[prime]] divisors in common, which is mathematically written <math>\gcd(m,n)=1</math>. 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 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>. | |
== See also == | == See also == | ||
| − | |||
* [[Number theory]] | * [[Number theory]] | ||
* [[Greatest common divisor]] | * [[Greatest common divisor]] | ||
| − | * [[ | + | * [[Chicken McNugget Theorem]] |
| − | |||
{{wikify}} | {{wikify}} | ||
| − | |||
{{stub}} | {{stub}} | ||
| − | |||
[[Category:Definition]] | [[Category:Definition]] | ||
[[Category:Number theory]] | [[Category:Number theory]] | ||
Revision as of 12:55, 17 April 2008
Two positive integers 
and 
are said to be relatively prime or coprime if they share no common divisors greater than 1. Equivalently, and must have no prime divisors in common, which is mathematically written 
. 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.
By the Euclidean algorithm, consecutive positive integers are always relatively prime. This is related to the fact that two numbers 
and 
are relatively prime if and only if there exist some 
such that 
.
See also
Template:Wikify This article is a stub. Help us out by expanding it.
