Criteri de divisibilitat

Un criteri de divisibilitat és un algorisme que aprofita la informació que dona 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 quan el càlcul es fa a mà per a estalviar el treball de calcular les divisions entre els possibles factors si el nombre no és divisible entre ells.

Tipus de criteris de divisibilitat

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

Criteris basats en les últimes xifres

Si un nombre p és divisor de 10ⁿ 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 sigui divisor de 10ⁿ vol dir que existeix 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 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 amb els 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

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 congruent 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{aligned}&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{aligned}}$

Com que bⁿ 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 bⁿ 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 b¹ mod p, b² mod p ... fins que es repeteix b¹ mod p. Llavors es para i es descarta l'últim resultat perquè a partir d'aquí es repetirien tots.

Demostració

Per a demostrar que: si un nombre es repeteix, es repeteixen tots. Es tracta de veure que:

$b^{n}{\bmod {p}}=b^{m}{\bmod {p}}\Rightarrow b^{n+1}{\bmod {p}}=b^{m+1}{\bmod {p}}$

Només cal calcular:

${\begin{aligned}b^{m+1}{\bmod {p}}\\&=\left(b\times b^{m}\right){\bmod {p}}\\&=\left[b\times \left(b^{m}{\bmod {p}}\right)\right]{\bmod {p}}\\&=\left[b\times \left(b^{n}{\bmod {p}}\right)\right]{\bmod {p}}\\&=b^{n+1}{\bmod {p}}\end{aligned}}$

Per a veure que tard o d'hora es repeteixen, només cal veure que bⁿ mod p és sempre més petit que p. Per tant com a màxim hi pot haver p valors diferents. Un cop hi hagi p valors diferents, el següent que es calculi, per força, ha de repetir-ne un o altre dels anteriors.

Exemples

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

Primer es troba la cinta de pascal:

${\begin{aligned}&10^{1}{\bmod {1}}1=10\\&10^{2}{\bmod {1}}1=1\\&10^{3}{\bmod {1}}1=10\\\end{aligned}}$

La cinta de Pascal és 10,1 i a partir 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 d'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ò dona 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 d'11 el nombre z també ho és.

Cas en què se sumen grups de xifres

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 b^m 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{aligned}&10^{1}{\bmod {7}}=3\\&10^{2}{\bmod {7}}=2\\&10^{3}{\bmod {7}}=6\\\end{aligned}}$

Fixeuvos que no cal continuar, 6 mod 7 = -1 mod 7. i 1.000.000 mod 7 = (1.000)² mod 7 =(-1)²=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

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 d'identificar si és o no múltiple dep El nombre z es pot expressar com:

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

On a₀ és la xifra de les unitats de z i z_p é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{aligned}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{aligned}}$

On $\left(10{\bmod {p}}\right)^{-1}$ és un nombre que multiplicat per $\left(10{\bmod {p}}\right)$ dona 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 expressat 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 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 dona:

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

Taula de criteris de divisibilitat

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 dona 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 dona 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 d'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 dona 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 dona 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 dona 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 dona 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 dona 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 dona 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

• Interactive Divisibility Lesson on these rules (anglès)
• Criteris de divisibilitat a cut-the-knot (anglès)