Pairwise coprime

From Wikipedia, the free encyclopedia

In mathematics, especially number theory, a set of integers is said to be pairwise coprime (or pairwise relatively prime) if every pair of integers a and b in the set are coprime (that is, have no common divisors apart from 1). The concept of pairwise coprimality is important in applications of the Chinese remainder theorem.

[edit] Examples

The set {10, 7, 33, 13} is pairwise coprime, because any pair of the numbers have greatest common divisor equal to 1:

(10, 7) = (10, 33) = (10, 13) = (7, 33) = (7, 13) = (33, 13) = 1.

Here the notation (a, b) means the greatest common divisor of a and b.

On the other hand, the integers 10, 7, 33, 14 are not pairwise coprime, because (10, 14) = 2 ≠ 1 (or indeed because (7, 14) = 7 ≠ 1).

[edit] Usage

It is permissible to say "the integers 10, 7, 33, 13 are pairwise coprime", rather than the more exacting "the set of integers {10, 7, 33, 13} is pairwise coprime".

[edit] "Pairwise coprime" vs "coprime"

The concept of pairwise coprimality should not be confused with coprimality itself. The latter indicates that the greatest common divisor of all integers in the set is 1. For example, the integers 6, 10, 15 are coprime (because the only integer dividing all of them is 1), but they are not pairwise coprime because (6, 10) = 2, (10, 15) = 5 and (6, 15) = 3.