Divizibilitate și Numere PrimeCel Mai Mic Multiplu Comun

Doi alergători se antrenează pe o pistă de alergare de formă circulară. Primul alergător face un tur în 60 de secunde. Al doilea alergător face un tur în doar 40 de secunde. Dacă ambii pornesc în același timp de la linia de start, când se vor întâlni din nou la start?

Această intrebare chiar nu este despre geometria pistei de alergare sau despre viteză - este despre multipli și divizibilitate.

Primul alergător trece linia de start după 60s, 120s, 180s, 240s, ș.a.m.d. Aceștia sunt pur și simplu multipliifactorii lui 60. Al doilea alergător trece linia de start după 40s, 80s, 120s, 160s, ș.a.m.d. Primul moment când ambii alergători se află din nou la linia de start este după seconds.

Rezultatul găsit este cel mai mic număr care este și multiplul lui 40 și multiplul lui 60. Acesta se numește cel mai mic multiplu comun sau cmmmc.

Pentru a afla cmmmc pentru două numere oarecare, este important să ne dăm seama că dacă a divide pe b, atunci b are nevoie să conțină toți factorii primi ai lui a (plus alți câțiva):

Se verifică ușor: dacă un factor prim divide pe a și a divide pe b, atunci acel factor prim divide și el pe b.

Pentru a afla cmmmc pentru 40 și 60, avem nevoie să facem mai întâi descompunerea în factori primi a ambelor numere:

Să presupunem că X este cmmmc al lui 40 și al lui 60. Atunci 40 divide pe X, deci 2, 2, 2 și 5 sunt factorii primi ai lui X. De asemenea, 60 divide pe X, deci 2, 2, 3 și 5 sunt factorii primi ai lui X.

Pentru a afla X, vom combina pur și simplu toți factorii primi ai lui 40 și ai lui 60, dar vom utiliza duplicatele o singură dată:

X  =  2 × 2 × 2 × 3 × 5

Rezultă că X = 120, exact cum s-a văzut mai sus. De observat că dacă un factor prim apare de mai multe ori, precum 2 mai sus, avem nevoie să pastrăm numărul maxim de apariții într-unul din cele două numere (de 3 ori în 40 este mai mult decât de 2 ori în 60).

Acum avem o metodă simplă de calculare a cmmmc a două numere:

1. Descompune în factori primi fiecare număr.
2. Combină toți factorii primi, dar numără duplicatele o singură dată.

Putem folosi aceeași metodă pentru a calcula cmmmc pentru trei sau mai multe numere simultan, precum 12, 30 and 45:

Așadar cmmmc pentru 12, 30 și 45 este 2 × × 3 × 3 × = 180.

Numerele prime sunt un caz special: cmmmc pentru două numere prime diferite este pur și simplu produsulsumadiferența lor, pentru că ele nu au niciun factor prim comun care s-ar putea “tăia”.

Cicadele

Și 1, și 17 sunt numere prime și există o explicație pertinentă pentru asta. Imaginează-ți că în pădure există predatori care omoară cicadele. Acești predatori apar și ei la intervale regulate, să zicem la fiecare 6 ani.

Acum imaginează-ți ca o generație de cicade apare o dată la fiecare ${n} de ani (${isPrime(n) ? 'prime' : 'not prime'}). Cele două animale s-ar întâlni o dată la fiecare ${lcm(n,6)} ani, care este cmmmcprodusulmedia lui 6 și ${n}.

Acest număr pare să fie mult mai mare dacă durata ciclului de viață al cicadei este un număr prim precum 13 și 17. Este așa pentru că numerele prime nu au factori comuni cu 6, astfel că la calcularea cmmmc nu tăiem niciun factor duplicat.

Bineînțeles că cicadele nu au nicio idee ce sunt numerele prime, dar de-a lungul a milioane de ani evoluția a stabilit că numerele prime sunt cea mai sigură opțiune pentru durata ciclului de viață. Animalul prădător pare să fi dispărut de-a lungul timpului, dar ciclurile de viață cu numere prime au ramas.