Pairwise coprime: Difference between revisions
Content deleted Content added
No edit summary |
Tom.Reding (talk | contribs) m +{{Redirect category shell}} for multiple-{{R}} #Rs using AWB |
||
| (34 intermediate revisions by 23 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''', also known as '''mutually coprime''') if every pair of 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 for x<sup>3</sup> + y<sup>3</sup> + z<sup>3</sup> = 0 has no integer solutions. |
|||
{{Redirect category shell|1= |
|||
== Definition == |
|||
{{R from merge}} |
|||
{{R to section}} |
|||
A set of integers {p<sub>1</sub>,p<sub>2</sub>,p<sub>3</sub>,...,p<sub>n</sub>} is '''pairwise coprime''' ⇔ [[Greatest_common_divisor|gcd]](p<sub>i</sub>,p<sub>j</sub>) = 1 where p<sub>i</sub>,p<sub>j</sub> ∈ {p<sub>1</sub>,p<sub>2</sub>,p<sub>3</sub>,...,p<sub>n</sub>} and p<sub>i</sub> ≠ p<sub>j</sub> |
|||
}} |
|||
== 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). |
|||
== 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". |
|||
== "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 (6, 10) = 2, (10, 15) = 5 and (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). |
|||
{{numtheory-stub}} |
|||
[[Category:Number theory]] |
|||
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:
|