La divisibilitat dels nombres enters positius

1. Introducció
2. A la recerca dels nombres primers
3. Màxim comú divisor i mínim comú múltiple de dos nombres enters positius

1. Introducció
Aquí hi trobareu una proposta metodològica encarada a l'estudi dels nombres primers i la divisibilitat fonamentada en l'experimentació per ordinador de diverses estratègies i processos. Vaig redactar aquestes notes, ja fa molts anys (1999). Els centres d'interès procedimental són l'algorisme d'Eratòstenes i d'altres alternatius elementals per a la recerca sistemàtica de nombres primers així com l'algorisme d'Euclides -- i d'altres més elementals -- per la determinació del mcd de dos nombres enters. Quant als conceptes hom incideix sobre les nocions de múltiples i divisors; en particular, les de màxim comú divisor i mínim comú múltiple. Pel que fa referència a l'educació d'actituds hom pretén fomentar una actitud activa, rigorosa i de descobriment quant a la valoració i verificació dels resultats, així com encoratjar l'alumnat a la comprensió i justificació de les propietats i teoremes matemàtics. Per bé que els algorismes figuren escrits segons els constructors del llenguatge WinLogo i, per tant, són directament implementables per a aquest interpret, la claredat del llenguatge permet emprar el codi font com a pseudocodi que facilitarà escriure'ls en d'altres llenguatges de programació. Abans de començar: tinguem en compte que el zero es divisible per qualsevol nombre enter (positiu o negatiu) i, per tant, és múltiple de qualsevol nombre enter; per altra banda, és clar que la noció de divisibilitat que tractem aquí per als nombres enters positius (i per al zero) és extensible a tots els nombres enters, per bé que, per facilitar la comprensió dels algorismes i dels senzills programes en Logo, en aquest article només es parla dels positius.

2. A la recerca dels nombres primers
Un primer procediment el dedicarem a realitzar la següent tasca: donat un nombre enter positiu qualsevol volem que el procediment doni com a resultat si aquest és - o no és - un nombre primer.

procediment Genera.nombres.primers :nombre_enter_fins_on_cal_buscar
  fes.local "nombre.inicial
  posa.a "nombre.inicial 2
  escriu.seguit 2 escriu [...‚s un nombre primer]
  repeteix :nombre.enter.fins.on.cal.buscar
     [
       Digues.quin.nombre.es.primer :nombre.inicial
       posa.a "nombre.inicial  (:nombre.inicial + 1)
     ]
fi

procediment Digues.quin.nombre.es.primer :n
  fes.local "divisor 
  fes.local "fita_del_bucle 
  posa.a "divisor 2
  posa.a "fita.del.bucle  part.entera (arrel :n)
  repeteix :fita.del.bucle 
    [
      si (residu :n :divisor) = 0 
        [acaba] 
        [posa.a "divisor (:divisor+1)]   
    ] 
  escriu.seguit :n escriu [és un nombre primer]
fi

3. Màxim comú divisor i mínim comú múltiple de dos nombres enters positius
El següent algorisme mostra una manera de calcula el màxim comú divisor de dos nombres enters:

procediment mcd.rudimentari :a :b
  si :a=:b 
      [escriu.seguit [mcd=] escriu :a  acaba] 
     [
       si :a<:b 
         [posa.a "b :a] 
         [posa.a "a (:a - :b) mcd.rudimentari :a :b]
     ]
fi

I, aquest altre, ens servirà per calcular el mínim comú múltiple:

procediment mcm_rudimentari :a :b
  fes.local "n
  fes.local "múltiple
  fes.local "nombre_més_petit
  fes.local "nombre_més_gran
  fes.local "màxim_iteracions
  posa.a  "n 0
  si :a>:b 
    [posa.a "nombre_més_gran :a posa.a "nombre_més_petit :b]
    [posa.a "nombre_més_gran :b posa.a "nombre_més_petit :a]             
  posa.a "màxim_iteracions :nombre_més_gran
  repeteix  :màxim_iteracions 
    [
      posa.a "n :n+1 
      posa.a "múltiple :n*:nombre_més_petit
      si :nombre_més_gran>:múltiple  
         [si residu :nombre_més_gran  :múltiple = 0 [escriu [mcm=] :múltiple acaba]
         [si residu :múltiple  :nombre_més_gran = 0 [escriu [mcm=] :múltiple acaba ]
    ]
fi

Un procediment alternatiu es fonamenta en el mètode d'Euclides:

procediment mcd.i.mcm.Euclides :a :b 
  fes.local "r 
  fes.local "dividend 
  fes.local "divisor 
  si :a > :b 
     [
       posa.a "dividend :a 
       posa.a "divisor :b
     ]  
     [
       posa.a "dividend :b  
       posa.a "divisor :a
     ]   
  repeteix :dividend
    [
      posa.a "r residu :dividend :divisor
      si :r=0 
        [
           escriu.seguit  [mcd =] escriu :divisor 
           escriu.seguit [mcm =]  escriu :a * :b / :divisor 
           acaba
        ]
        [
           posa.a "dividend :divisor 
           posa.a "divisor :r
        ]
     ]  
fi

$\square$