# Coprime integers

In

number theory, two

integers *a* and

*b* are said to be

**relatively prime**,

**mutually prime**,

^{} or

**coprime** (also written

**co-prime**) if the only positive integer (

factor) that divides both of them is 1. Consequently, any

prime number that divides one does not divide the other. This is equivalent to their

greatest common divisor (gcd) being 1.

^{}The numerator and denominator of a reduced fraction are coprime. As specific examples, 14 and 15 are coprime, being commonly divisible only by 1, while 14 and 21 are not coprime, because they are both divisible by 7.

Standard notations for relatively prime integers a and b are: gcd(*a*, *b*) = 1 and (*a*, *b*) = 1. Graham, Knuth and Patashnik have proposed that the notation $a\perp b$ be used to indicate that *a* and *b* are relatively prime and that the term "prime" be used instead of coprime (as in a is *prime* to b).^{}

A fast way to determine whether two numbers are coprime is given by the Euclidean algorithm.

The number of integers coprime to a positive integer *n*, between 1 and *n*, is given by Euler's totient function (or Euler's phi function) *φ*(*n*).

A set of integers can also be called **coprime** if its elements share no common positive factor except 1. A stronger condition on a set of integers is **pairwise coprime**, which means that *a* and *b* are coprime for every pair (*a*, *b*) of different integers in the set. The set {2, 3, 4} is coprime, but it is not pairwise coprime since 2 and 4 are not relatively prime.

This page was last edited on 12 February 2018, at 02:28.

Reference:

https://en.wikipedia.org/wiki/Coprime under CC BY-SA license.

## Related Topics

**Warning**: DOMDocument::loadHTML(): Tag math invalid in Entity, line: 1 in

**/home/ashver/webapps/infospaze/index.php** on line

**389**
**Warning**: DOMDocument::loadHTML(): Tag semantics invalid in Entity, line: 1 in

**/home/ashver/webapps/infospaze/index.php** on line

**389**
**Warning**: DOMDocument::loadHTML(): Tag mrow invalid in Entity, line: 1 in

**/home/ashver/webapps/infospaze/index.php** on line

**389**
**Warning**: DOMDocument::loadHTML(): Tag mstyle invalid in Entity, line: 1 in

**/home/ashver/webapps/infospaze/index.php** on line

**389**
**Warning**: DOMDocument::loadHTML(): Tag mi invalid in Entity, line: 1 in

**/home/ashver/webapps/infospaze/index.php** on line

**389**
**Warning**: DOMDocument::loadHTML(): Tag mo invalid in Entity, line: 1 in

**/home/ashver/webapps/infospaze/index.php** on line

**389**
**Warning**: DOMDocument::loadHTML(): Tag mi invalid in Entity, line: 1 in

**/home/ashver/webapps/infospaze/index.php** on line

**389**
**Warning**: DOMDocument::loadHTML(): Tag annotation invalid in Entity, line: 1 in

**/home/ashver/webapps/infospaze/index.php** on line

**389**
## Recently Viewed