Av Lee Johnson Uppdaterad 30 augusti 2022

Sky_Blue/iStock/GettyImages

Inom matematiken hjälper begreppet coprimality – även kallat relativt eller ömsesidigt primtal – oss att förstå hur tal interagerar baserat på deras primtalsfaktorer. Ett par heltal är coprime när den enda gemensamma divisorn de delar är 1. Denna egenskap ligger till grund för många områden av talteori, kryptografi och algoritmdesign.

Vad är en Coprime?

Två tal är coprime om, efter att ha sönderdelats var och en i sina primtalsfaktorer, inget primtal förekommer i båda faktoriseringarna. Till exempel, 21 =3 × 7 och 22 =2 × 11; den enda delade divisorn är 1, så 21 och 22 är coprime. Primtal primeras automatiskt med alla tal som inte innehåller det primtal i sin faktorisering.

Prime Factorization:Nyckeln till Coprime-identifiering

Att bestämma coprime-status börjar med primtalsfaktorisering. Ta 35 som exempel:

• 35 ÷ 5 =7 (båda primtal) → 35 =5 × 7.

Därefter faktor 60:

• 60 ÷ 2 =30 → 30 ÷ 2 =15 → 15 ÷ 3 =5 → 5 är primtal, så 60 =2² × 3 × 5.

Genom att lista primtalsfaktorerna kan vi se vilka primtal som är frånvarande och därför lämpliga för att konstruera samprimtal.

Hitta Coprimes:Praktiska steg

När primtalsfaktorerna för ett tal är kända, kommer alla heltal som byggs enbart från primtal som inte finns i den faktoriseringen att vara coprime till det. För 35 (primtal 5 och 7), siffror som 2, 3, 11, 13, 17, 19, 23, 29, 31, 37, etc., och deras produkter – 6 (2×3), 9 (3²), 22 (2×11), 33 (3×11), 33 (3×11), 1×3—2 till 26 till 26 till (2)

På liknande sätt, för 60 (primtal 2, 3, 5), är varje heltal som undviker dessa primtal coprime. Exempel inkluderar 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59 och deras produkter:77 (7×11), 91 (7×13), 119 (7×17), 143, (1) osv.

Användbara genvägar:

• Alla primtal som inte delar det ursprungliga talet är automatiskt coprime.
• Två på varandra följande heltal är alltid coprime.
• Den största gemensamma divisorn (GCD) kan beräknas snabbt med den euklidiska algoritmen.

Kontrollerar om två nummer är Coprime

Den enklaste verifieringen är att faktorisera båda talen och leta efter delade primtal. Alternativt, beräkna GCD; om det är lika med 1 är talen coprime. Detta tillvägagångssätt är snabbare för stora heltal och är grunden för många kryptografiska protokoll.

Verktyg och resurser

Online primtalsfaktorisering och GCD-kalkylatorer kan automatisera dessa steg. Tillförlitliga resurser inkluderar WolframAlpha, Number Theory Toolbox och andra välrenommerade matematikplattformar.