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"

(Wikified, please confirm that no more wikification is needed and delete tag)
m
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. 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.
+
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 <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 ==
 
== 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.
  
−
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>.
+
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 ==
Line 13: Line 13:
 
* [[Chicken McNugget Theorem]]
 
* [[Chicken McNugget Theorem]]
  
−
{{wikify}}
 
 
{{stub}}
 
{{stub}}
 
[[Category:Definition]]
 
[[Category:Definition]]
 
[[Category:Number theory]]
 
[[Category:Number theory]]

Revision as of 13:21, 17 April 2008

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 $\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 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 $a$ and $b$ are relatively prime if and only if there exist some $x,y\in \mathbb{Z}$ such that $ax+by=1$.

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=24899"