Relatief priem

Twee gehele getallen worden ten opzichte van elkaar relatief priem (ook wel copriem) of onderling ondeelbaar genoemd, wanneer er geen positief geheel getal groter dan 1 bestaat dat beide getallen deelt. Om te bepalen of twee getallen relatief priem zijn, berekent men gewoonlijk hun grootste gemene deler (ggd); twee getallen ${\displaystyle a}$ en ${\displaystyle b}$ zijn precies dan relatief priem, wanneer hun ${\displaystyle \mathrm {ggd} (a,b)}$ gelijk is aan 1. Dit betekent ook dat deze twee getallen geen gemeenschappelijke priemfactor bezitten.

Terwijl de getallen 6 en 35 zelf geen priemgetallen zijn, zijn deze wel 'relatief priem'; 6 = 2 × 3 en 35 = 5 × 7: er is geen gemeenschappelijke priemfactor.
Het getal 1 is gedefinieerd als relatief priem ten opzichte van elk ander geheel getal. Twee verschillende priemgetallen zijn hierdoor altijd ook relatief priem; 3 = 1 × 3 en 5 = 1 × 5.

Het algoritme van Euclides is een snelle manier om te bepalen of twee gehele getallen relatief priem zijn. De Eulers totiëntfunctie (of Eulers phi-functie) van een positief getal ${\displaystyle n}$ geeft het aantal gehele getallen tussen 1 en ${\displaystyle n}$ die relatief priem zijn ten opzichte van ${\displaystyle n}$.

Voor een verzameling van meer dan twee getallen kent men ook het begrip paarsgewijs relatief priem, waarbij voor elk paar getallen uit deze verzameling geldt dat ze relatief priem zijn.

Equivalente definities

Twee gehele getallen ${\displaystyle a}$ en ${\displaystyle b}$ zijn relatief priem als:

• er gehele getallen ${\displaystyle x}$ en ${\displaystyle y}$ bestaan, zodanig dat ${\displaystyle ax+by=1}$ (zie Stelling van Bachet-Bézout).
• ${\displaystyle b}$ een multiplicatieve inverse modulo ${\displaystyle a}$ heeft: er bestaat een geheel getal ${\displaystyle y}$ zodanig dat ${\displaystyle by\equiv 1{\pmod {a}}}$. In andere woorden, ${\displaystyle b}$ is een eenheidselement in de ring ${\displaystyle \mathbb {Z} /a\mathbb {Z} }$ van gehele getallen modulo ${\displaystyle a}$.

Een gevolg hiervan is dat als ${\displaystyle b^{a-1}\equiv 1{\pmod {a}}}$, de getallen ${\displaystyle a}$ en ${\displaystyle b^{a-1}}$ copriem, waaruit weer volgt dat ${\displaystyle a}$ en ${\displaystyle b}$ ook copriem moeten zijn.

Breuk

Een breuk kan dan en slechts dan vereenvoudigd worden als de teller en de noemer niet relatief priem zijn.

Toepassingen

Wanneer twee tandwielen tegen elkaar draaien en de aantallen tanden op de twee wielen zijn relatief priem, dan komen alle tanden elkaar bij ronddraaien tegen. Door te kiezen voor twee tandwielen, waarbij het aantal tanden ten opzichte van elkaar relatief priem zijn, voorkomt men een snelle slijtage van bepaalde tanden, terwijl andere tanden nooit worden gebruikt.

Waarschijnlijkheid dat twee getallen relatief priem zijn

Gegeven twee willekeurig gekozen gehele getallen ${\displaystyle a}$ en ${\displaystyle b}$, is het redelijk om zich af te vragen hoe groot de kans is dat ${\displaystyle a}$ en ${\displaystyle b}$ copriem zijn. Bij het bepalen van deze waarschijnlijkheid kan men gebruik van maken van de karakterisering dat ${\displaystyle a}$ en ${\displaystyle b}$ dan en slechts dan copriem zijn ten opzichte van elkaar als geen enkel priemgetal noch op ${\displaystyle a}$, noch op ${\displaystyle b}$ deelt, de twee getallen zijn onderling ondeelbaar (zie ook de hoofdstelling van de rekenkunde).

Intuïtief gezien is de kans dat enig getal deelbaar is door een priemgetal (of elk willekeurig geheel getal), ${\displaystyle p}$ gelijk aan ${\displaystyle 1/p}$. Vandaar dat de kans dat twee getallen beiden deelbaar zijn door dit priemgetal gelijk is aan

${\displaystyle 1/p^{2}}$

en is de kans dat ten minste een van hen dat niet is gelijk aan

${\displaystyle 1-1/p^{2}}$.

De kans dat twee getallen copriem zijn wordt dus gegeven door een product over alle priemgetallen,

${\displaystyle \prod _{p}^{\infty }\left(1-{\frac {1}{p^{2}}}\right)=\left(\prod _{p}^{\infty }{\frac {1}{1-p^{-2}}}\right)^{-1}={\frac {1}{\zeta (2)}}={\frac {6}{\pi ^{2}}}}$ ≈ 0{,}607927102 ≈ 61%.

Hier refereert ${\displaystyle \zeta }$ aan de Riemann-zeta-functie, de identiteit, die het product over de priemgetallen aan ${\displaystyle \zeta (2)}$ relateert, is een voorbeeld van een Euler-product en de evaluatie van ${\displaystyle \zeta (2)}$ als ${\displaystyle \pi ^{2}/6}$ wordt het Bazel-probleem genoemd. Dit probleem werd in 1735 opgelost door Leonhard Euler. In het algemeen geldt dat de kans dat ${\displaystyle k}$ willekeurig gekozen gehele getallen relatief priem zijn gelijk is aan

${\displaystyle 1/\zeta (k)}$

Er bestaat soms verwarring over wat precies bedoeld wordt met een "willekeurig gekozen geheel getal". Een manier om dit te begrijpen is om te veronderstellen dat deze gehele getallen willekeurig worden gekozen uit een verzameling gehele getallen beginnend bij 1 en lopend tot ${\displaystyle N}$. In dat geval bestaat er voor elke bovengrens ${\displaystyle N}$ een kans

${\displaystyle P_{N}}$

dat twee willekeurig gekozen gehele getallen relatief priem zijn. Dit zal nooit exact gelijk zijn aan

${\displaystyle 6/\pi ^{2}}$, maar in de limiet naar ${\displaystyle N\to \infty }$ nadert ${\displaystyle P_{N}\to 6/\pi ^{2}}$.^[1]

Zie ook

• Priemgetal
• Stelling van Dirichlet over rekenkundige rijen

Referenties