Numerele coprime

Numerele coprime  sunt numere întregi care nu au divizori comuni alții decât ±1. Definiție echivalentă [1] : numerele întregi sunt între prime dacă cel mai mare divizor comun al lor (mcd) este 1 .

De exemplu, numerele 14 și 25 sunt între prime deoarece nu au divizori comuni; dar numerele 15 și 25 nu sunt între prime, deoarece au un divizor comun de 5.

Pentru a indica simplitatea relativă a numerelor și , se folosește uneori notația (o analogie cu drepte perpendiculare care nu au direcții comune - numerele prime relativ nu au factori comuni [2] ).

Acest concept a fost introdus în Cartea a VII -a a Elementelor lui Euclid . Algoritmul lui Euclid poate fi folosit pentru a determina dacă două numere sunt între prime .

Noțiunea de cosimplicitate se generalizează în mod natural la orice inele euclidiene .

Numere coprime în perechi

Dacă într-o mulțime de numere întregi oricare două numere sunt coprime, atunci astfel de numere se numesc coprime perechi (sau pur și simplu prime perechi [3] ). Pentru două numere, conceptele de „coprim” și „prim în perechi” sunt aceleași, pentru mai mult de două numere, proprietatea simplității perechilor este mai puternică decât proprietatea definită anterior a simplității reciproce (în agregat) - numerele prime în perechi vor fi, de asemenea, coprim, dar inversul nu este adevărat [3 ] . Exemple:

• 8, 15 nu sunt primi, ci coprim.
• 6, 8, 9 sunt numere prime reciproc (în mod colectiv), dar nu prime în perechi.
• 8, 15, 49 sunt prime perechi și coprime (împreună).

Dacă numerele sunt numere prime perechi, atunci:

• cel mai mic multiplu comun al acestora este egal cu valoarea absolută a produsului lor: ;
• pentru orice număr întreg , formula [4] este valabilă :

Proprietăți

Toate numerele menționate în această secțiune sunt considerate a fi numere întregi, dacă nu se specifică altfel.

• Numărul de numere naturale care sunt relativ prime față de un număr natural este dat de funcția Euler .

• Numerele și sunt între prime dacă și numai dacă există numere întregi și astfel încât ( relația lui Bezout ) [1] . Dacă numerele naturale și sunt între prime, atunci numerele și sunt, de asemenea, între prime, iar inversul este de asemenea adevărat.

• ( Lema lui Euclid ) Dacă este un divizor al unui produs și coprim cu , atunci este un divizor al lui .

• Dacă mcd , atunci numerele și sunt coprime.

• O fracție este ireductibilă dacă și numai dacă numărătorul și numitorul ei sunt coprim.

• Dacă numerele și sunt relativ prime, atunci congruența pentru oricare are o soluție unică [5] modulo În special, soluția congruenței pentru dă elementul invers pentru în inelul de reziduuri modulo m . (Vezi relația Bezout )

• Probabilitatea ca numerele întregi pozitive alese aleatoriu să fie coprime este , în sensul că pentru , probabilitatea ca numerele întregi pozitive mai mici decât (și alese aleatoriu) să fie coprime tinde să . Aici  este funcția zeta Riemann .

Tabelul numerelor coprime până la 30

Fiecare celulă conține cel mai mare divizor comun al coordonatelor sale, iar unitățile corespunzătoare perechilor de coordonate coprime sunt evidențiate în întuneric. Din proprietatea descrisă mai sus, rezultă că densitatea medie a celulelor întunecate atunci când tabelul este extins la infinit devine egală cu .

Variații și generalizări

Conceptele de numere prime , cel mai mare divizor comun și numere coprime se generalizează în mod natural la inele euclidiene arbitrare , cum ar fi inelul polinomial sau numerele întregi gaussiene . O generalizare a conceptului de număr prim este „ elementul ireductibil ”. Definiția de mai sus a numerelor coprime nu este potrivită pentru un inel euclidian arbitrar, deoarece pot exista divizori de unități în inel ; în special, GCD este definit până la înmulțirea cu un divizor al unității. Prin urmare, definiția numerelor prime relativ ar trebui modificată [6] .

Formulări echivalente [6] :

• Elementele unui inel euclidian sunt coprime dacă nu au divizori comuni, alții decât divizorii unităților.
• ( Relația lui Bezout ) Elementele unui inel euclidian sunt coprime dacă și numai dacă există elemente astfel încât

Lema lui Euclid este valabilă și .

Aplicație practică

Proprietatea simplității reciproce nu numai că joacă un rol important în teoria numerelor și algebra comutativă , dar are o serie de aplicații practice importante, în special, numărul de dinți pe pinioane și numărul de zale dintr-o transmisie cu lanț tind să fie relativ prime, care asigură o uzură uniformă: fiecare dinte al pinionului va lucra pe rând cu toate verigile lanțului.

Note

1. ↑ 1 2 numere coprime. // Enciclopedie matematică (în 5 volume). - M .: Enciclopedia Sovietică , 1977. - T. 1. - S. 690.
2. ↑ R. Graham, D. Knuth, O. Patashnik. Matematică concretă . - M . : „Mir”, 1998. - S.  139 . - 703 p. — ISBN 5-03-001793-3 .
3. ↑ 1 2 Mihailovici, 1967 , p. 28.
4. ↑ Nesterenko Yu. V. Teoria numerelor. - M . : Centrul de Editură „Academia”, 2008. - S. 40. - 272 p. — ISBN 9785769546464 .
5. ↑ Mihailovici, 1967 , p. 64.
6. ↑ 1 2 Larin S. V. Algebră și teoria numerelor. Grupuri, inele și câmpuri: manual. manual pentru bacalaureat academic. - Ed. a II-a. - M. : Yurait, 2018. - S. 92-93. — 160 s. — (Licenţă. Curs academic). - ISBN 978-5-534-05567-2 .

Literatură

• Numerele coprime  // Marea Enciclopedie Sovietică  : în 66 de volume (65 de volume și 1 suplimentar) / cap. ed. O. Yu. Schmidt . - M.  : Enciclopedia sovietică , 1926-1947.
• Mihailovici Sh. Kh. Teoria numerelor. - Ed. a II-a. - M . : Şcoala superioară, 1967. - 336 p.