Paarsgewijs relatief priem

In de getaltheorie is een verzameling van gehele getallen paarsgewijs relatief priem als voor elk paar getallen a en b geldt dat ze relatief priem zijn (a en b hebben 1 als grootste gemene deler). Het concept wordt onder andere gebruikt bij de Chinese reststelling.

Naast de formulering "de verzameling { a, b, c} is paarsgewijs relatief priem" gebruikt men ook wel "de getallen a, b en c zijn paarsgewijs relatief priem".

Definitie

Een verzameling gehele getallen $S = \{ p_{1}, \ldots, p_{n} \}$ is paarsgewijs relatief priem dan en slechts dan als

$\text{ggd}(p_{i}, p_{j}) = 1$ voor alle $p_{i}, p_{j} \in S$ met $i \not = j$.

Voorbeelden

De verzameling { 10, 7, 33, 13 } is paarsgewijs relatief priem want elk paar van getallen heeft 1 als grootste gemene deler:

$\mathrm{ggd}(10,7) = \mathrm{ggd}(10,33) = \mathrm{ggd}(10,13) = \mathrm{ggd}(7,33) = \mathrm{ggd}(7,13) = \mathrm{ggd}(33,13) = 1$.

De verzameling { 10, 7, 33, 14 } is niet paarsgewijs relatief priem aangezien

$\mathrm{ggd}(10,14) = 2 \ne 1$ en ook $\mathrm{ggd}(7,14) = 7 \ne 1$.