Criteri de divisibilitat
![]() | Aquest article o secció no cita les fonts o necessita més referències per a la seva verificabilitat. |
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 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
i al mateix temps el fet que p sigui divisor de 10n vol dir que existeix un nombre natural c tal que
per tant
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:
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:
Però tenint en compte la representació posicional del nombre i operant es pot escriure:
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 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.
Només cal calcular:
Exemples
Trobar un criteri de divisibilitat entre 11 pels nombres escrits en base 10.
Primer es troba la cinta de pascal:
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 bm si les seves xifres s'agafen en grups de m en m. Per exemple 1253 que en base deu vol dir:
En base 100 vol dir:
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:
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:
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:
On és un nombre que multiplicat per 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 |
|
3 | Un nombre és dvisible entre 3 si la suma de les seves xifres és divisible entre 3. |
|
5 | Un nombre és divisible entre 5 si l'última xifra é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 |
|
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 |
| |
11 | Un nombre és divisible entre 11 si en sumar i restar alternativament les seves xifres el resultat és múltiple d'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 |
|
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 |
| |
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 |
|
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 |
| |
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 |
|
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 |
|
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
![](http://upload.wikimedia.org/wikipedia/commons/thumb/4/4a/Commons-logo.svg/30px-Commons-logo.svg.png)
- Interactive Divisibility Lesson on these rules (anglès)
- Criteris de divisibilitat a cut-the-knot (anglès)