Coprimality

Coprimality is a relative property of two or more integers based on their prime factorization. Two integers are coprime if and only if their greatest common divisor (GCD) is 1, otherwise they are noncoprime (co-composite, so to speak). For example, 5, 7, 33, 53 and 1729 are mutually coprime; 7909, 9746, 745789 and 10177773727 are mutually noncoprime (their GCD is 11). Mutually coprime numbers might include number pairs which are pairwise noncoprime, e.g. 6, 15, 35 are mutually coprime, but 6 and 15 are pairwise noncoprime, 15 and 35 are pairwise noncoprime, although 6 and 35 are pairwise coprime. Obviously mutually noncoprime numbers necessarily include number pairs which are all pairwise noncoprime!

Formulae

${\rm {Coprime}}(m,n)\equiv [(m,n)=1],\,$

${\rm {Mutually~coprime}}(n_{1},\ldots ,n_{k})\equiv [((((n_{1},n_{2}),n_{3}),\cdots ),n_{k})=1],\,$

${\rm {Pairwise~coprime}}(n_{1},\ldots ,n_{k})\equiv \prod _{i\neq j}{\rm {Coprime}}(n_{i},n_{j})=\prod _{i=1}^{k}\prod _{j=1}^{i-1}{\rm {Coprime}}(n_{i},n_{j}),\,$

where 

[·]

is the Iverson bracket and 

(m, n)

is the GCD.

Pairwise coprime infinite sequences

An infinite sequence can have all its terms pairwise coprime, and it's not necessary for all terms to be prime numbers.

Sylvester's sequence (A000058) has this property, since each new term (odd) is the product of all the previous terms (even), plus 1

$a(0)=2,\,a(n)=a(0)\cdot a(1)\cdot \ldots \cdot a(n-1)+1,\,n\geq 1,\,$

and some terms are composite, like 1807 (the product of 13 and 139).

The Fermat numbers (A000215) also have this property, since each new term (odd) is the product of all the previous terms (odd), plus 2

$a(0)=3,\,a(n)=a(0)\cdot a(1)\cdot \ldots \cdot a(n-1)+2,\,n\geq 1,\,$

and apart from the first five Fermat numbers (  

F0

to 

F4

) which are prime, all other known Fermat numbers happen to be composite.

See also

• Strong coprimality
• Weak coprimality
• Coprimality triangle