Numere întregi coprimă - Coprime integers

În teoria numerelor , două numere întregi $a$ și $b$ sunt prime între ele , relativ prim sau mutual prime dacă este un număr întreg pozitiv numai că este un divizor de ambele dintre ele este 1. Prin urmare, orice număr prim care separă unul de $un$ sau $b$ nu divide celălalt . Acest lucru este echivalent cu lor cel mai mare divizor comun (GCD) fiind 1. Se spune , de asemenea , $un$ este prim pentru a $b$ sau $o$ este cu prime între ele $b$ .

Numărătorul și numitorul unei fracții reduse sunt coprimi. Numerele 14 și 25 sunt coprimă, deoarece 1 este singurul lor divizor comun. Pe de altă parte, 14 și 21 nu sunt coprimă, deoarece ambele sunt divizibile cu 7.

Notare și testare

Notațiile standard pentru numere întregi relativ prime $a$ și $b$ sunt: $mcd (a, b) = 1$ și $(a, b) = 1$ . În manualul lor din 1989, Ronald Graham , Donald Knuth și Oren Patashnik au propus ca notația să fie utilizată pentru a indica faptul că $a$ și $b$ sunt relativ prime și că termenul „prim” trebuie utilizat în locul coprimei (așa cum este în $a$ este prim la $b$ ) . ${\ displaystyle a \ perp b}$

O modalitate rapidă de a determina dacă două numere sunt coprimă este dată de algoritmul euclidian și de variantele sale mai rapide, cum ar fi algoritmul GCD binar sau algoritmul GCD al lui Lehmer .

Numărul coprimelor întregi cu un număr întreg pozitiv $n$ , între 1 și $n$ , este dat de funcția totient a lui Euler , cunoscută și sub numele de funcția ph a lui Euler, $φ (n)$ .

Un set de numere întregi poate fi numit și coprimă dacă elementele sale nu au niciun factor pozitiv comun, cu excepția 1. O condiție mai puternică pe un set de numere întregi este coprimă pereche, ceea ce înseamnă că $a$ și $b$ sunt coprimă pentru fiecare pereche $(a, b)$ de diferite numere întregi în set. Setul ${2, 3, 4$ } este coprimă, dar nu este coprimă pereche, deoarece 2 și 4 nu sunt relativ prime.

Proprietăți

Numerele 1 și −1 sunt singurele numere întregi coprimă cu fiecare număr întreg și sunt singurele numere întregi care sunt coprimă cu 0.

Un număr de condiții sunt echivalente cu $a$ și $b$ fiind coprimă:

Niciun număr prim nu împarte atât $a$ cât și $b$ .
Există numere întregi $x$ și $y$ astfel încât $ax + by = 1$ (vezi identitatea lui Bézout ).
Numărul întreg $b$ are un modul invers multiplicativ $a$ , ceea ce înseamnă că există un număr întreg $y$ astfel încât $prin \equiv 1 (mod a)$ . În limbajul teoretic inelar, $b$ este o unitate din inelul $Z / a Z$ al numărului întreg modulo $a$ .
Fiecare pereche de relații congruență pentru un întreg necunoscut $x$ , de forma $x \equiv k (mod a)$ și $x \equiv m (mod b)$ , are o soluție ( rest teorema chineză ); de fapt soluțiile sunt descrise printr-o singură relație de congruență modulo $ab$ .
Cel mai mic multiplu comun al lui $a$ și $b$ este egal cu produsul lor $ab$ , adică $mcm (a, b) = ab$ .

Ca o consecință a celui de-al treilea punct, dacă a și b sunt coprimă și br ≡ bs ( mod a ), atunci r ≡ s (mod a ). Adică, putem „împărți la b ” atunci când lucrăm la modulul a . Mai mult decât atât, în cazul în care b ₁ și b ₂ sunt ambele cu prime între ele o , atunci așa este produsul lor b ₁b ₂ (adică, modulo o este un produs al elementelor inversabilă, și , prin urmare , inversabile); aceasta rezultă și din primul punct de lema lui Euclid , care afirmă că dacă un număr prim p împarte un produs bc , atunci p împarte cel puțin unul dintre factorii b , c .

Ca o consecință a primului punct, dacă a și b sunt coprimă, atunci la fel sunt și puterile a ^k și b ^m .

Dacă a și b sunt coprimă și a împarte produsul bc , atunci a împarte c . Aceasta poate fi privită ca o generalizare a lemei lui Euclid.

Figura 1. Numerele 4 și 9 sunt coprimă. Prin urmare, diagonala unei rețele 4 × 9 nu intersectează niciun alt punct de rețea

Cele două numere întregi a și b sunt coprimă dacă și numai dacă punctul cu coordonatele ( a , b ) dintr-un sistem de coordonate carteziene este „vizibil” de la origine (0,0), în sensul că nu există niciun punct cu coordonate întregi pe segmentul de linie dintre origine și ( a , b ). (A se vedea figura 1.)

Într-un sens care poate fi precis, probabilitatea ca două numere întregi alese aleatoriu să fie coprimă este 6 / π ² (vezi pi ), care este de aproximativ 61%. Vezi mai jos.

Două numere naturale a și b sunt coprimă dacă și numai dacă numerele 2 ^a - 1 și 2 ^b - 1 sunt coprimă. Ca o generalizare a acestui fapt, urmând cu ușurință algoritmul euclidian în baza n > 1:

{\ displaystyle \ gcd \ left (n ^ {a} -1, n ^ {b} -1 \ right) = n ^ {\ gcd (a, b)} - 1.}

Coprimalitatea în seturi

Un set de numere întregi S = { a ₁ , a ₂ , .... o _n } poate fi numită și prime între ele sau prime între ele setwise dacă cmmdc al tuturor elementelor setului este 1. De exemplu, numerele întregi 6, 10, 15 sunt coprimă deoarece 1 este singurul număr întreg pozitiv care le împarte pe toate.

Dacă fiecare pereche dintr-un set de numere întregi este coprimă, atunci se spune că setul este coprimă pereche (sau pereche relativ primă , reciproc coprime sau reciproc relativ primă ). Coprimalitatea pereche este o condiție mai puternică decât coprimalitatea setată; fiecare set finit de coprimă pereche este, de asemenea, coprimă setwise, dar inversul nu este adevărat. De exemplu, numerele întregi 4, 5, 6 sunt coprimă (setwise) (deoarece singurul număr întreg pozitiv care le împarte pe toate este 1), dar nu sunt coprimă pereche (deoarece gcd (4, 6) = 2).

Conceptul de coprimalitate în perechi este important ca ipoteză în multe rezultate ale teoriei numerelor, cum ar fi teorema restului chinezesc .

Este posibil ca un set infinit de numere întregi să fie coprimă în perechi. Exemple notabile includ setul tuturor numerelor prime, setul de elemente din secvența lui Sylvester și setul tuturor numerelor Fermat .

Coprimalitatea în idealuri inelare

Două idealuri A și B într - un inel comutativ R sunt numite prime între ele (sau comaximal ) dacă A + B = R . Aceasta generalizează identitatea lui Bézout : cu această definiție, două idealuri principale ( a ) și ( b ) în inelul numerelor întregi Z sunt coprimă dacă și numai dacă a și b sunt coprimă. Dacă idealurile A și B ale lui R sunt coprimă, atunci AB = A ∩ B ; în plus, în cazul în care C este un al treilea ideală astfel încât A conține BC , atunci A conține C . Teorema a restului chinezesc poate fi generalizat la orice inel comutativ, folosind idealurile prime între ele.

Probabilitatea coprimalității

Având în vedere două numere întregi alese aleatoriu a și b , este rezonabil să ne întrebăm cât de probabil este ca a și b să fie coprimă. În această determinare, este convenabil să se utilizeze caracterizarea că a și b sunt coprimă dacă și numai dacă niciun număr prim nu le împarte pe amândouă (a se vedea Teorema fundamentală a aritmeticii ).

În mod informal, probabilitatea ca orice număr să fie divizibil cu un prim (sau de fapt orice număr întreg) este ; de exemplu, fiecare al 7-lea număr întreg este divizibil cu 7. Prin urmare, probabilitatea ca două numere să fie ambele divizibile cu p este , iar probabilitatea ca cel puțin unul dintre ele să nu fie este . Orice colecție finită de evenimente de divizibilitate asociate primilor distincti este independentă reciproc. De exemplu, în cazul a două evenimente, un număr este divizibil cu primele p și q dacă și numai dacă este divizibil cu pq ; ultimul eveniment are probabilitatea 1 / pq . Dacă se face presupunerea euristică că un astfel de raționament poate fi extins la infinit de multe evenimente de divizibilitate, este condus să presupunem că probabilitatea ca două numere să fie coprimă este dată de un produs peste toate primele, ${\ displaystyle p}$ ${\ displaystyle 1 / p}$ ${\ displaystyle 1 / p ^ {2}}$ ${\ displaystyle 1-1 / p ^ {2}}$

{\ displaystyle \ prod _ {{\ text {prime}} p} \ left (1 - {\ frac {1} {p ^ {2}}} \ right) = \ left (\ prod _ {{\ text { prime}} p} {\ frac {1} {1-p ^ {- 2}}} \ right) ^ {- 1} = {\ frac {1} {\ zeta (2)}} = {\ frac { 6} {\ pi ^ {2}}} \ aproximativ 0.607927102 \ aproximativ 61 \%.}

Aici ζ se referă la funcția zeta Riemann , identitatea referitoare produsul peste amorse la ζ (2) este un exemplu al unui produs Euler , iar evaluarea ζ (2) ca π ² /6 este problema Basel , rezolvată de Leonhard Euler în 1735.

Nu există nicio modalitate de a alege un număr întreg pozitiv la întâmplare, astfel încât fiecare număr întreg pozitiv să apară cu probabilitate egală, dar enunțurile despre „numere întregi alese la întâmplare”, precum cele de mai sus, pot fi formalizate prin utilizarea noțiunii de densitate naturală . Pentru fiecare număr întreg pozitiv N , fie P _N probabilitatea ca două numere alese aleatoriu să fie coprimă. Deși P _N nu va egala niciodată exact, cu munca se poate arăta că în limita ca probabilitatea se apropie . ${\ displaystyle \ {1,2, \ ldots, N \}}$ ${\ displaystyle 6 / \ pi ^ {2}}$ ${\ displaystyle N \ to \ infty}$ ${\ displaystyle P_ {N}}$ ${\ displaystyle 6 / \ pi ^ {2}}$

Mai general, probabilitatea ca k numere întregi alese aleatoriu să fie coprimă este . ${\ displaystyle 1 / {\ zeta (k)}}$

Generarea tuturor perechilor coprimă

Ordinea de generare a perechilor coprimă prin acest algoritm. Primul nod (2,1) este marcat cu roșu, cei trei copii ai acestuia sunt afișați în portocaliu, a treia generație este galbenă și așa mai departe în ordinea curcubeului.

Toate perechile de numere coprimă pozitive (cu ) pot fi aranjate în doi arbori ternari complet disjunsi , un arbore pornind de la (pentru perechi pare-impare și impar-pare), iar celălalt arbore pornind de la (pentru perechi impar-impar). Copiii fiecărui vârf sunt generați după cum urmează: ${\ displaystyle (m, n)}$ ${\ displaystyle m> n}$ ${\ displaystyle (2,1)}$ ${\ displaystyle (3,1)}$ ${\ displaystyle (m, n)}$

Ramura 1: ${\ displaystyle (2m-n, m)}$
Ramura 2: ${\ displaystyle (2m + n, m)}$
Sucursala 3: ${\ displaystyle (m + 2n, n)}$

Această schemă este exhaustivă și nu este redundantă, fără membri invalizi.

Aplicații

În proiectarea mașinilor, o uzură uniformă și uniformă a angrenajului este obținută prin alegerea numărului de dinți ai celor două trepte de viteză care se unesc pentru a fi relativ prime. Când se dorește un raport de transmisie 1: 1, între ele poate fi introdusă o transmisie relativ primară la cele două angrenaje de dimensiuni egale.

În criptografia pre-computer , unele mașini de cifrat Vernam au combinat mai multe bucle de bandă de chei de diferite lungimi. Multe mașini cu rotor combină rotori cu diferite numere de dinți. Astfel de combinații funcționează cel mai bine atunci când întregul set de lungimi este coprimă în perechi.

Vezi si

Note

Referințe

Hardy, GH ; Wright, EM (2008), An Introduction to Theory of Numbers (ediția a VI-a), Oxford University Press , ISBN 978-0-19-921986-5
Niven, Ivan; Zuckerman, Herbert S. (1966), O introducere în teoria numerelor (ediția a doua), John Wiley & Sons
Ore, Oystein (1988) [1948], The Number Number and Its History , Dover, ISBN 978-0-486-65620-5
Rosen, Kenneth H. (1992), The Elementary Number Theory and its Applications (ed. A 3-a), Addison-Wesley, ISBN 978-0-201-57889-8

Lecturi suplimentare

Lord, Nick (martie 2008), „O construcție uniformă a unor secvențe de coprimă infinite”, Mathematical Gazette , 92 : 66–70.

Languages

In other projects