Glosar

Selectați unul dintre cuvintele cheie din stânga ...

Divizibilitate și Numere PrimeCel Mai Mic Multiplu Comun

Timp de citit: ~20 min

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?

START 40 80 120 60 120

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 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):

12
60
2
 × 
2
 × 
3
2
 × 
2
 × 
3
 × 
5

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:

40
=
2
×
2
×
2
×
5
60
=
2
×
2
×
3
×
5

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:

12
=
2
×
2
×
3
30
=
2
×
3
×
5
45
=
3
×
3
×
5

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 lor, pentru că ele nu au niciun factor prim comun care s-ar putea “tăia”.

Cicadele

America de Nord găzduiește diferite familii de cicade. Acestea au o caracteristică interesantă

  • apar la suprafață pentru a se înmulți doar o dată la câțiva ani în timpul verii - restul timpului și-l petrec în subteran.

De exemplu, cicadele din Florida și Mississippi apar o dată la 13 ani. Cicadele din Illinois și Iowa apar doar o dată la 17 ani. Dar nu există cicade cu ciclul de viață de 12, 14, 15 sau 16 ani.

Ș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 lui 6 și ${n}.

4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

Durata până la întalnirea cicadelor cu prădătorii, pentru diferite lungimi de ciclu de viață al cicadelor.

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.