Ce este interprime. §3

Ce este interprime. §3

Manualele de matematică sunt uneori greu de citit. Limbajul sec și clar al autorilor nu este întotdeauna ușor de înțeles. Da, iar subiectele de acolo sunt întotdeauna interconectate, curgând reciproc. Pentru a stăpâni un subiect, trebuie să ridicați un număr de subiecte anterioare și, uneori, să răsfoiți întregul manual. Dificil? Da. Și să ne asumăm riscul de a ocoli aceste dificultăți și să încercăm să găsim o abordare non-standard a subiectului. Să facem un fel de excursie în țara numerelor. Totuși, vom lăsa definiția aceeași, deoarece regulile matematicii nu pot fi anulate. Deci reciproc numere prime sunt numere naturale cu un divizor comun egal cu unu. Este clar? Destul de.

Pentru mai mult bun exemplu să luăm numerele 6 și 13. Ambele sunt divizibile cu unul (coprime). Dar numerele 12 și 14 nu pot fi astfel, deoarece sunt divizibile nu numai cu 1, ci și cu 2. Următoarele numere - 21 și 47, de asemenea, nu se încadrează în categoria „numerelor coprime”: ele pot fi împărțite nu numai la 1, ci și la 7.

Numerele coprime se notează după cum urmează: ( A, y) = 1.

Se poate spune și mai simplu: divizorul comun (cel mai mare) aici este egal cu unu.
De ce avem nevoie de asemenea cunoștințe? Motiv suficient.

Incluse reciproc în unele sisteme de criptare. Cei care lucrează cu cifrurile Hill sau cu sistemul de substituție Caesar înțeleg că fără aceste cunoștințe, nu poți ajunge nicăieri. Dacă ați auzit despre generatoare, atunci este puțin probabil să îndrăznești să negi: numerele coprime sunt folosite și acolo.

Acum să vorbim despre modalități de a obține astfel de simple, după cum înțelegeți, pot avea doar doi divizori: sunt divizibili prin ei înșiși și cu unul. Să presupunem că 11, 7, 5, 3 sunt numere prime, dar 9 nu este, deoarece acest număr este deja divizibil cu 9, 3 și 1.

Si daca A este un număr prim și la- din set (1, 2,... A- 1), atunci este garantat ( A, la) = 1 sau numere coprime — AȘi la.

Aceasta nu este, mai degrabă, nici măcar o explicație, ci o repetare sau o rezumare a ceea ce tocmai s-a spus.

Obținerea numerelor prime este posibilă, însă, pentru numere impresionante (miliarde, de exemplu), această metodă este prea lungă, dar, spre deosebire de super-formule, care greșesc uneori, este mai fiabilă.

Poate lucra prin alegere la > A. Pentru a face acest lucru, y este ales astfel încât numărul pornit A nu a împărtășit. Pentru a face acest lucru, un număr prim este înmulțit cu un număr natural și se adaugă o valoare (sau, dimpotrivă, se scade) (de exemplu, R), care este mai puțin A:

y= R a + k

Dacă, de exemplu, A = 71, R= 3, q=10, apoi, respectiv, la aici va fi egal cu 713. Este posibilă o altă selecție, cu grade.

Numerele compuse, spre deosebire de numerele coprime, sunt divizibile cu ele însele, cu 1 și cu alte numere (și fără rest).

Cu alte cuvinte, (cu excepția unuia) sunt împărțite în compozite și simple.

Numerele prime sunt numere naturale care nu au divizori non-triviali (altele decât numărul în sine și unitatea). Rolul lor este deosebit de important în criptografia actuală, modernă, în dezvoltare rapidă, datorită căreia, considerată anterior o disciplină extrem de abstractă, a devenit atât de solicitată: algoritmii de protecție a datelor sunt în permanență îmbunătățiți.

Cel mai mare număr prim a fost găsit de medicul oftalmolog Martin Nowak, care a participat la proiectul GIMPS (computing de distribuție), împreună cu alți entuziaști, dintre care au fost aproximativ 15 mii. A fost nevoie de șase pentru a calcula de ani lungi. Au fost implicate două duzini și jumătate de calculatoare situate în clinica oftalmologică a lui Novak. Rezultatul muncii și perseverenței titanice a fost numărul 225964951-1, scris cu 7816230 de zecimale. De altfel, înregistrarea un numar mare a fost livrat cu șase luni înainte de această descoperire. Și au fost cu jumătate de milion mai puține semne.

Un geniu care vrea să numească un număr în care durata recordului zecimal „sare” peste marca de zece milioane are șansa să primească nu numai faimă în întreaga lume, ci și 100.000 de dolari. Apropo, Nayan Khairatwal a primit o sumă mai mică (50.000 de dolari) pentru numărul care a depășit pragul milionului.

În acest articol, vom vorbi despre ce sunt numerele coprime. În primul paragraf, formulăm definiții pentru două, trei sau mai multe numere coprime, dăm mai multe exemple și arătăm în ce cazuri două numere pot fi considerate prime unul față de celălalt. După aceea, ne întoarcem la formularea principalelor proprietăți și dovezile lor. În ultimul paragraf, vom vorbi despre un concept înrudit - numere prime perechi.

Yandex.RTB R-A-339285-1

Ce sunt numerele coprime

Ambele două numere întregi și mai multe dintre ele pot fi coprime. Pentru început, introducem o definiție pentru două numere, pentru care avem nevoie de conceptul celui mai mare divizor comun al acestora. Dacă este necesar, repetă materialul dedicat acestuia.

Definiția 1

Două astfel de numere a și b vor fi reciproc prime, cel mai mare divizor comun al cărora este egal cu 1, adică. mcd (a, b) = 1.

Din această definiție putem concluziona că singurul divizor comun pozitiv al două numere coprime va fi egal cu 1. Doar două astfel de numere au doi divizori comuni - unu și minus unu.

Care sunt câteva exemple de numere relativ prime? De exemplu, o astfel de pereche ar fi 5 și 11. Au un singur divizor pozitiv comun, egal cu 1, ceea ce este o confirmare a simplității lor reciproce.

Dacă luăm două numere prime, atunci unul față de celălalt vor fi relativ prime în toate cazurile, dar astfel de relații reciproce se formează și între numerele compuse. Există cazuri când un număr dintr-o pereche de coprime este compus, iar al doilea este prim sau ambele sunt compuse.

Această afirmație este ilustrată de următorul exemplu: numerele compuse - 9 și 8 formează o pereche între prime. Să demonstrăm acest lucru calculând cel mai mare divizor comun al lor. Pentru a face acest lucru, notăm toți divizorii lor (recomandăm să recitiți articolul despre găsirea divizorilor unui număr). Pentru 8, acestea vor fi numerele ± 1, ± 2, ± 4, ± 8 și pentru 9 - ± 1, ± 3, ± 9. Alegem dintre toți divizorii pe cel care va fi comun și cel mai mare - acesta este unul. Prin urmare, dacă mcd (8, - 9) = 1, atunci 8 și - 9 vor fi coprime unul față de celălalt.

500 și 45 nu sunt numere prime reciproc, deoarece au un alt divizor comun - 5 (vezi articolul despre semnele divizibilității cu 5). Cinci este mai mare decât unu și este un număr pozitiv. O altă pereche similară ar putea fi - 201 și 3 , deoarece ambele pot fi împărțite la 3 , așa cum este indicat de semnul corespunzător divizibilitate.

În practică, este destul de comun să se determine primitatea reciprocă a două numere întregi. Aflarea acestui lucru poate fi redusă la găsirea celui mai mare divizor comun și compararea acestuia cu unul. De asemenea, este convenabil să folosiți un tabel de numere prime pentru a nu face calcule inutile: dacă unul dintre numerele date se află în acest tabel, atunci este divizibil doar cu unul și de la sine. Să aruncăm o privire la o soluție la această problemă.

Exemplul 1

Condiție: află dacă numerele 275 și 84 sunt între prime.

Soluţie

Ambele numere au în mod clar mai mult de un divizor, așa că nu le putem numi imediat coprime.

Calculați cel mai mare divizor comun folosind algoritmul euclidian: 275 = 84 3 + 23 , 84 = 23 3 + 15 , 23 = 15 1 + 8 , 15 = 8 1 + 7 , 8 = 7 1 + 1 , 7 = 7 1 .

Răspuns:întrucât mcd (84, 275) = 1, atunci aceste numere vor fi coprime.

După cum am spus mai devreme, definiția unor astfel de numere poate fi extinsă la cazurile în care nu avem două numere, ci mai multe.

Definiția 2

Numerele întregi coprime a 1 , a 2 , … , a k , k > 2 vor fi atunci când au cel mai mare divizor comun egal cu 1 .

Cu alte cuvinte, dacă avem o mulțime de numere cu cel mai mare divizor pozitiv mai mare decât 1, atunci toate aceste numere nu sunt reciproc inverse unul față de celălalt.

Să luăm câteva exemple. Deci, numerele întregi - 99 , 17 și - 27 sunt coprime. Orice număr de numere prime va fi coprime în raport cu toți membrii populației, cum ar fi în secvența 2 , 3 , 11 , 19 , 151 , 293 și 667 . Dar numerele 12 , − 9 , 900 și − 72 coprime nu vor fi, deoarece pe lângă unitate vor mai avea un divizor pozitiv egal cu 3. Același lucru este valabil și pentru numerele 17, 85 și 187: cu excepția unuia, toate pot fi împărțite la 17.

De obicei, simplitatea reciprocă a numerelor nu este evidentă la prima vedere, acest fapt trebuie dovedit. Pentru a afla dacă unele numere sunt coprime, trebuie să găsiți cel mai mare divizor comun al lor și să trageți o concluzie pe baza comparației cu unul.

Exemplul 2

Condiție: determinați dacă numerele 331 , 463 și 733 sunt între prime.

Soluţie

Să verificăm tabelul numerelor prime și să stabilim că toate aceste trei numere sunt în el. Atunci divizorul lor comun poate fi doar unul.

Răspuns: toate aceste numere vor fi relativ prime între ele.

Exemplul 3

Condiție: dați dovada că numerele − 14 , 105 , − 2 107 și − 91 nu sunt coprime.

Soluţie

Să începem prin a găsi cel mai mare divizor comun al lor, după care ne asigurăm că acesta nu este egal cu 1 . Deoarece numerele negative au aceiași divizori ca și cele pozitive corespondente, atunci mcd (− 14 , 105 , 2 107 , − 91) = mcd (14 , 105 , 2 107 , 91) . Conform regulilor pe care le-am dat în articolul despre găsirea celui mai mare divizor comun, în acest caz, GCD va fi egal cu șapte.

Răspuns:șapte este mai mare decât unu, ceea ce înseamnă că aceste numere nu sunt coprime.

Proprietățile de bază ale numerelor coprime

Astfel de numere au unele proprietăți practic importante. Le enumerăm în ordine și le dovedim.

Definiția 3

Dacă împărțim numerele întregi a și b la numărul corespunzător celui mai mare divizor comun al lor, obținem numere prime relativ. Cu alte cuvinte, a: mcd(a, b) și b: mcd(a, b) vor fi coprime.

Am dovedit deja această proprietate. Dovada poate fi găsită în articolul despre proprietățile celui mai mare divizor comun. Datorită acesteia, putem defini perechi de numere coprime: luați doar două numere întregi și împărțiți la mcd. Ca rezultat, ar trebui să obținem numere coprime.

Definiția 4

O condiție necesară și suficientă pentru simplitatea reciprocă a numerelor a și b este existența unor astfel de numere întregi tu 0Și v0, pentru care egalitatea a u 0 + b v 0 = 1 va fi adevărat.

Dovada 1

Începem prin a demonstra necesitatea acestei condiții. Să presupunem că avem două numere prime relativ, etichetate a și b. Apoi, prin definiția acestui concept, cel mai mare divizor comun al lor va fi egal cu unu. Știm din proprietățile mcd că pentru numerele întregi a și b există o relație Bezout a u 0 + b v 0 = mcd (a, b). Din asta obținem asta a u 0 + b v 0 = 1. După aceea, trebuie să dovedim suficiența condiției. Lasă egalitatea a u 0 + b v 0 = 1 va fi adevărat dacă gcd (a, b)împarte și a , și b, atunci se va împărți și va însuma a u 0 + b v 0, și respectiv unitate (acest lucru poate fi argumentat pe baza proprietăților divizibilității). Și acest lucru este posibil doar dacă mcd(a, b) = 1, ceea ce demonstrează simplitatea reciprocă a lui a și b .

Într-adevăr, dacă a și b sunt coprimi, atunci conform proprietății anterioare, egalitatea va fi adevărată a u 0 + b v 0 = 1. Înmulțim ambele părți cu c și obținem asta a c u 0 + b c v 0 = c. Putem împărți primul termen a c u 0 + b c v 0 prin b , deoarece este posibil pentru a c , iar al doilea termen este și el divizibil cu b , deoarece unul dintre factorii pe care îi avem este b . Din aceasta concluzionăm că întreaga sumă poate fi împărțită la b și, deoarece această sumă este egală cu c, atunci c poate fi împărțită la b.

Definiția 5

Dacă două numere întregi a și b sunt între prime, atunci mcd(a c, b) = mcd(c, b) .

Dovada 2

Să demonstrăm că mcd (a c , b) va împărți mcd (c , b) , iar după aceea - că mcd (c , b) împarte mcd (a c , b) , ceea ce va dovedi egalitatea mcd (a c , b) = mcd (c , b) .

Deoarece mcd (a c , b) împarte atât a c și b și mcd (a c , b) împarte b , va împărți și b c . Aceasta înseamnă că mcd (a c , b) împarte atât a c, cât și b c , prin urmare, datorită proprietăților mcd, împarte și mcd (a c , b c), care va fi egal cu c gcd (a , b) = c . Prin urmare, mcd(a c, b) împarte atât b, cât și c, prin urmare mcd(c, b) împarte și ele.

De asemenea, puteți spune că, deoarece mcd (c, b) împarte atât c, cât și b, atunci va împărți atât c, cât și a c. Aceasta înseamnă că GCD (c , b) împarte atât a c, cât și b, prin urmare, GCD (a c , b) împarte și el.

Astfel, mcd (a c, b) și mcd (c, b) se împart reciproc, ceea ce înseamnă că sunt egale.

Definiția 6

Dacă numerele din succesiune a 1 , a 2 , … , a k vor fi coprime în raport cu numerele șirului b 1 , b 2 , … , b m(pentru valorile naturale ale lui k și m), apoi produsele lor a 1 a 2 … a kȘi b 1 b 2 … b m sunt, de asemenea, coprime, în special, a 1 = a 2 = … = a k = aȘi b 1 = b 2 = ... = b m = b, Acea un kȘi b m sunt coprime.

Dovada 3

Conform proprietății anterioare, putem scrie egalități de următoarea formă: mcd (a 1 a 2 … a k , b m) = mcd (a 2 a k , b m) = … = mcd (a k , b m) = 1 . Posibilitatea ultimei tranziții este asigurată de faptul că a k și b m sunt coprime prin presupunere. Prin urmare, GCD (a 1 · a 2 · … · a k , b m) = 1 .

Notăm a 1 a 2 ... a k = A și obținem că mcd (b 1 b 2 ... b m , a 1 a 2 ... a k) = mcd (b 1 b 2 ... b m , A) = mcd (b 2 ... b b m , A) = ... = mcd (b m , A) = 1 . Acest lucru va fi adevărat datorită ultimei egalități din lanțul construit mai sus. Astfel, am obținut egalitatea mcd (b 1 b 2 … b m , a 1 a 2 … a k) = 1, care poate fi folosită pentru a demonstra simplitatea reciprocă a produselor a 1 a 2 … a kȘi b 1 b 2 … b m

Acestea sunt toate proprietățile numerelor coprime despre care am dori să vă spunem.

Conceptul de numere prime în perechi

Știind ce sunt numerele coprime, putem formula definiția numerelor prime în perechi.

Definiția 7

Numere prime în perechi este o succesiune de numere întregi a 1 , a 2 , … , a k , unde fiecare număr este copprim față de celelalte.

Un exemplu de succesiune de numere prime perechi ar fi 14 , 9 , 17 și - 25 . Aici toate perechile (14 și 9 , 14 și 17 , 14 și − 25 , 9 și 17 , 9 și − 25 , 17 și − 25) sunt coprime. Rețineți că condiția coprime este obligatorie pentru numerele prime în perechi, dar numerele coprime nu vor fi prime în perechi în toate cazurile. De exemplu, în secvența 8 , 16 , 5 și 15 numerele nu sunt așa, deoarece 8 și 16 nu vor fi coprime.

Ar trebui să ne oprim și asupra conceptului de mulțime de un anumit număr de numere prime. Ele vor fi întotdeauna simple atât reciproc, cât și perechi. Un exemplu ar fi secvența 71 , 443 , 857 , 991 . În cazul numerelor prime, conceptele de simplitate reciprocă și perechi vor coincide.

Dacă observați o greșeală în text, vă rugăm să o evidențiați și să apăsați Ctrl+Enter

$p$ se numește număr prim dacă are doar $2$ divizori: $1$ și el însuși.

separator numar natural$a$ este un număr natural cu care numărul original $a$ este divizibil fără rest.

Exemplul 1

Aflați divizorii numărului $6$.

Soluție: Trebuie să găsim toate numerele cu care numărul dat $6$ este divizibil fără rest. Acestea vor fi numere: $1,2,3, 6$. Deci divizorul numărului $6$ vor fi numerele $1,2,3,6.$

Răspuns: $1,2,3,6$.

Deci, pentru a găsi divizorii unui număr, trebuie să găsiți toate numerele naturale prin care dat este divizibil fără rest. Este ușor de observat că numărul $1$ va fi un divizor al oricărui număr natural.

Definiția 2

Compozit Un număr se numește un număr care are alți divizori în afară de unul și el însuși.

Un exemplu de număr prim ar fi $13$, un exemplu de număr compus ar fi $14.$

Observație 1

Numărul $1$ are un singur divizor - acest număr în sine, deci nu este clasificat nici ca prim sau compus.

Numerele coprime

Definiția 3

Numerele coprime cei al căror GCD este egal cu $1$ sunt numiți.Deci, pentru a afla dacă numerele sunt coprime, este necesar să găsiți GCD-ul lor și să-l comparați cu $1$.

Coprime în perechi

Definiția 4

Dacă într-un set de numere oricare două sunt coprime, atunci se numesc astfel de numere coprime perechi. Pentru două numere, conceptele de „coprime” și „coprime în perechi” sunt aceleași.

Exemplul 2

$8, 15$ - nu prime, ci coprime.

$6, 8, 9$ sunt numere coprime, dar nu coprime perechi.

$8, 15, 49$ sunt coprime perechi.

După cum putem vedea, pentru a determina dacă numerele sunt coprime, trebuie mai întâi să le descompuneți în factori primi. Să fim atenți cum să o facem corect.

factorizare primara

De exemplu, să factorizăm numărul $180$:

$180=2\cdot 2\cdot 3\cdot 3\cdot 5$

Folosim proprietatea gradelor, apoi obținem,

$180=2^2\cdot 3^2\cdot 5$

O astfel de reprezentare a descompunerii în factori primi se numește canonică, adică. pentru a factoriza un număr în formă canonică, este necesar să se folosească proprietatea puterii și să se reprezinte numărul ca produs de puteri cu baze diferite.

Descompunerea canonică a unui număr natural în formă generală

Descompunerea canonică a unui număr natural în vedere generala se pare ca:

$m=p^(n1)_1\cdot p^(n2)_2\cdot \dots \dots ..\cdot p^(nk)_k$

unde $p_1,p_2\dots \dots .p_k$ sunt numere prime și exponenți grade – naturale numere.

Reprezentarea unui număr sub forma unei descompunere canonică în mulțimi simple facilitează găsirea celui mai mare divizor comun al numerelor și acționează ca o consecință a demonstrației sau definiției numerelor coprime.

Exemplul 3

Găsiți cel mai mare divizor comun de $180$ și $240$.

Soluție: Descompuneți numerele în mulțimi simple folosind descompunerea canonică

$180=2\cdot 2\cdot 3\cdot 3\cdot 5$, apoi $180=2^2\cdot 3^2\cdot 5$

$240=2\cdot 2\cdot 2\cdot 2\cdot 3\cdot 5$, apoi $240=2^4\cdot 3\cdot 5$

Acum să găsim GCD-ul acestor numere, pentru aceasta alegem grade cu aceeași bază și cu cel mai mic exponent, apoi

$gcd \ (180;240)= 2^2\cdot 3\cdot 5=60$

Să compunem algoritm pentru găsirea mcd ținând cont de descompunerea canonică în factori primi.

Pentru a găsi cel mai mare divizor comun al două numere folosind expansiunea canonică, trebuie să:

  1. factorizează numerele în factori primi în formă canonică
  2. alegeți grade cu aceeași bază și cu cel mai mic exponent al numerelor incluse în descompunerea acestor numere
  3. Găsiți produsul numerelor găsite la pasul 2. Numărul rezultat va fi cel mai mare divizor comun dorit.

Exemplul 4

Stabiliți dacă numerele $195$ și $336$ sunt numere prime, coprime.

    $195=3\cdot 5\cdot 13$

    $336=2\cdot 2\cdot 2\cdot 2\cdot 3\cdot 7=2^4\cdot 3\cdot 5$

    $gcd \ (195;336) =3\cdot 5=15$

Vedem că mcd-ul acestor numere este diferit de $1$, ceea ce înseamnă că numerele nu sunt coprime. De asemenea, vedem că fiecare dintre numere include factori, pe lângă $1$ și numărul în sine, ceea ce înseamnă că nici numerele nu vor fi prime, ci vor fi compuse.

Exemplul 5

Stabiliți dacă numerele $39$ și $112$ sunt numere prime, coprime.

Soluție: Folosim factorizarea canonică pentru factorizare:

    $112=2\cdot 2\cdot 2\cdot 2\cdot 7=2^4\cdot 7$

    $gcd \ (39;112)=1$

Vedem că mcd-ul acestor numere este egal cu $1$, ceea ce înseamnă că numerele sunt coprime. De asemenea, vedem că fiecare dintre numere include factori, pe lângă $1$ și numărul în sine, ceea ce înseamnă că nici numerele nu vor fi prime, ci vor fi compuse.

Exemplul 6

Stabiliți dacă numerele $883$ și $997$ sunt numere prime, coprime.

Soluție: Folosim factorizarea canonică pentru factorizare:

    $883=1\cdot 883$

    $997=1\cdot 997$

    $gcd \ (883;997)=1$

Vedem că mcd-ul acestor numere este egal cu $1$, ceea ce înseamnă că numerele sunt coprime. De asemenea, vedem că fiecare dintre numere include doar factori egali cu $1$ și numărul în sine, ceea ce înseamnă că numerele vor fi prime.