Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "Relatively prime"

m (→‎Number Theory)
(→‎Number Theory)
Line 4: Line 4:
 
Relatively prime numbers show up frequently in [[number theory]] formulas and derivations:
 
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.
+
[[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 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>.
+
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>.
 
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 09:00, 10 September 2017

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$.

See also

This article is a stub. Help us out by expanding it.

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=Relatively_prime&oldid=87444"