Pairwise coprime


Pairwise coprime

In mathematics, especially number theory, a set of integers 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 divisors other than 1). The concept of pairwise coprimality is important in applications of the Chinese remainder theorem and the proof for x3 + y3 + z3 = 0 has no nonzero integer solutions.

Definition

A set of integers {p1,p2,p3,...,pn} is pairwise coprime ⇔ gcd(pi,pj) = 1 where pi,pj ∈ {p1,p2,p3,...,pn} and pi ≠ pj

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).


Wikimedia Foundation. 2010.

Look at other dictionaries:

  • Coprime — In number theory, a branch of mathematics, two integers a and b are said to be coprime (also spelled co prime) 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 …   Wikipedia

  • 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.… …   Wikipedia

  • Gödel numbering for sequences — A Gödel numbering for sequences provides us an effective way to represent each finite sequence of natural numbers as a single natural number. Of course, the embedding is surely possible set theoretically, but the emphasis is on the effectiveness… …   Wikipedia

  • Dedekind sum — In mathematics, Dedekind sums, named after Richard Dedekind, are certain sums of products of a sawtooth function, and are given by a function D of three integer variables. Dedekind introduced them to express the functional equation of the… …   Wikipedia

  • Beal's conjecture — is a conjecture in number theory proposed by the Texas billionaire and amateur mathematician Andrew Beal.While investigating generalizations of Fermat s last theorem in 1993, Beal formulated the following conjecture:If: left. A^x +B^y = C^z ight …   Wikipedia

  • List of mathematics articles (P) — NOTOC P P = NP problem P adic analysis P adic number P adic order P compact group P group P² irreducible P Laplacian P matrix P rep P value P vector P y method Pacific Journal of Mathematics Package merge algorithm Packed storage matrix Packing… …   Wikipedia

  • Quotient ring — In mathematics a quotient ring, also known as factor ring or residue class ring, is a construction in ring theory, quite similar to the factor groups of group theory and the quotient spaces of linear algebra. One starts with a ring R and a two… …   Wikipedia

  • Ostrowski's theorem — Ostrowski s theorem, due to Alexander Ostrowski (1916), states that any non trivial absolute value on the rational numbers Q is equivalent to either the usual real absolute value or a p adic absolute value. Contents 1 Definitions 2 Proof 2.1 Case …   Wikipedia

  • Square-free polynomial — In mathematics, a square free polynomial is a polynomial with no square factors, i.e, f in F [x] is square free if and only if b^2 mid f for every b in F [x] with non zero degree. This definition implies that no factors of higher order can exist …   Wikipedia

  • abc conjecture — The abc conjecture (also known as Oesterlé–Masser conjecture) is a conjecture in number theory, first proposed by Joseph Oesterlé and David Masser in 1985. The conjecture is stated in terms of three positive integers, a, b and c (whence comes the …   Wikipedia