Divisibilidat

Iste articlo ye en proceso de cambio enta la ortografía oficial de Biquipedia (la Ortografía de l'aragonés de l'Academia Aragonesa d'a Luenga). Puez aduyar a completar este proceso revisando l'articlo, fendo-ie los cambios ortograficos necesarios y sacando dimpués ista plantilla.

12 ye dibisible por 3

10 NO ye dibisible por 3

Se diz que un numero entero b ye divisible entre atro entero a (distinto de cero) si existe un tercer entero c tal que:

b = a · c

Gosa expresar-se d'a forma a|b, que se leye a divide a b, u a ye divisor de b, u tamién b ye multiplo de a. Por eixemplo, 6 ye divisible por 3, ya que 6 = 3·2; pero no ye divisible por 4, pues no existe un entero c tal que 6 = 4·c. Ye decir, o repui d'a división euclidia (entera) de 6 entre 4 no ye cero. Se veiga l'algorismo d'a división.

Tot numero entero ye divisible por 1 y por sí mesmo. Os numeros mayors que 1 que no admiten mas que istos dos divisors se dicen numeros primers. Os que admiten mas de dos divisors se dicen numeros compuestos.

Propiedaz

Sían $a,b,c\in \mathbb {Z}$, ye decir $\ a$, $\ b$ y $\ c$ son numeros enters. Tenemos as siguients propiedaz basicas:

1. $a\mid a$ (Propiedat reflexiva).
2. Si $a\mid b$ y $b\mid c$, alavez $a\mid c$ (Propiedat transitiva).
3. Si $a\mid b$ , alavez $|a|\leq |b|$.
4. Si $a\mid b$ y $a\mid c$, alavez $a\mid \beta b+\gamma c\ \ \forall \ \beta ,\gamma \in \mathbb {Z}$.
5. Si $a\mid b$ y $a\mid b\pm \ c$, alavez $a\mid c$
6. Si $a\mid b$ y $b\mid a$, alavez $\ |a|=|b|$.
7. Si $a\mid b$ y $a\neq 0$, alavez ${\frac {b}{a}}\mid b$.
8. Ta $c\neq 0$, $a\mid b$ si y nomás si $ac\mid bc$
9. Si $a\mid bc$ y $\ mcd(a,b)=1$, alavez $a\mid c$.
10. Si $\ mcd(a,b)=1$ y $\ c$ cumple que $a\mid c$ y $b\mid c$, alavez $ab\mid c$.

Como $0=0\cdot n$ y $n=n\cdot 1$ se tien que $n\mid 0$ y $1\mid n$ ta tot $\ n$ entero. Si $\ m$ no ye divisible por $\ n$ escribimos $n\nmid m$. Notemos que $0\nmid m$ ta tot $\ m$ distinto de cero, pues $m\neq 0=k\cdot 0$ ta tot $\ k$ entero.

Tipos de criterios de divisibilidat

Os diferents criterios de divisibilidat se pueden clasificar en base a o tipo de manipulación que cada un fa con as cifras que representan o numero escrito en una base dada.

Criterios basatos en as zagueras cifras

Si un numero p ye divisor de 10ⁿ alavez ta saber si un numero cualsiquiera z ye divisible entre p nomas cal verificar que o numero z' formato por as n-1 zagueras cifras de z sían multiplo de p.

Como

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

y a la vegata o feito de que p sía divisor de 10ⁿ quiere decir que existe un numero natural c tal que

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

por tanto

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

Lo que evidencia que bi'n ha prou con que z' sía divisible entre 'p' ta que z tamién lo sía. O mesmo razonamiento se puet fer ta cualsiquier base substituyindo 10 por a correspondient base.

En o caso de base 10 isto nomas pasa con bels numeros d'a forma 2^n*5^m, por eixemplo o 2, 5, 10, 4, 8, 25, 125,...

Por eixemplo 1000 ye multiplo de 125 por tanto ta saber si un numero ye multiplo de 125 bi'n ha prou con comprevar que o numero formato por as suyas tres zagueras cifras ye multiplo de 125.

Por eixemplo 19.387.912.713.750 ye multiplo de 125 porque 750 en ye.

En isto es basan os criterios de divisibilidat de 2 y 5 d'a tabla.

Criterios basatos en a suma de cifras

Un numero z escrito en un sistema de numeración posicional de base b tien a forma siguient:

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

Si iste numero ye divisible entre unatro numero p quiere decir que o repui de dividir-lo entre p ye cero y por tanto que ye congruent con cero modulo p, asinas aplicando l'aritmetica modular se puet escribir:

$0=z{\bmod {p}}$

Pero parando cuenta en a representación posicional d'o numero y operando se puet escribir:

${\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}}$

Como bⁿ mod p ye mas chicot que p a partir d'un determinato valor de n os numeros que resultan d'ista expresión son muito mas chicoz que z. Isto permitiría construyir un criterio de divisibilidat:

Un numero z ye divisible entre p si:
o numero que s'obtiene como resultato de sumar cadaguna d'as suya cifras a_n multiplicata por o repui de dividir bⁿ entre p,
ye multiplo de p.

Ta aplicar iste criterio aparentment caldría trobar o repui de dividir bⁿ entre p ta tot n. A cinta de Pascal permite asegurar que isto nomás cal fer-lo ta una cantidat de valors que siempre ye mas chicota que p.

A cinta de Pascal se construye calculando b^{1 mod p, b2 mod p ... dica que se repitan b1 mod p. Alavez s'atura y se descarta o zaguer resultato ya que a partir d'aquí se repetirían toz.}

Demostración

Ta contrimostrar que: si un nombre se repite, se repiten toz. Se tracta de veyer 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}}$

Ta veyer que antis u dimpués se repiten, nomás cal veyer que bⁿ mod p ye siempre mas chicot que p. Por tanto como maximo i puet haber p valors diferents. Una vegata que bi haiga p valors diferents, o siguient que se calcule, ha de repetir-ne un u atro d'os anteriors.

 

Eixemplos

Trobar un criterio de divisibilidat entre 11 por os numeros escritos en base 10.

Primero se construye a 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}}$

A cinta de Pascal ye 10, 1 y a partit d'aquí se repite indefinidament.

Con isto se puet definir o criterio de divisibilidat siguient:

Ta saber si un numero z escrito en base 10 ye divisible entre 11:
sumar as cifras par, multiplicar-las por 10 y sumar-le a o resultato a suma de totas as cifras impars,
si o resultato ye multiplo d'11 o numero z tamién en ye.

Por eixemplo: z=3.536.026.857, suma de cifras pars: 5+6+0+3+3=17, suma de cifras impars: 7+8+2+6+5=28, pars x 10 + impars: 17x10+28=198

Si se quiere se puet repetir ta veyer si 198 ye multiplo d'11: 10x9+(1+8)=99 que ye multiplo de 11 (99=9x11) por tanto 3.536.026.857 ye multiplo d'11.

Una observación que se fa servir a sobén en istos metodos ye que 10 mod 11 = -1 mod 11, por tanto ye o mesmo multiplicar por 10 as cifras pars que restar-las. En o caso anterior:

pars - impars = 28-17=11 que ye multiplo d'11 y por tanto 3.536.026.857 tamién en ye.

Isto da o siguient criterio de divisibilidat equivalent a l'anterior pero mas simple:

Ta saber si un numero z escrito en base 10 ye divisible entre 11:
sumar as cifras pars, y d'atra man as cifras impars,
a la suma d'as cifras impars, restar-le a suma d'as cifras pars,
si o resultato ye multiplo d'11 o numero z tamién en ye.

Caso en que se suman grupos de cifras

Os criterios que resultan d'as cintas de Pascal aplicatos cifra por cifra tienen o inconvenient de que cada cifra cal multiplicar-la por un numero. O caso en que ye mas practico ye cuan o numero ye 1 (u -1 ≡ p-1).

Pero cualsiquier numero escrito en base b tamién se puet considerar escrito en base b^m si as suyas cifras se chuntan en grupos de m en m. Por eixemplo 1253 que en base diez quiere decir:

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

En base 100 quiere decir:

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

Ta evitar fer multiplicacions a cinta de Pascal ye puet fer servir porque una vegata trobata pillar as posicions a on bi ha 1 (u 1 i -1) y creyar un criterio de divisibilidat basato en un bloque de cifras.

Por eixemplo en calcular a cinta de Pascal de 7 ta numeros escritos en base diez obtenemos:

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

Por o que no cal continar, 6 mod 7 = -1 mod 7. y 1.000.000 mod 7 = (1.000)² mod 7 =(-1)²=1.

Por tanto se puet definir o siguient criterio de divisibilidat entre 7 d'un numero expresau en base 10 (que se treballa como si fuese base 1000):

Ta saber si un numero z escrito en base 10 ye divisible entre 7:
1) Deseparar as suyas cifras en grupos de 3 en 3
2) Sumar por deseparato os grupos impars y os grupos pars
3) D'o resultato d'a suma d'os grupos pars restar o resultato d'a suma d'os grupos impars.
Si o numero que resulta ye multiplo de 7 alavez z tamién en ye.

Por eixemplo, ta saber si 2.250.198.909.861 ye multiplo de 7, se suman os grupos de cifras pars: 909+250=1159 y os grupos impars: 861+198+2=1061 y d'os pars se restan os impars: 1159-1061=98. Como 98 ye multiplo de 7 (98=7x14) alavez 2.250.198.909.861 tamién en ye.

Criterios basatos en sumar a las primeras cifras un multiplo d'a zaguera

Istos criterios buscan transformar o problema de saber si un numero z ye multiplo de p en o problema de saber-lo ta un numero z' que tien una cifra menos que z. Asinas, aplicando repetidament o criterio, si z ye multiplo de p en zagueras se plega a un numero facil d'identificar si ye u no multiplo dep

O numero z se puet expresar como:

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

A on a₀ ye a cifra d'as unidaz de z i z_p ye o numero que forman a resta de cifras (o numero de decenas que tien z). Si z ye multiplo de p alavez ha d'estar:

${\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}}$

A on $\left(10{\bmod {p}}\right)^{-1}$ ye un numero que multiplicato por $\left(10{\bmod {p}}\right)$ da 1 mod p.

Por tanto se puet definir o siguient criterio de divisibilidat:

Un numero z en base 10 ye divisible entre p si tamién lo ye o resultau de:
sumar a o numero de decenas a cifra d'as unidaz multiplicada por o inverso de 10 mod p.

Ye evident que se puet fer un razonamient analogo en cualsiquier atra base.

Por eixemplo, trobar un criterio ta saber si un numero ye divisible entre 7.

Cal trobar un numero x que multiplicato por 10 mod 7 dé 1. Como 10 mod 7 =3 i 3x5=15 y como 15 mod 7 =1 o numero en cuestión ye o 5.

Por tanto un criterio de divisibilidat entre 7 por un numero expresato en base diez sería:

Un numero z en base 10 ye divisible entre 7 si tamién en ye o resultato de:
sumar a o numero de decenas a cifra d'as unidaz multiplicata por 5.

Por eixemplo ta veyer si 17.948 ye multiplo de 7 s'aplica repetidament o criterio y s'obtiene:

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

Como 35 ye multiplo de 7 (35=7x5) alavez 17.948 tamién en ye.

O zaguer refinamiento d'iste metodo ye parar cuenta que 5 mod 7 = -2 mod 7 y por tanto en cuentas de multiplicar por 5 se puet restar o resultato de muliplicar por 2. (Isto tamién se cheneraliza ta cualsiquier base y ta cualsiquier numero p).

D'ista traza se puet definir o criterio:

Un numero z en base 10 ye divisible entre 7 si tamién en ye o resultato de:
restar a o numero de decenas a cifra d'as unidaz multiplicata por 2.

En l'eixemplo anterior da:

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

Tabla de criterios de divisibilidat

De contino s'amostra una tabla d'os criterios de divisibilidat entre os numeros primers mas chicoz que 20. Tamién bi ha criterios de divisibilitat entre os numeros compuestos y se pueden trobar fendo servir as tecnicas que s'han explicato antis. Pero ta saber si un numero ye divisible entre un numero compuesto a vegatas ye mas facil verificar si ye divisible entre toz os suyos factors primers, atras vegatas, si l'obchectivo d'aplicar o criterio de divisibilidat ye descomponer o numero en factors primers no tien sentito prebar os factors compuestos.

Ista tabla s'aplica si os numeros son escrits en base 10.

Divisibilidat entre :	Enunciato d'o criterio:	Eixemplo :
2	Un numero ye divisible entre 2 si a cifra d'as suyas unidaz ye multiplo de 2	158.538.456 ye multiplo de 2 porque 6 ye multiplo de 2. 5.896.740.320 ye multiplo de 2 porque 0 és multiplo de 2.
3	Un numero ye divisible entre 3 si a suma d'as suya cifras ye divisible entre 3.	35.796.825 ye divisible entre 3 porque: 3 + 5 + 7 + 9 + 6 + 8 + 2 + 5 = 45 i 45 ye divisible entre 3 tamién se puet repetir o criterio ta veyer si 45 ye divisible entre 3: 4 + 5 = 9 que ye divisible entre 3.
5	Un numero ye divisible entre 5 si a zaguera cifra ye multiplo de 5.	35.796.825 ye multiplo de 5 porque remata en 5 que ye multiplo de 5. 321.654.864.510 ye multiplo de 5 porque remata en 0 que ye multiplo de 5.
7	Un numero ye divisible entre 7 si en restar d'o numero de decenas o doble d'as unidaz da un numero que ye multiplo de 7	189 ye divisible entre 7 porque 18 - 2 * 9 = 0 que ye multiplo de 7. 864.192 ye divisible entre 7 porque: 86.419 - 2*2 = 86.415 que ye multiplo de 7 porque: 8.641 - 2*5 = 8.631 que ye multiplo de 7 porque: 863 - 2*1 = 861 que ye multiplo de 7 porque: 86 - 2*1 = 84 que ye multiplo de 7 porque: 8 - 2*4 = 0 que ye multiplo de 7.
	Un numero ye divisible entre 7 si en deseparar as suyas cifras en grupos de 3, sumar-las y restar-las alternativament da un numero que ye multiplo de 7	8.641.975.237.077 ye divisible entre 7 porque: 8 - 641 + 975 - 237 + 077 = 182 que ye multiplo de 7 porque (criterio anterior en tener menos de 3 cifras): 18 -2*2 = 14 que ye multiplo de 7.
11	Un numero ye divisible entr 11 si en sumar y restar alternativament as suyas cifras u resultato ye multiplo d'11	135.802.458 ye multiplo de 11 porque: 1 - 3 + 5 - 8 + 0 - 2 + 4 - 5 + 8 = 0 que ye multiplo d'11 10.864.197.531 ye multiplo de 11 porque: 1 - 0 + 8 - 6 + 4 - 1 + 9 - 7 + 5 - 3 + 1 = 11 que ye multiplo d'11
13	Un numero ye divisible entre 13 si en sumar a o numero de decenas o cuadruple d'as unidaz da un numero que ye multiplo de 13	273 ye divisible entre 13 porque 27 + 4 * 3 = 39 que ye multiplo de 13 (3*13). 172.302 ye divisible entre 13 porque: 17.230 + 4*2 = 17.238 que ye multiplo de 13 porque: 1.723 + 4*8 = 1.755 que ye multiplo de 13 porque: 175 + 4*5 = 195 que ye multiplo de 13 porque: 19 + 4*5 = 39 que ye multiplo de 13 porque ye 3*13
	Un numero ye divisible entre 13 si en deseparar as suyas cifras en grupos de 3, sumar-las y restar-las alternativament da un numero que ye multiplo de 13	1.633.123.612.311.854 ye divisible entre 13 porque: 1 - 633 + 123 - 612 + 311 - 854 = -1.664 que ye multiplo de 13 porque (criterio anterior en tener pocas cifras): 166+4*4=182 18+4*2=26 que ye multiplo de 13. (2*13)
17	Un numero ye divisible entre 17 si en restar a o numero de decenas o quintuplo d'as unitats da un numero que ye multiplo de 17	3723 ye multiplo de 17 porque: 372 - 5*3 = 357 que ye multiplo de 17 porque 35 - 5*7 = 0 que ye multiplo de 17
	Un numero ye divisible entre 17 si en separar as suyas cifras en grupos de 8, sumar-las y restar-las alternativament da un numero que ye multiplo de 17	416.52136869.99864791.53682401 ye multiplo de 17 porque: 416-52136869+99864791-53682401 = -5954063 que ye multiplo de 17 porque 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 ye multiplo de 17
19	Un numero ye divisible entre 19 si en sumar a o numero de decenas o doble d'as unidaz da un numero que ye multiplo de 19	247 ye divisible entre 19 porque 24 + 2 * 7 = 38 que ye multiplo de 19 (2*19).
	Un numero ye divisible entre 19 si en deseparar as suyas cifras en grups de 9, en sumar-las y restar-las alternativament da un numero que ye multiplo de 19	48822138.835949515.214962479 ye divisible entre 19 porque: 48822138-835949515+214962479 = -572164898 que ye multiplo de 19 porque (criterio anterior en tener pocas cifras): 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 ye multiplo de 19 (4*19)

En a siguient tabla, ta bels numeros primers mas grans de 20, se dan o factor que multiplica as unidaz ta o caso d'o metodo basato en sumar a las decenas un multiplo d'as unidaz y ta o caso de deseparar o numero en bloques de cifras a largaria d'o bloque y o coeficient d'os bloques pars (o d'os bloques impars se considera siempre 1).

Nombre	Factor d'as unidaz	cifras d'o bloque	Factor d'o bloque impar
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

Vinclos externos

• (en) Interactive Divisibility Lesson on these rules
• (en) Divisibility Criteria en cut-the-knot
• (en) Divisibility by 9 and 11 en cut-the-knot
• (en) Divisibility by 7 en cut-the-knot
• (en) Divisibility by 81 en cut-the-knot
• (en) Divisibility by Three Explained