Cel mai mare divizor comun al nodurilor

Orice număr natural este întotdeauna divizibil cu 1 și în sine. Numărul 2 este cel mai mic număr prime. Acesta este singurul număr prime, numerele prime rămase sunt impare.

Există multe numere prime, iar primul dintre ele este numărul 2. Cu toate acestea, nu există ultimul număr prime.

Dar multe numere naturale sunt împărțite uniform în alte numere naturale.

- numărul 12 este împărțit în 1, 2, 3, 4, 6, 12;

- numărul 36 este împărțit în 1, 2, 3, 4, 6, 12, 18, 36.

Numerele la care este împărțit numărul în întregime (pentru 12 sunt 1, 2, 3, 4, 6 și 12) sunt numiți divizori ai unui număr. Un divizor al unui număr natural a este un număr natural care împarte un număr dat a fără un rest. Un număr natural care are mai mult de doi divizori se numește compozit. Rețineți că numerele 12 și 36 au divizoare comune. Aceste numere sunt: 1, 2, 3, 4, 6, 12. Cel mai mare divizor al acestor numere este 12.

Divizorul comun al celor două numere date a și b este numărul prin care ambele numere a și b sunt divizibile fără rest. Divizorul comun al mai multor numere (GCD) este un număr care servește ca divizor pentru fiecare dintre ele.

Pe scurt, cel mai mare divizor comun al a și b este scris ca:

Un exemplu. DUMNEZEU (12, 36) = 12.

Divizoarele numerelor din înregistrarea soluției sunt notate cu un "D" mare.

Numerele 7 și 9 au doar un singur divizor comun - numărul 1. Aceste numere sunt numite slimes reciproc simple.

Numerele primare sunt numere naturale care au doar un divizor comun - numărul 1. GCD este egal cu 1.

Cel mai mare divizor comun (GCD), proprietăți.

Proprietatea principală: cel mai mare divizor comun m și n este divizibil de orice divizor comun al acestor numere. Un exemplu. pentru numerele 12 și 18, cel mai mare divizor comun este de 6; este împărțită în toți divizorii obișnuiți ai acestor numere: 1, 2, 3, 6.
Corolarul 1: setul de divizori comuni m și n coincide cu setul de divizori ai GCD (m. N).
Corolarul 2: mulțimea comună m și n coincide cu mulțimea de LCM-uri multiple (m. N).

Dacă m este divizibil cu n. apoi GCD (m. n) = n. În special, GCD (n. N) = n.
- factorul comun poate fi considerat ca semn GCD.
Dacă, după diviziunea prin numere, devin reciproc simple, adică.

Acest lucru înseamnă, printre altele, că, pentru a aduce împușcat la ireductibilă înseamnă că este necesar să se împartă numărătorul și numitorul prin GCD lor.

Multiplicitatea: dacă este reciproc simplă, atunci:

Cel mai mare divizor comun al numerelor m și n poate fi definit ca cel mai mic element pozitiv al setului tuturor combinațiilor lor liniare:

și prin urmare o reprezentăm sub forma unei combinații liniare a numerelor m și n:

Această relație se numește relația Bezout. iar coeficienții u și v sunt coeficienții Bezout. Coeficienții Bezout sunt efectiv calculați prin algoritmul extins Euclidian. Această afirmație poate fi generalizat la seturi de numere naturale - sensul său este că subgrupa generat de un set - ciclic și este generat de un singur element: GCD (a1 a2 ... un ...).

Calculul celui mai mare divizor comun (GCD).

Metodele eficiente pentru calculul GCD a două numere sunt algoritmul euclidian și algoritmul binar. În plus, valoarea GCD (m, n) poate fi ușor calculată dacă este cunoscută descompunerea canonică a m și n în factori simpli:

unde numerele prime sunt diferite, și u sunt numerele întregi nonnegative (ele pot fi zerouri dacă primele corespunzătoare sunt absente în expansiune). Apoi GCD (m, n) și LCM (m, n) sunt exprimate prin formule:

Dacă există mai mult de două numere :, GCD-ul lor se găsește prin următorul algoritm:

- acesta este GCD necesar.

De asemenea, pentru a găsi cel mai mare divizor comun. se poate extinde fiecare dintre numerele date prin factori primari. Apoi scrieți separat numai acei factori care intră în toate numerele date. Apoi multiplicăm numerele scrise între ele - rezultatul multiplicării și este cel mai mare divizor comun.

Să analizăm pas cu pas calculul celui mai mare divizor comun:

1. Extindeți divizorii numerelor în principalii factori:

Calculele pot fi înregistrate convenabil utilizând o bară verticală. În stânga liniei, scrieți mai întâi dividendul, pe dreapta - divizorul. Mai jos, în coloana din stânga, notăm valorile coeficienților. Să explicăm dintr-o dată un exemplu. Noi descompunem numerele 28 și 64 în principalii factori.