Paarsgewijs relatief priem

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken

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[bewerken]

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[bewerken]

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 .