Coprime tal

Coprimtal  er heltal , der ikke har andre fælles divisorer end ±1. Ækvivalent definition [1] : heltal er coprime, hvis deres største fælles divisor (gcd) er 1 .

For eksempel er tallene 14 og 25 coprime, fordi de ikke har nogen fælles divisorer; men tallene 15 og 25 er ikke coprime, da de har en fælles divisor på 5.

For at angive den relative enkelthed af tallene og , bruges notationen nogle gange (en analogi med vinkelrette linjer, der ikke har fælles retninger - relativt primtal har ikke fælles faktorer [2] ).

Dette koncept blev introduceret i Bog VII af Euklids elementer . Euklids algoritme kan bruges til at bestemme, om to tal er coprime .

Begrebet cosimplicity generaliserer naturligvis til alle euklidiske ringe .

Parvise coprime tal

Hvis to tal i et sæt af heltal er coprime, så kaldes sådanne tal parvise coprime (eller blot parvise primtal [3] ). For to tal er begreberne "coprime" og "parvise primtal" de samme, for mere end to tal er egenskaben for parvis enkelhed stærkere end den tidligere definerede egenskab for gensidig enkelhed (i det samlede antal) - parvise primtal vil også være coprime, men det modsatte er ikke sandt [3] . Eksempler:

• 8, 15 er ikke prime, men coprime.
• 6, 8, 9 er indbyrdes primtal (samlet), men ikke parvise primtal.
• 8, 15, 49 er parvise prime og coprime (sammen).

Hvis tallene er parvise primtal, så:

• deres mindste fælles multiplum er lig med den absolutte værdi af deres produkt: ;
• for ethvert heltal gælder formlen [4] :

Egenskaber

Alle tal nævnt i dette afsnit antages at være heltal, medmindre andet er angivet.

• Antallet af naturlige tal, der er relativt prime til et naturligt tal , er givet af Euler-funktionen .

• Tal og er coprime hvis og kun hvis der er heltal og sådan ( Bezouts relation ) [1] . Hvis de naturlige tal og er coprime, så er tallene og også coprime, og det omvendte er også sandt.

• ( Euklids Lemma ) Hvis er en divisor af et produkt og coprime med , så er en divisor af .

• Hvis gcd , så er tallene og coprime.

• En brøk er irreducerbar , hvis og kun hvis dens tæller og nævner er coprime.

• Hvis tallene og er relativt primtal, så har kongruensen for enhver en unik løsning [5] modulo Især giver løsningen af ​​kongruensen for det inverse element for i ringen af ​​rester modulo m . (Se Bezout relation )

• Sandsynligheden for, at tilfældigt valgte positive heltal vil være coprime er , i den forstand, at sandsynligheden for, at positive heltal mindre end (og tilfældigt udvalgte) vil være coprime, har en tendens til . Her  er Riemann zeta-funktionen .

Tabel med primtal op til 30

Hver celle indeholder den største fælles divisor af dens koordinater, og de enheder, der svarer til coprime - par af koordinater, er fremhævet i mørke. Af den ovenfor beskrevne egenskab følger det, at den gennemsnitlige tæthed af mørke celler, når bordet udvides til uendeligt, bliver lig med .

Variationer og generaliseringer

Begreberne primtal , største fælles divisor og coprimtal generaliseres naturligt til vilkårlige euklidiske ringe , såsom polynomialringen eller de Gaussiske heltal . En generalisering af begrebet et primtal er det " irreducerbare element ". Ovenstående definition af coprimtal er ikke egnet til en vilkårlig euklidisk ring, da der kan være enhedsdelere i ringen ; især er GCD defineret op til multiplikation med en divisor af enhed. Derfor bør definitionen af ​​relativt primtal modificeres [6] .

Tilsvarende formuleringer [6] :

• Elementer i en euklidisk ring er coprime, hvis de ikke har andre fælles divisorer end enhedsdivisorer.
• ( Bezout 's relation ) Elementer i en euklidisk ring er coprime hvis og kun hvis der er elementer sådan at

Euklids lemma gælder også .

Praktisk anvendelse

Egenskaben gensidig enkelhed spiller ikke kun en vigtig rolle i talteori og kommutativ algebra , men har en række vigtige praktiske anvendelser, især antallet af tænder på tandhjul og antallet af kædeled i et kædedrev har en tendens til at være relativt prime, hvilket sikrer ensartet slitage: hver tand på kædehjulet vil arbejde efter tur med alle kædens led.

Noter

1. ↑ 1 2 Coprime tal. // Matematisk Encyklopædi (i 5 bind). - M .: Soviet Encyclopedia , 1977. - T. 1. - S. 690.
2. ↑ R. Graham, D. Knuth, O. Patashnik. Konkret matematik . - M . : "Mir", 1998. - S.  139 . - 703 s. — ISBN 5-03-001793-3 .
3. ↑ 1 2 Mikhelovich, 1967 , s. 28.
4. ↑ Nesterenko Yu. V. Talteori . - M . : Publishing Center "Academy", 2008. - S. 40. - 272 s. — ISBN 9785769546464 .
5. ↑ Mikhelovich, 1967 , s. 64.
6. ↑ 1 2 Larin S. V. Algebra og talteori. Grupper, ringe og felter: lærebog. manual til akademisk studentereksamen. - 2. udg. - M. : Yurait, 2018. - S. 92-93. — 160 sek. — (Bachelor. Akademisk kursus). - ISBN 978-5-534-05567-2 .

Litteratur

• Coprime numbers  // Great Soviet Encyclopedia  : i 66 bind (65 bind og 1 yderligere) / kap. udg. O. Yu. Schmidt . - M  .: Sovjetisk encyklopædi , 1926-1947.
• Mikhelovich Sh. Kh. Talteori. - 2. udg. - M . : Højere skole, 1967. - 336 s.