Door Lee Johnson Bijgewerkt op 30 augustus 2022

Sky_Blue/iStock/GettyImages

In de wiskunde helpt het concept van coprimaliteit – ook wel relatief of wederzijds priemgetal genoemd – ons te begrijpen hoe getallen op elkaar inwerken op basis van hun primaire factoren. Een paar gehele getallen is coprime als de enige gemeenschappelijke deler die ze delen 1 is. Deze eigenschap ligt ten grondslag aan veel gebieden van de getaltheorie, cryptografie en algoritmeontwerp.

Wat is een Coprime?

Twee getallen zijn coprime als er, nadat ze elk in hun priemfactoren zijn ontbonden, in beide factorisaties geen priemgetal voorkomt. Bijvoorbeeld 21 =3 × 7 en 22 =2 × 11; de enige gedeelde deler is 1, dus 21 en 22 zijn coprime. Priemgetallen worden automatisch geprimeerd met elk getal dat dat priemgetal niet in de factorisatie bevat.

Prime-factorisatie:de sleutel tot Coprime-identificatie

Het bepalen van de coprime-status begint met priemfactorisatie. Neem 35 als voorbeeld:

• 35 ÷ 5 =7 (beide priemgetallen) → 35 =5 × 7.

Vervolgens factor 60:

• 60 ÷ 2 =30 → 30 ÷ 2 =15 → 15 ÷ 3 =5 → 5 is een priemgetal, dus 60 =2² × 3 × 5.

Door de priemfactoren op een rij te zetten, kunnen we zien welke priemgetallen ontbreken en dus geschikt zijn voor het construeren van coprimes.

Coprimes vinden:praktische stappen

Zodra de priemfactoren van een getal bekend zijn, zal elk geheel getal dat uitsluitend is opgebouwd uit priemgetallen die niet aanwezig zijn in die factorisatie, er coprime voor zijn. Voor 35 (priemgetallen 5 en 7) zijn getallen zoals 2, 3, 11, 13, 17, 19, 23, 29, 31, 37, enz., en hun producten (6 (2×3), 9 (3²), 22 (2×11), 33 (3×11), 26 (2×13)) allemaal coprime tot 35.

Op dezelfde manier is voor 60 (priemgetallen 2, 3, 5) elk geheel getal dat deze priemgetallen vermijdt coprime. Voorbeelden zijn onder meer 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59 en hun producten:77 (7×11), 91 (7×13), 119 (7×17), 143 (11×13), enz.

Handige sneltoetsen:

• Elk priemgetal dat het oorspronkelijke getal niet deelt, is automatisch coprime.
• Twee opeenvolgende gehele getallen zijn altijd coprime.
• De grootste gemene deler (GCD) kan snel worden berekend met behulp van het Euclidische algoritme.

Controleren of twee nummers Coprime zijn

De eenvoudigste verificatie is om beide getallen te ontbinden en te zoeken naar gedeelde priemgetallen. U kunt ook de GCD berekenen; als het gelijk is aan 1, zijn de getallen coprime. Deze aanpak is sneller voor grote gehele getallen en vormt de basis voor veel cryptografische protocollen.

Hulpmiddelen en bronnen

Online factorisatie en GCD-rekenmachines kunnen deze stappen automatiseren. Betrouwbare bronnen zijn WolframAlpha, de Number Theory Toolbox en andere gerenommeerde wiskundeplatforms.