Difference between revisions of "Relatively prime"

Latest revision as of 17:45, 14 October 2024

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, their greatest common divisor 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 is relatively prime to that number.

Consecutive positive integers are always relatively prime, since, if a prime $p$ divides both $n$ and $n+1$ , then it must divide their difference $(n+1)-n = 1$ , which is impossible since $p > 1$ .

Two integers $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). The Euclidean Algorithm can be used to compute the coefficients $x,y$ .

For two relatively prime numbers, their least common multiple is their product. This pops up in Chinese Remainder Theorem.

@@ Line 1: / Line 1: @@
-(Also called ''coprime''.)
+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.
-Two '''relatively prime''' integers <math>{m}</math> and <math>{n}</math> 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; as 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.
+== Number Theory ==
+Relatively prime numbers show up frequently in [[number theory]] formulas and derivations:
-Note that for relatively prime <math>{m}</math> and <math>{n}</math>, <math>\frac{m}{n}</math> will be in lowest terms.
+[[Euler's totient function]] determines the number of positive integers less than any given positive integer that is relatively prime to that number.
-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.
+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>.
-It is also worth noting that by the [[Euclidean algorithm]], consecutive positive integers are always relatively prime.
+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>.
-=== See also ===
+For two relatively prime numbers, their [[least common multiple]] is their product. This pops up in [[Chinese Remainder Theorem]].
+== See also ==
 * [[Number theory]]
 * [[Greatest common divisor]]
-* [[Euclidean algorithm]]
+* [[Chicken McNugget Theorem]]
+{{stub}}
+[[Category:Definition]]
+[[Category:Number theory]]

Page

Toolbox

Search

Difference between revisions of "Relatively prime"

Latest revision as of 17:45, 14 October 2024

Number Theory

See also