Samprimtal

Samprimtal  är heltal som inte har några andra gemensamma delare än ±1. Ekvivalent definition [1] : heltal är coprime om deras största gemensamma divisor (gcd) är 1 .

Till exempel är talen 14 och 25 coprime eftersom de inte har några gemensamma divisorer; men talen 15 och 25 är inte coprime eftersom de har en gemensam divisor på 5.

För att indikera den relativa enkelheten hos talen och , används beteckningen ibland (en analogi med vinkelräta linjer som inte har gemensamma riktningar - relativt primtal har inte gemensamma faktorer [2] ).

Detta koncept introducerades i bok VII av Euklids element . Euklids algoritm kan användas för att bestämma om två tal är coprime .

Begreppet cosimplicity generaliserar naturligtvis till alla euklidiska ringar .

Parvisa samprimtal

Om i en uppsättning heltal några två tal är coprime, då kallas sådana tal parvis coprime (eller helt enkelt parvisa primtal [3] ). För två tal är begreppen "samprim" och "parvis primtal" desamma, för fler än två tal är egenskapen för parvis enkelhet starkare än den tidigare definierade egenskapen för ömsesidig enkelhet (i sammantaget) - parvisa primtal kommer att också vara coprime, men det omvända är inte sant [3] . Exempel:

• 8, 15 är inte primtal, utan coprime.
• 6, 8, 9 är ömsesidigt primtal (kollektivt), men inte parvisa primtal.
• 8, 15, 49 är parvis primtal och coprime (tillsammans).

Om talen är parvisa primtal, då:

• deras minsta gemensamma multipel är lika med det absoluta värdet av deras produkt: ;
• för vilket heltal som helst gäller formeln [4] :

Egenskaper

Alla tal som nämns i detta avsnitt antas vara heltal om inte annat anges.

• Antalet naturliga tal som är relativt primtal till ett naturligt tal ges av Euler-funktionen .

• Tal och är coprime om och endast om det finns heltal och sådant ( Bezouts relation ) [1] . Om de naturliga talen och är coprima, så är talen och också coprima, och det omvända är också sant.

• ( Euklids Lemma ) Om är en divisor av en produkt och coprime med , då är en divisor av .

• Om gcd , då är talen och coprime.

• Ett bråk är irreducerbart om och endast om dess täljare och nämnare är coprime.

• Om talen och är relativt primtal, så har kongruensen för någon en unik lösning [5] modulo I synnerhet ger lösningen av kongruensen för det inversa elementet för i ringen av rester modulo m . (Se Bezout relation )

• Sannolikheten att slumpmässigt valda positiva heltal kommer att vara coprime är , i den meningen att för , sannolikheten att positiva heltal mindre än (och slumpmässigt valda) kommer att vara coprime tenderar att . Här  är Riemann zeta-funktionen .

Tabell med samprimtal upp till 30

Varje cell innehåller den största gemensamma divisorn av dess koordinater, och enheterna som motsvarar coprime- par av koordinater är markerade i mörker. Av egenskapen som beskrivs ovan följer att den genomsnittliga tätheten av mörka celler när tabellen expanderas till oändlighet blir lika med .

Variationer och generaliseringar

Begreppen primtal , största gemensamma divisor och coprimtal generaliserar naturligt till godtyckliga euklidiska ringar , såsom polynomen ringer eller Gaussiska heltal . En generalisering av begreppet ett primtal är det " icke reducerbara elementet ". Ovanstående definition av samprimtal är inte lämplig för en godtycklig euklidisk ring, eftersom det kan finnas enhetsdelare i ringen ; i synnerhet definieras GCD upp till multiplikation med en enhetsdelare. Därför bör definitionen av relativt primtal modifieras [6] .

Likvärdiga formuleringar [6] :

• Element i en euklidisk ring är coprime om de inte har några gemensamma delare förutom enhetsdelare.
• ( Bezouts relation ) Element i en euklidisk ring är coprime om och endast om det finns sådana element

Euklids lemma håller också .

Praktisk tillämpning

Egenskapen av ömsesidig enkelhet spelar inte bara en viktig roll i talteori och kommutativ algebra , utan har ett antal viktiga praktiska tillämpningar, i synnerhet antalet tänder på kedjehjul och antalet kedjelänkar i en kedjedrift tenderar att vara relativt prime, vilket säkerställer jämnt slitage: varje tand på kedjehjulet kommer att arbeta i sin tur med alla länkar i kedjan.

Anteckningar

1. ↑ 1 2 Samprimtal. // Mathematical Encyclopedia (i 5 volymer). - M .: Soviet Encyclopedia , 1977. - T. 1. - S. 690.
2. ↑ R. Graham, D. Knuth, O. Patashnik. Konkret matematik . - M . : "Mir", 1998. - S.  139 . - 703 sid. — ISBN 5-03-001793-3 .
3. ↑ 1 2 Mikhelovich, 1967 , sid. 28.
4. ↑ Nesterenko Yu. V. Talteori. - M . : Publishing Center "Academy", 2008. - S. 40. - 272 sid. — ISBN 9785769546464 .
5. ↑ Mikhelovich, 1967 , sid. 64.
6. ↑ 1 2 Larin S. V. Algebra och tallära. Grupper, ringar och fält: lärobok. manual för akademisk studentexamen. - 2:a uppl. - M. : Yurait, 2018. - S. 92-93. — 160 s. — (Kandidat. Akademisk kurs). - ISBN 978-5-534-05567-2 .

Litteratur

• Coprime numbers  // Stora sovjetiska encyklopedin  : i 66 volymer (65 volymer och ytterligare 1) / kap. ed. O. Yu. Schmidt . - M .  : Sovjetiskt uppslagsverk , 1926-1947.
• Mikhelovich Sh. Kh. Talteori. - 2:a uppl. - M . : Högre skola, 1967. - 336 sid.