Criteri de divisibilitat

De Viquipèdia
Dreceres ràpides: navegació, cerca

Un criteri de divisibilitat és un algorisme que aprofita la informació que dóna el fet de tenir un nombre escrit en un sistema de numeració posicional en una determinada base per decidir si és o no divisible entre un altre sense necessitat de calcular la divisió per a comprovar si el residu és zero o no.

Els criteris de divisibilitat es fan servir en la descomposició en factors primers d'un nombre quant el càlcul es fa a mà per estalviar el treball de calcular les divisions entre els possibles factors si el nombre no és divisible entre ells.


Tipus de criteris de divisibilitat[modifica | modifica el codi]

Els diferents criteris de divisibilitat es poden classificar en base al tipus de manipulació que cada un fa amb les xifres que representen el nombre escrit en una base donada.

Criteris basats en les últimes xifres[modifica | modifica el codi]

Si un nombre p és divisor de 10n llavors per saber si un nombre qualsevol z és divisible entre p només cal verificar que el nombre z' format per les n-1 últimes xifres de z siguin múltiple de p.

Com que

z=z_{a}\times 10^{n}+{z}'

i al mateix temps el fet que p disgui divisor de 10n vol dir que existeis un nombre natural c tal que

\frac{10^{n}}{p}=c

per tant

\frac{z}{p}=z_{a}\times \frac{10^{n}}{p}+\frac{{{z}'}}{p}=z_{a}\times c+\frac{{{z}'}}{p}

El que evidencia que n'hi ha prou amb que z' sigui divisible entre 'p' perquè z també ho sigui. El mateix raonament es pot fer per a qualsevol base substituint 10 per la corresponent base.

En el cas de base 10 això només passa ambels nombres de la forma 2^n*5^m, per exemple el 2, 5, 10, 4, 8, 25, 125,...

Per exemple 1000 és múltiple de 125 per tant per saber si un nombre és múltiple de 125 n'hi ha prou amb comprovar que el nombre format per les seves tres últimes xifres és múltiple de 125.

Per exemple 19387912713750 és múltiple de 125 perquè 750 ho és.

En això es basen els criteris de divisibilitat de 2 i 5 de la taula.

Criteris basats en la suma de xifres[modifica | modifica el codi]

Un nombre z escrit en un sistema de numeració posicional de base b té la forma següent:

z=a_{0}+a_{1}\times b+a_{2}\times b^{2}+\ldots +a_{n}\times b^{n}

Si aquest nombre és divisible entre un altre nombre p vol dir que el residu de dividir-lo entre p és zero i per tant que és conruent amb zero mòdul p, així aplicant l'aritmètica modular es pot escriure:

0=z\bmod p

Però tenint en compte la representació posicional del nombre i operant es pot escriure:

\begin{align}
 & 0=(a_{0}+a_{1}\times b+a_{2}\times b^{2}+\ldots +a_{n}\times b^{n})\bmod p \\ 
 & 0=(a_{0}+a_{1}\times \left( b\bmod p \right)+a_{2}\times \left( b^{2}\bmod p \right)+\ldots +a_{n}\times \left( b^{n}\bmod p \right))\bmod p \\ 
\end{align}

Com que bn mod p és més petit que p a partir d'un determinat valor de n els nombres que resulta d'aquesta expressió és molt més petit que z. Això permetria construir un criteri de divisibilitat:

Un nombre z és divisible entre p si: 
el nombre que s'obté com a resultat de sumar cada una de les seves xifres an multiplicada pel residu de dividir bn entre p,
és múltiple de p.

Per aplicar aquest criteri aparentment caldria trobar el residu de dividir bn entre p per a tot n. La cinta de Pascal permet assegurar que això només cal fer-ho per una quantitat de valors que sempre és més petita que p.

La cinta de Pascal es construeix calculant b1 mod p, b2 mod p ... fins que es repeteix b1 mod p. Llavors es para i es descarta l'últim resultat perquè a partir d'aquí es repetirien tots.



Exemples[modifica | modifica el codi]

Trobar un criteri de divisibilitat entre 11 pels nombres escrits en base 10.

Primer es trona la cinta de pascal:

\begin{align}
 & 10^{1}\bmod 11=10 \\ 
 & 10^{2}\bmod 11=1 \\ 
 & 10^{3}\bmod 11=10 \\ 
\end{align}

La cinta de Pascal és 10,1 i a partit d'aquí es repeteix indefinidament.

Amb això es pot definir el criteri de divisibilitat següent:

per saber si un nombre z escrit en base 10 és divisible entre 11:
sumar les xifres parells, multiplicar-les per 10 i sumar-li al resultat la suma de totes les xifres senars,
si el resultat és múltiple de 11 el nombre z també ho és.

Per exemple: z=3.536.026.857, suma de xifres parells: 5+6+0+3+3=17, suma de xifres senars: 7+8+2+6+5=28, parells x 10 + senars: 17x10+28=198

Si es vol es pot repetir per veure si 198 és múltiple de 11: 10x9+(1+8)=99 que és múltiple de 11 (99=9x11) per tant 3.536.026.857 és múltiple de 11.

Una observació que es fa servir sovint en aquests mètodes és que 10 mod 11 = -1 mod 11, per tant és el mateix multiplicar per 10 les xifres parells que restar-les. En el cas anterior: senars - parells = 28-17=11 que és múltiple de 11 i per tant 3.536.026.857 també ho és.

Això dóna el següent criteri de divisibilitat equivalent a l'anterior però més senzill:

per saber si un nombre z escrit en base 10 és divisible entre 11:
sumar les xifres parells, i les xifres senars per separat,
a la suma de les xifres senars, restar-li la suma de les xifres parells,
si el resultat és múltiple de 11 el nombre z també ho és.

Cas en què se sumen grups de xifres[modifica | modifica el codi]

Els criteris que resulten de les cintes de pascal aplicats xifra per xifre tenen l'inconvenient de què cada xifra cal multiplicar-la per un nombre. El cas en què és més pràctic és quan el nombre és 1 (o -1 ≡ p-1).

Però qualsevol nombre escrit en base b també es pot considerar escrit en base bm si les seves xifres s'agafen en grups de m en m. Per exemple 1253 que en base deu vol dir:

1\times 10^{3}+2\times 10^{2}+5\times 10^{1}+3\times 10^{0}

En base 100 vol dir:

12\times 100^{1}+53\times 100^{0}

Per evitar fer multiplicacions la cinta de Pascal es pot fer servir perquè un cop trobada agafar les posicions on hi a 1 (o 1 i -1) i crear un criteri de divisibilitat basat en un bloc se xifres.

Per exemple en calcular la cinta de Pascal de 7 per nombres escrits en base deu surt:

\begin{align}
 & 10^{1}\bmod 7=3 \\ 
 & 10^{2}\bmod 7=2 \\ 
 & 10^{3}\bmod 7=6 \\ 
\end{align}

Fixeuvos que no cal continuar, 6 mod 7 = -1 mod 7. i 1.000.000 mod 7 = (1.000)2 mod 7 =(-1)2=1.

Per tant es pot definir el següent criteri de divisibilitat entre 7 d'un nombre expressat en base 10 (que es treballa com si fos base 1000):

Per saber si un nombre z escrit en base 10 és divisible entre 7:
1)separar les seves xifres en grups de 3 en 3
2)sumar per separat els grups senrars i els grups parells
3)del resultat de la suma dels grups parells restar-los el resultat de la suma dels grups senars.
si el nombre que resulta és múltiple de 7 llavors z també ho és.

Per exemple, per saber si 2.250.198.909.861 és múltiple de 7, se sumen els grups de xifres parells: 909+250=1159 i els grups senars:861+198+2=1061 i dels parells es resta els senars: 1159-1061=98. Com que 98 és múltiple de 7 (98=7x14) llavors 2.250.198.909.861 també ho és.

Criteris basats en sumar a les primeres xifres un múltiple de l'última[modifica | modifica el codi]

Aquests criteris busquen transformar el problema de saber si un nombre z és múltiple de p en el problema de saber-ho per un nombre z' que té una xifra menys que z. Així, aplicant repetidament el criteri, si z és múltiple de p al final s'arriba a un nombre fàcil de identificar si és o no múltiple dep El nombre z es pot expressar com:

z=a_{0}+z_{d}\times 10

On a0 és la xifra de les unitats de z i zp és el nombre que formen la resta de xifres (el nombre de desenes que té z). Si z és múltiple de p llavors ha de ser:

\begin{align}
 0& =z\bmod p \\ 
 & =\left( a_{0}+z_{d}\times 10 \right)\bmod p \\ 
 & =\left( a_{0}+z_{d}\times \left( 10\bmod p \right) \right)\bmod p \\ 
 & =\left( 10\bmod p \right)^{-1}\times \left( a_{0}+z_{d}\times \left( 10\bmod p \right) \right)\bmod p \\ 
 & =\left( \left( 10\bmod p \right)^{-1}\times a_{0}+z_{d}\times \left( 10\bmod p \right)\times \left( 10\bmod p \right)^{-1} \right)\bmod p \\ 
 & =\left( \left( 10\bmod p \right)^{-1}\times a_{0}+z_{d} \right)\bmod p 
\end{align}

On \left( 10\bmod p \right)^{-1} és un nombre que multiplicat per \left( 10\bmod p \right) dóna 1 mod p.

Per tant es pot definir el següent criteri de divisibilitat:

Un nombre z en base 10 és divisible entre p si també ho és el resultat de: 
sumar al nombre de desenes la xifra de les unitats multiplicada per l'invers de 10 mod p.

És evident que es pot fer un raonament anàleg en qualsevol altra base.

Per exemple, trobar un criteri per saber si un nombre és divisible entre 7.

Cal trobar un nombre x que multiplicat per 10 mod 7 doni 1. Com que 10 mod 7 =3 i 3x5=15 i com que 15 mod 7 =1 el nombre en qüestió és el 5.

Per tant un criteri de divisibilitat entre 7 per un nombre expresat en base deu seria:

Un nombre z en base 10 és divisible entre 7 si també ho és el resultat de: 
sumar al nombre de desenes la xifra de les unitats multiplicada per 5.

Per exemple per veure si 17.948 és múltiple de 7 s'aplica repetidament el criteri i s'obté:

1.794+5x8=1.834
183+5x4= 203
20+5x3= 35

Com que 35 és múltiple de 7 (35=7x5) llavors 17.948 també ho és.

L'últim refinament d'aquest mètode és adonar-se'n que 5 mod 7 = -2 mod 7 i per tant en comptes de multiplicar per 5 es pot restar el resultat de muliplicar per 2. (Això també es es generalitza per a qualsevol base i per a qualsevol nombre p).

D'aquesta manera es pot definir el criteri:

Un nombre z en base 10 és divisible entre 7 si també ho és el resultat de: 
restar al nombre de desenes la xifra de les unitats multiplicada per 2.

En l'exemple anterior dóna:

1.794-2x8=1.778
177-2x8= 161
16-2x1= 14

Taula de criteris de divisibilitat[modifica | modifica el codi]

Tot seguit es presenta una taula dels criteris de divisibilitat entre els nombres primers més petits de 20. També hi ha criteris de divisibilitat entre els nombres compostos i es poden trobar fent servir les tècniques que s'han explicat abans. Però per saber si un nombre es divisible entre un nombre compost de vegades és més fàcil verificar si és divisible entre tots els seus factors primers, altres vegades, si l'objectiu d'aplicar el criteri de divisibilitat és descompondre el nombre en factors primers no té sentit provar els factors compostos.

Aquesta taula s'aplica si els nombres estan escrits en base 10.

Divisibilitat entre : Enunciat del criteri: Exemple :
2 Un nombre és divisible entre 2 si la xifra de les seves unitats és múltiple de 2
  • 158.538.456 és múltiple de 2 perquè 6 és múltiple de 2.
  • 5.896.740.320 és múltiple de 2 perquè 0 és múltiple de 2.
3 Un nombre és dvisible entre 3 si la suma de les seves xifres és divisible entre 3.
  • 35.796.825 és divisible entre 3 perquè:
3 + 5 + 7 + 9 + 6 + 8 + 2 + 5 = 45 i 45 és divisible entre 3
també es pot repetir el critei per veure si 45 és divisible entre 3:
4 + 5 = 9 que és divisible entre 3.
5 Un nombre és divisible entre 5 si l'última xifra és múltiple de 5.
  • 35.796.825 és múltiple de 5 perquè acaba en 5 que és múltiple de 5.
  • 321.654.864.510 és múltiple de 5 perquè acaba en 0 que és múltiple de 5.
7 Un nombre és divisible entre 7 si al restar del nombre de desenes el doble de les unitats dóna un nombre que és múltiple de 7
  • 189 és divisible entre 7 perquè 18 - 2 * 9 = 0 que és múltiple de 7.
  • 864.192 és divisible entre 7 perquè:
86.419 - 2*2 = 86.415 que és múltiple de 7 perquè:
8.641 - 2*5 = 8.631 que és múltiple de 7 perquè:
863 - 2*1 = 861 que és múltiple de 7 perquè:
86 - 2*1 = 84 que és múltiple de 7 perquè:
8 - 2*4 = 0 que és múltiple de 7.
Un nombre és divisible entre 7 si al separar les seves xifres en grups de 3, al sumarles i restarles alternativament dóna un nombre que és múltiple de 7
  • 8.641.975.237.077 és divisible entre 7 perquè:
8 - 641 + 975 - 237 + 077 = 182 que és múltiple de 7 perquè (criteri anterior al tenir menys de 3 xifres):
18 -2*2 = 14 que és múltiple de 7.
11 Un nombre és divisible entre 11 si en sumar i restar alternativament les seves xifres el resultat és múltiple de 11
  • 135.802.458 és múltiple de 11 perquè:
1 - 3 + 5 - 8 + 0 - 2 + 4 - 5 + 8 = 0 que és múltiple de 11
  • 10.864.197.531 és múltiple de 11 perquè:
1 - 0 + 8 - 6 + 4 - 1 + 9 - 7 + 5 - 3 + 1 = 11 que és múltiple de 11
13 Un nombre és divisible entre 13 si al sumar al nombre de desenes el quàdruple de les unitats dóna un nombre que és múltiple de 13
  • 273 és divisible entre 13 perquè 27 + 4 * 3 = 39 que és múltiple de 13 (3*13).
  • 172.302 és divisible entre 13 perquè:
17.230 + 4*2 = 17.238 que és múltiple de 13 perquè:
1.723 + 4*8 = 1.755 que és múltiple de 13 perquè:
175 + 4*5 = 195 que és múltiple de 13 perquè:
19 + 4*5 = 39 que és múltiple de 13 perquè és 3*13
Un nombre és divisible entre 13 si al separar les seves xifres en grups de 3, al sumar-les i restar-les alternativament dóna un nombre que és múltiple de 13
  • 1.633.123.612.311.854 és divisible entre 13 perquè:
1 - 633 + 123 - 612 + 311 - 854 = -1.664 que és múltiple de 13 perquè (criteri anterior al tenir poques xifres):
166+4*4=182
18+4*2=26 que és múltiple de 13. (2*13)
17 Un nombre és divisible entre 17 si al restar al nombre de desenes el quíntuple de les unitats dóna un nombre que és múltiple de 17
  • 3723 és múltiple de 17 perquè:
372 - 5*3 = 357 que és múltiple de 17 perquè
35 - 5*7 = 0 que és múltiple de 17
Un nombre és divisible entre 17 al separar les seves xifres en grups de 8, al sumarles i restarles alternativament dóna un nombre que és múltiple de 17
  • 416.52136869.99864791.53682401 és múltiple de 17 perquè:
416-52136869+99864791-53682401 = -5954063 que és múltiple de 17 perquè
595.406 - 5*3 = 595.391
59539 - 5*1 = 59.534
5.953 - 5*4 = 5.933
593 - 5*3 = 578
57 - 5*8 = 17 que és múltiple de 17
19 Un nombre és divisible entre 19 si al sumar al nombre de desenes el doble de les unitats dóna un nombre que és múltiple de 19
  • 247 és divisible entre 19 perquè 24 + 2 * 7 = 38 que és múltiple de 19 (2*19).
Un nombre és divisible entre 19 si al separar les seves xifres en grups de 9, al sumar-les i restar-les alternativament dóna un nombre que és múltiple de 19
  • 48822138.835949515.214962479 és divisible entre 19 perquè:
48822138-835949515+214962479 = -572164898 que és múltiple de 19 perquè (criteri anterior al tenir poques xifres):
57.216.489 + 2*8 = 57.216.505
5.721.650 + 2*5 = 5.721.660
572.166 + 2*0 = 572.166
57.216 + 2*6 = 57.228
5.722 + 2*8 = 5.738
573 + 2*8 = 589
58 + 2*9 = 76 que és múltiple de 19 (4*19)

En la següent taula, per una quants nombres primers més grans de 20, es donen el factor que multiplica les unitats pel cas del mètode basat en sumar a les desenes un múltiple de les unitats i pel cas de separar el nombre en blocs de xifres la longitud del bloc i el coeficient dels blocs parells (el dels blocs senars es considera sempre 1.

Nombre Factor de les unitats Xifres del bloc Factor del bloc senar
23 7 11 -1
29 3 14 -1
31 -3 15 +1
37 −11 3 +1
41 –4 5 +1
73 4 -1
101 2 -1
137 4 -1

Enllaços externs[modifica | modifica el codi]