Pairwise coprime: Difference between revisions
Content deleted Content added
Rewrote bits and pieces for clarity; removed redundant "Definition" section |
Tom.Reding (talk | contribs) m +{{Redirect category shell}} for multiple-{{R}} #Rs using AWB |
||
| (7 intermediate revisions by 6 users not shown) | |||
| Line 1: | Line 1: | ||
#REDIRECT [[Coprime integers#Coprimality in sets]] |
|||
In [[mathematics]], especially [[number theory]], a set of [[integer]]s is said to be '''pairwise coprime''' (or '''pairwise relatively prime''', '''mutually coprime''' or '''mutually relatively prime''') if every two distinct integers ''a'' and ''b'' in the set are [[coprime]] (that is, have no common positive [[divisor]]s other than 1). |
|||
{{Redirect category shell|1= |
|||
Pairwise coprimality should be contrasted with coprimality (unmodified by the word "pairwise"; also known as ''setwise coprimality''), in which it is requested only that no positive integer other than 1 divides all the members of the set. |
|||
{{R from merge}} |
|||
{{R to section}} |
|||
The concept of pairwise coprimality is important as a hypothesis in many results in number theory such as the [[Chinese remainder theorem]]. |
|||
}} |
|||
== Examples == |
|||
The set {10, 7, 33, 13} is pairwise coprime, because any pair of the numbers have [[greatest common divisor]] (gcd) equal to 1: |
|||
: gcd(10, 7) = gcd(10, 33) = gcd(10, 13) = gcd(7, 33) = gcd(7, 13) = gcd(33, 13) = 1. |
|||
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 pairwise coprime, as is the set of elements in [[Sylvester's sequence]], 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 divisor]] 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 gcd(6, 10) = 2, gcd(10, 15) = 5 and gcd(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''' if and only if there is no prime number that divides two or more elements of ''P''. |
|||
{{numtheory-stub}} |
|||
[[Category:Number theory]] |
|||
[[nl:Paarsgewijs relatief priem]] |
|||
Latest revision as of 00:36, 15 June 2017
Redirect to:
This page is a redirect. The following categories are used to track and monitor this redirect:
|