Sådan identificeres og beregnes coprime-tal

Af Lee Johnson Opdateret 30. august 2022

Sky_Blue/iStock/GettyImages

I matematik hjælper begrebet coprimality - også kaldet relativt eller gensidigt primtal - os med at forstå, hvordan tal interagerer baseret på deres primfaktorer. Et par heltal er coprime, når den eneste fælles divisor, de deler, er 1. Denne egenskab ligger til grund for mange områder inden for talteori, kryptografi og algoritmedesign.

Hvad er en Coprime?

To tal er coprime, hvis der efter nedbrydning af hver i dets primtalsfaktorer ikke optræder noget primtal i begge faktoriseringer. For eksempel, 21 =3 × 7 og 22 =2 × 11; den eneste delte divisor er 1, så 21 og 22 er coprime. Primtal er automatisk coprime med ethvert tal, der ikke indeholder det primtal i sin faktorisering.

Prime Factorization:Nøglen til Coprime-identifikation

Bestemmelse af coprime-status begynder med primtalsfaktorisering. Tag 35 som eksempel:

• 35 ÷ 5 =7 (begge primtal) → 35 =5 × 7.

Dernæst faktor 60:

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

Ved at liste primtalsfaktorerne kan vi se, hvilke primtal der er fraværende og derfor egnede til at konstruere coprime.

Find Coprimes:Praktiske trin

Når først et tals primtal er kendt, vil ethvert heltal, der udelukkende er bygget ud fra primtal, der ikke er til stede i denne faktorisering, være coprime til det. For 35 (primtal 5 og 7), tal som 2, 3, 11, 13, 17, 19, 23, 29, 31, 37 osv., og deres produkter – 6 (2×3), 9 (3²), 22 (2×11), 33 (3×11), 1×11), 1×3—2 til 26 til 26 (2)

Tilsvarende, for 60 (primtal 2, 3, 5), er ethvert heltal, der undgår disse primtal, coprime. Eksempler omfatter 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59 og deres produkter:77 (7×11), 91 (7×13), 119 (7×17), 143), 143, (1) osv.

Nyttige genveje:

• Ethvert primtal, der ikke deler det oprindelige tal, er automatisk coprime.
• To på hinanden følgende heltal er altid coprime.
• Den største fælles divisor (GCD) kan hurtigt beregnes ved hjælp af den euklidiske algoritme.

Kontrollerer, om to tal er Coprime

Den enkleste verifikation er at faktorisere begge tal og se efter fælles primtal. Alternativt kan du beregne GCD'en; hvis det er lig med 1, er tallene coprime. Denne tilgang er hurtigere for store heltal og er grundlaget for mange kryptografiske protokoller.

Værktøjer og ressourcer

Online primfaktorisering og GCD-beregnere kan automatisere disse trin. Pålidelige ressourcer omfatter WolframAlpha, Number Theory Toolbox og andre velrenommerede matematikplatforme.