Criterio de divisibilidad

En matemáticas y más precisamente en aritmética modular , un criterio de divisibilidad es una característica de un número entero que permite determinar si este número es divisible por otro. A pesar de su apariencia de "receta de cocina" (ver la lista de criterios de divisibilidad ), los criterios de divisibilidad se basan en pruebas matemáticas; es posible encontrarlos para cualquier número gracias a las congruencias .

Buscar un criterio de divisibilidad

Para encontrar un criterio de divisibilidad por m en base 10 , basta con encontrar si existe un entero relativo k tal que 10 k - 1 es un múltiplo de m (por lo tanto, escaneamos los números de la forma + ... 9 o - ... 1).

Entonces es suficiente sumar k veces los dígitos de las unidades al número de decenas. Por ejemplo, para m = 7, el número entero k = –2 es adecuado porque 10 k - 1 = –21 = –3 m . Para probar la divisibilidad de 7,485, calculamos 748 + (–2) × 5 = 738 y reiteramos a partir de 738. Gradualmente, 7,485 será un múltiplo de 7 si y solo si el número final es un múltiplo de 7 (ver demostración a continuación ).

Ejemplos:

3 × 3 = 9 = 1 × 10 - 1: sumaremos las unidades a las decenas para la divisibilidad entre 3 o 9.
–3 × 7 = –2 × 10 - 1: restaremos el doble de las unidades de las decenas para la divisibilidad por 7 o 3.
–11 = –1 × 10 - 1: restaremos las unidades a las decenas para la divisibilidad por 11.
13 × 3 = 4 × 10 - 1: sumaremos 4 veces las unidades a las decenas para la divisibilidad entre 13 o 3.
–17 × 3 = –5 × 10 - 1: restaremos 5 veces las unidades de las decenas para la divisibilidad por 17 o 3.
29 = 3 × 10 - 1: sumaremos 3 veces las unidades a las decenas para la divisibilidad por 29.
–31 = –3 × 10 - 1: restaremos 3 veces las unidades de las decenas para la divisibilidad por 31.
–41 = –4 × 10 - 1: restaremos 4 veces las unidades de las decenas para la divisibilidad por 41.

Observación:

Si 10 k - 1 es un múltiplo de m, entonces 10 ( k ± m ) - 1 también. Por ejemplo, para m = 7, hemos elegido arriba k = –2 (la solución más cercana a 0) pero también podríamos elegir, por ejemplo, k = –2 + 7 = 5 (la solución más pequeña positiva).

Ejemplo y demostración de criterios de divisibilidad

Antes de abordar el método general, aquí se presentan algunos criterios de divisibilidad que ilustran las técnicas utilizadas. Puede encontrar una lista más extensa de criterios en el artículo Lista de criterios de divisibilidad .

Nos acercamos a las demostraciones en ℕ porque un entero relativo tiene los mismos divisores que su valor absoluto .

A continuación se muestran las notaciones utilizadas en el resto del artículo.

Sea A un número natural . Establecemos A = a n a n - 1 … a 1 a 0 , es decir, un 0 es el dígito de las unidades, un 1 es el dígito de las decenas, y así sucesivamente. de donde

A = a 0 + a 1 × 10 + a 2 × 10 2 +… + a n × 10 n .

Además, denotaremos por el número de decenas de A (que no debe confundirse con el dígito de las decenas):

d = a n a n - 1 … a 1 = a 1 + a 2 × 10 +… + a n × 10 n - 1 , así: A = ( d × 10) + a 0 .

Por 2

Un número es par , es decir, divisible por 2, si y solo si su dígito de unidades es 0, 2, 4, 6 u 8.

De hecho, A = ( d × 10) + a 0 y d × 10 es siempre un múltiplo de 2, por lo que A es un múltiplo de 2 si y solo si un 0 es un múltiplo de 2.

Por 3

Un número es divisible por 3 si y solo si la suma de sus dígitos es divisible por 3 (la suma de los dígitos se puede aplicar nuevamente a la suma obtenida y así sucesivamente hasta obtener 3, 6 o 9).

Demostración -

A es divisible por 3 si y solo si es congruente con 0 módulo 3. O

A = a 0 + a 1 × 10 + a 2 × 10 2 +… + a n × 10 n .

Pero 10 es congruente con 1 módulo 3, por lo que sus poderes también, por lo tanto

A ≡ a 0 + a 1 + a 2 +… + a n mod 3.

También demostramos que un número es divisible por 9 si y solo si la suma de sus dígitos es divisible por 9 (ya que 10 es congruente con 1 no solo módulo 3, sino incluso módulo 9).

Por 7

Declaración 1

Un número es divisible por 7 si y solo si la diferencia entre su número de decenas y el doble de su dígito de unidades (es decir: d - 2 a 0 ) es.

Ejemplo :

413

número de decenas: 41; dígitos de las unidades: 3

41 - 2 × 3 = 35 es divisible por 7, por lo que 413 también lo es.

Demostración -

A = 10 días + a 0

Sea B = d - 2 a 0 y demuestre (usando que 21 es un múltiplo de 7) que A es divisible por 7 si y solo si B lo es.

d = B + 2 a 0 entonces A = 10 B + 21 a 0 entonces si B es divisible por 7 entonces A también lo es.

a 0 = A - 10 d por lo tanto B = –2 A + 21 d entonces si A es divisible por 7 entonces B también lo es.

Declaración 2

Usando la clave de divisibilidad : 1, 3, 2, −1, −3, −2. Esto se obtiene, por ejemplo, del resto de la división de 1, 10, 100, etc. por 7, de lo cual restamos 7 cuando exceden 3. Este método también es válido para todos los demás divisores.

Cada dígito del número a analizar se multiplica por el dígito correspondiente de la clave, comenzando por las unidades.

Ejemplos:

Para verificar, por ejemplo, que 826,413 es divisible entre 7, miramos para ver si el número 3 × 1 + 1 × 3 + 4 × 2 + 6 × (−1) + 2 × (−3) + 8 × (- 2) es divisible por 7. El valor absoluto de este número es 14, que de hecho es divisible por 7 (podemos usar la tabla de multiplicar o nuevamente la cinta Pascal: 4 × 1 + 1 × 3 = 7).
Por el contrario, 19 231 no es divisible por 7 porque 1 × 1 + 3 × 3 + 2 × 2 + 9 × (−1) + 1 × (−3) = 1 + 9 + 4-9-3 = 2 n no es un múltiplo de 7.

Prueba de cualquier número

En general, para determinar si un número A es divisible por M , procedemos en varios pasos:

descomponemos M en la forma m × 2 q × 5 p donde m es primo con 10;
siguiendo la transitividad de la división euclidiana y consecuentemente del lema de Gauss (si a | c, b | cy pgcd (a, b) = 1, entonces ab | c), M divide A si y solo si m , 2 q y 5 p divide A ;
opcionalmente, si tenemos una factorización de m como un producto de los factores dos a dos primos entre sí, también podemos reducir el problema de la divisibilidad por m a problemas similares para estos factores. Por ejemplo: A es divisible por 63 si y solo si es divisible por 9 y por 7.

Divisibilidad por 2 q

A es divisible por 2 q si y solo si el número formado por los primeros q dígitos (comenzando desde la unidad) es divisible por 2 q .

Ejemplo : 79,532,512 es divisible entre 16 (= 2 4 ) porque 2,512 es divisible entre 16.

Demostración : 10 q es un múltiplo de 2 q , por lo que podemos deshacernos de la parte completa del número que es múltiplo de 10 q .

Divisibilidad por 5 p

A es divisible por 5 p si y solo si el número formado por sus p primeros dígitos (comenzando desde la unidad) es divisible por 5 p .

Ejemplo : 9,864,375 es divisible por 125 (= 5 3 ) porque 375 es divisible por 125.

Demostración : 10 p es un múltiplo de 5 p , por lo que podemos deshacernos de la parte completa del número que es múltiplo de 10 p .

Divisibilidad por m primo con 10

Cinta de Pascal

El enunciado 2 anterior está generalizado (consulte el artículo detallado para ver más ejemplos): uno calcula de antemano el resto de cada potencia de 10 en la división por m (eventualmente disminuye m si excede m / 2). Como m es primo con 10, solo hay un número finito de residuos para calcular porque esta "cinta" de residuos es periódica : la vemos tan pronto como encontramos 1 como residuo, que el teorema de Euler permitió predecir. Entonces podemos reemplazar, escribiendo el número A , cada potencia de 10 por su resto: el número obtenido siempre tendrá el mismo resto que A en la división por m .

Eliminación de unidades

Este método le permite realizar siempre un solo tipo de operación.

Dado que m es primo con 10, existe un número entero k tal que 10 × k ≡ 1 mod m . Ésta es la aplicación del teorema de Bachet-Bézout . Entonces el número A será divisible por m si y solo si el número | d + ( k × a 0 ) | es un múltiplo de m , donde d denota, como antes , el número de decenas de A y un 0 es su dígito de unidades. Entonces, basta con reiterar este principio tantas veces como sea necesario .

Demostración -

A = ( d × 10) + a 0 por lo tanto A es divisible por m si y solo si ( d × 10) + a 0 ≡ 0 mod m .

Como k es primo con m , podemos multiplicar la congruencia por k manteniendo la equivalencia, y como 10 × k ≡ 1 mod m , tenemos:

A es divisible por m si y solo si d + ( k × a 0 ) ≡ 0 mod m .

Ejemplo :

La primera dificultad es encontrar este entero k (lo más cerca posible de 0). Por ejemplo, para m = 7, este número entero es –2 porque –20 ≡ 1 mod 7 (para m = 93, este número entero sería 28 porque 280 ≡ 1 mod 93).

Luego, para comprobar, por ejemplo, que 826 413 es divisible entre 7:

826,413 es divisible por 7 si y solo si 82,641 - 2 × 3, es decir, 82,635, es;

82.635 es divisible por 7 si y solo si 8.263 - 2 × 5, es decir, 8.253, es;

8 253 es divisible por 7 si y solo si 825 - 2 × 3, es decir, 819, es;

819 es divisible por 7 si y solo si 81 - 2 × 9, es decir, 63, es;

finalmente, 63 es divisible entre 7 porque 6 - 2 × 3, es decir, 0, lo es.

Este método tiene la ventaja de terminar Después de n pasos si el número A es del orden de 10 n .

Reducir el tamaño del número

Para un número muy grande, este trabajo puede acortarse precediéndolo con una reducción de este número. Primero encontramos el entero más pequeño r > 0 tal que 10 r ≡ ± 1 mod m (para 10 r ≡ +1 mod m , este entero r es el período de la cinta Pascal en base diez ), luego aplicamos el método de la "Cinta pascal en base 10 r ", base para la que la clave de divisibilidad es muy sencilla:

El entero A se puede dividir en n r bloques de r dígitos $A = \ sum _ {{i = 0}} ^ {{n_ {r} -1}} A_ {i} 10 ^ {{ri}}$

si 10 r es congruente con 1 módulo m , el entero A tiene el mismo resto que la suma de estos n r bloques.
10 si r es congruente a -1 modulo m , toda la A incluso sigue siendo que la suma de alternancia de estos n r bloques: $A 0 - A 1 + A 2 - ...$ .

Obtenemos así un número B cuyo orden de magnitud es cercano a 10 r .

Ejemplo :

10 6 ≡ 1 mod 7 así que para divisibilidad entre 7, cortaremos en rodajas de 6.

1000 109 826 303 es divisible por 7 si y solo si 826 303 + 109 + 1, es decir 826 413, lo es. Una vez reducido el número, uno u otro de los dos métodos anteriores muestra que es divisible por 7.

Podemos reducir aún más el tamaño del número si observamos que 10 3 ≡ –1 mod 7 y que podemos sumar alternativamente los bloques de 3 dígitos:

1000 109 826 303 es divisible por 7 si y solo si 303 - 826 + 109 - 0 + 1, es decir, –413, lo es. Uno u otro de los dos métodos anteriores muestra que 413 es divisible por siete.

Nota sobre la complejidad algorítmica

En última instancia , uno puede encontrar de esta manera, para cada M , un criterio de divisibilidad por M . Primero debe notarse que existe un criterio general iterativo: un número A es divisible por M si el resto de la división euclidiana de A por M es cero. Dicho cálculo se lleva a cabo en una serie de operaciones determinadas por el número de dígitos de A (la complejidad es lineal).

Los algoritmos presentados aquí son de hecho variantes de este algoritmo general: hemos visto que se obtuvieron mediante un cálculo modular, que se basa en la noción de división euclidiana. Por consiguiente, su complejidad es lineal: en cada etapa de cálculo, que son llevados de vuelta a probar la división por m de un número que tiene un dígito menos que el número anterior, y el número total de pasos es del orden del número de figuras A . Para un cálculo a mano en base diez , al menos para divisores pequeños m , la ventaja de estos métodos sobre el método general es evitar cálculos de división intermedia.

Sin embargo, estos métodos solo proporcionan un criterio de divisibilidad, mientras que el método general proporciona el cociente y el resto.

Bibliografía

André Deledicq , El júbilo en las matemáticas , París, ACL - Les éditions du Kangourou,2005, 32 p. ( ISBN 978-2-87694091-8 )

enlaces externos

(en) Leonard Eugene Dickson , Historia de la teoría de los números (en) [ detalle de las ediciones ], Vuelo. Yo, cap. XII
(en) Edwin O'Shea, " Divisibility Tests Unified: Stacking the Trimmings for Sums " ,junio de 2014
(en) Marc Renault, “ Trucos estúpidos de divisibilidad: 101 formas de aturdir a tus amigos ” , Math Horizons (en) , vol. 14, n o 22006, p. 18-21, 42 ( leer en línea )