Pairwise coprime
Encyclopedia
In mathematics
, especially number theory
, a set of integer
s is said to be pairwise coprime (or pairwise relatively prime, also known as mutually coprime) if every pair of distinct integers a and b in the set are coprime
(that is, have no common divisor
s other than 1). The concept of pairwise coprimality is important in applications of the Chinese remainder theorem
and the proof that x3 + y3 + z3 = 0 has no nonzero integer solutions.
, for every p and q in P with p ≠ q, gcd(p, q) = 1. Here gcd denotes the greatest common divisor
.
Where gcd(a, b) refers to the greatest common divisor of a and b.
On the other hand, the integers 10, 7, 33, 14 are not pairwise coprime, because gcd(10, 14) = 2 ≠ 1 and gcd(7, 14) = 7 ≠ 1.
, and the set of all Fermat numbers.
of all integers in the set is 1. For example, the integers 6, 10, 15 are coprime (because the only positive integer dividing all of them is 1), but they are not pairwise coprime because the greatest common divisor or gcd of (6, 10) = 2, gcd of (10, 15) = 5 and gcd of (6, 15) = 3. On the other hand if some integers are pairwise coprime then they are certainly coprime, i.e. pairwise coprimality implies coprimality but not vice versa. To prove the implication it is sufficient to note that any common divisor of all the integers can only be 1 (otherwise pairwise coprimality will be violated).
, considering their prime factorization, there is no factor common to two or more of them.
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
, especially number theory
Number theory
Number theory is a branch of pure mathematics devoted primarily to the study of the integers. Number theorists study prime numbers as well...
, a set of integer
Integer
The integers are formed by the natural numbers together with the negatives of the non-zero natural numbers .They are known as Positive and Negative Integers respectively...
s is said to be pairwise coprime (or pairwise relatively prime, also known as mutually coprime) if every pair of distinct integers a and b in the set are coprime
Coprime
In number theory, a branch of mathematics, two integers a and b are said to be coprime or relatively prime if the only positive integer that evenly divides both of them is 1. This is the same thing as their greatest common divisor being 1...
(that is, have no common divisor
Divisor
In mathematics, a divisor of an integer n, also called a factor of n, is an integer which divides n without leaving a remainder.-Explanation:...
s other than 1). The concept of pairwise coprimality is important in applications of the Chinese remainder theorem
Chinese remainder theorem
The Chinese remainder theorem is a result about congruences in number theory and its generalizations in abstract algebra.In its most basic form it concerned with determining n, given the remainders generated by division of n by several numbers...
and the proof that x3 + y3 + z3 = 0 has no nonzero integer solutions.
Definition
A set P of integers is pairwise coprime iffIFF
IFF, Iff or iff may refer to:Technology/Science:* Identification friend or foe, an electronic radio-based identification system using transponders...
, for every p and q in P with p ≠ q, gcd(p, q) = 1. Here gcd denotes the greatest common divisor
Greatest common divisor
In mathematics, the greatest common divisor , also known as the greatest common factor , or highest common factor , of two or more non-zero integers, is the largest positive integer that divides the numbers without a remainder.For example, the GCD of 8 and 12 is 4.This notion can be extended to...
.
Examples
The set {10, 7, 33, 13} is pairwise coprime, because any pair of the numbers have a Greatest common divisor equal to 1:- gcd(10, 7) = gcd(10, 33) = gcd(10, 13) = gcd(7, 33) = gcd(7, 13) = gcd(33, 13) = 1.
Where gcd(a, b) refers to the greatest common divisor of a and b.
On the other hand, the integers 10, 7, 33, 14 are not pairwise coprime, because gcd(10, 14) = 2 ≠ 1 and gcd(7, 14) = 7 ≠ 1.
Infinite examples
The set of all primes is of course pairwise coprime, as is the set of elements in Sylvester's sequenceSylvester's sequence
In number theory, Sylvester's sequence is an integer sequence in which each member of the sequence is the product of the previous members, plus one. The first few terms of the sequence are:...
, and the set of all Fermat numbers.
"Pairwise coprime" vs "coprime"
The concept of pairwise coprimality is stronger than that of coprimality. The latter indicates that the greatest common divisorGreatest common divisor
In mathematics, the greatest common divisor , also known as the greatest common factor , or highest common factor , of two or more non-zero integers, is the largest positive integer that divides the numbers without a remainder.For example, the GCD of 8 and 12 is 4.This notion can be extended to...
of all integers in the set is 1. For example, the integers 6, 10, 15 are coprime (because the only positive integer dividing all of them is 1), but they are not pairwise coprime because the greatest common divisor or gcd of (6, 10) = 2, gcd of (10, 15) = 5 and gcd of (6, 15) = 3. On the other hand if some integers are pairwise coprime then they are certainly coprime, i.e. pairwise coprimality implies coprimality but not vice versa. To prove the implication it is sufficient to note that any common divisor of all the integers can only be 1 (otherwise pairwise coprimality will be violated).
Alternative definition
A set P of integers is pairwise coprime iffIFF
IFF, Iff or iff may refer to:Technology/Science:* Identification friend or foe, an electronic radio-based identification system using transponders...
, considering their prime factorization, there is no factor common to two or more of them.