View source for Coprime

In [[mathematics]], two [[integer]]s (''a'' and ''b'') are '''co-prime''' (or '''relatively prime''') if they share no common factors. This is sometimes written as <math>a \perp b</math>.<ref>{{Cite web|date=2020-03-01|title=Compendium of Mathematical Symbols|url=https://mathvault.ca/hub/higher-math/math-symbols/|access-date=2020-09-20|website=Math Vault|language=en-US}}</ref><ref name=":0">{{Cite web|last=Weisstein|first=Eric W.|title=Relatively Prime|url=https://mathworld.wolfram.com/RelativelyPrime.html|access-date=2020-09-20|website=mathworld.wolfram.com|language=en}}</ref> In other words, there is no number, other than 1, that divides both a and b evenly.<ref>{{Cite web|title=Coprime Definition (Illustrated Mathematics Dictionary)|url=https://www.mathsisfun.com/definitions/coprime.html|access-date=2020-09-20|website=www.mathsisfun.com}}</ref> In which case, the [[greatest common divisor]] ('''GCD''', or '''highest common factor''') of these numbers is 1.<ref name=":0" />

As an example, 6 and 35 are coprime, because the factors of 6, 2 and 3, do not divide 35 evenly. On the other hand, 6 and 27 are not coprime, because 3 divides both 6 and 27. Another example is 4 and 5:
4 = 2*2*1; 
5 = 5*1 (Prime). The only common factor is 1, so they are coprime.

On the other hand, 10 and 5:
10 = 5*2 
5 = 5*1 (Prime). The common factors are 5 and 1, so they are not coprime.

[[Prime number]]s are always '''coprime''' to each other.

# Any two consecutive integers are always '''coprime'''.
# Sum of any two '''coprime''' numbers is always '''coprime''' to their product.
# 1 is trivially '''coprime''' with all numbers.
# if out of two numbers, any one number is a prime number while the other number is not a multiple of first one, then both are coprime.
# This is not applicable to negative numbers

== Related pages ==

* [[Chinese remainder theorem]]
* [[Euler's totient function]]
* [[Euler's totient theorem]]

== References ==
<references />
{{Math-stub}}

[[Category:Number theory]]