Cinta de Pascal

El término cinta de Pascal se refiere a una técnica para determinar si un número entero $N$ es divisible por otro número entero $D$ utilizando la estructura de números de $N$ en una base $B$ . Los fundamentos teóricos de este método, se demuestran mediante la teoría de congruencia de números enteros. La cinta de Pascal permite calcular la clase de congruencia de $NmodD$ (mod = módulo).

Blaise Pascal propuso su método antes de que se estableciera esta teoría en De numeribus multiplicibus.^[1]

Durante todo el artículo, $N$ es el número del que queremos conocer la divisibilidad con el número $D$ , y $B$ es la base en la que se encuentra $N$ .

Construcción de una cinta de Pascal

El principio de la Cinta de Pascal es identificar para cada potencia de la base $B$ , el resto de la división euclídea entre $D$ .

Para una base $B=10$ y $D=7$ sería:

$10^{0}=0*7+1$
$10^{1}=1*7+3$
$10^{2}=14*7+2$
$10^{3}=142*7+6$
$10^{4}=1428*7+4$
$10^{5}=14285*7+5$
$10^{6}=142857*7+1$
$10^{7}=1428571*7+3$
$10^{8}=14285714*7+2$
$10^{9}=142857142*7+6$

Vemos que se siempre se repite la serie 1, 3, 2, 6, 4, 5, 1... La parte de los restos forman la Cinta de Pascal en una base $B$ por el divisor $D$ . Esta Cinta de Pascal es la que utilizaremos para saber si un número $N$ es divisible por otro número $D$ .

Las primeras cintas de Pascal en base 10

Las primeras cintas de Pascal en base decimal (base 10) son las siguientes:

0…
1, 0…
1, 1…
1, 2, 0…
1, 0…
1, 4, 4…
1, 3, 2, 6, 4, 5, 1, 3, 2, 6…
1, 2, 4, 0…
1, 1…

Uso de una Cinta de Pascal para la divisibilidad

La utilización de una cinta de Pascal para probar la divisibilidad de un número, pasa por la transformación de ese número en otro número más pequeño, que tiene el mismo resto al realizar la división por $D$ .

Por ejemplo, para saber si el número 123 456 789 es divisible entre 3.

La Cinta de Pascal de 3 es 1, 1, 1, 1, 1… Por lo que el nuevo número es: $1\times 1+1\times 2+1\times 3+1\times 4+1\times 5+1\times 6+1\times 7+1\times 8+1\times 9=1+2+3+4+5+6+7+8+9=45$ .

¿Será 123 456 789 divisible entre 7? Comenzamos alineando la Cinta de Pascal de 7 con el número desde la derecha, por lo que escribimos el número revés, quedaría:

9 8 7 6 5 4 3 2 1
1 3 2 6 4 5 1 3 2

A continuación sumamos los productos entre elementos de la Cinta de Pascal: $9\times 1\dotplus 8\times 3\dotplus 7\times 2\dotplus 6\times 6\dotplus 5\times 4\dotplus 4\times 5\dotplus 3\times 1\dotplus 2\times 3\dotplus 1\times 2=134$ . Como sigue siendo un número muy grande, lo podemos repetir para simplificar más el número:

4 3 1
1 3 2

Volvemos a sumar los productos entre los elementos de la Cinta de Pascal: $4\times 1+3\times 3+1\times 2=15$ . Podemos simplificar aún más el número, lo que nos daría:

5 1
1 3

$5+3=8$ , que no es un múltiplo de 7, por lo que el número 123 456 789 no es múltiplo de 7, al igual que el número 134 y el 15. Por otro lado, también sabemos el resto de todos estos números (8, 15, 134 y 123456789) entre 7, que es 1.

Por conveniencia, podemos escribir la Cinta de Pascal de derecha a izquierda, y mantener el orden natural de escritura de los números.

Corrección del criterio de divisibilidad

La explicación del funcionamiento de las Cintas de Pascal se hacen naturalmente a través de la teoría de congruencia de números enteros, donde se dice que un número $A$ es congruente con $B$ módulo $C$ , Si para la división euclídea de $A$ entre $C$ , se obtiene de resto $B$ (O lo que es lo mismo que $A-B$ es un múltiplo de $C$ ). Se anota de la forma $A\equiv B{\pmod {C}}$ .

Por ejemplo:

$8\equiv 13\equiv 3{\pmod {5}}$ dónde $8-13$ y $8-3={\dot {5}}$ (Múltiplo de 5).
$100\equiv 4{\pmod {12}}$ dónde $100-4={\dot {12}}$ (Múltiplo de 12).

Dos propiedades importantes de las congruencias son:

Si $a\equiv b{\pmod {m}}$ y ${\displaystyle c\equiv d{\pmod {m}}}\Rightarrow a\times c\equiv b\times d{\pmod {m}}$ .
Si $a\equiv b{\pmod {m}}$ y ${\displaystyle c\equiv d{\pmod {m}}}\Rightarrow a+c\equiv b+d{\pmod {m}}$ .

El objetivo es demostrar que la suma de productos es congruente con el mismo número:

$B^{i}\equiv r_{i}\mod D$ por construcción,
$c_{i}\times B^{i}\equiv c_{i}\times r_{i}\mod D$ por el producto de las congruencias (Propiedad 1),
$N=\sum _{i}c_{i}\times B^{i}\equiv \sum _{i}c_{i}\times r_{i}\mod D$ por suma de congruencias (Propiedad 2)

La consecuencia directa es que si $N$ es un múltiplo de $D$ , entonces $\sum _{i}c_{i}\times r_{i}$ también lo es.

$c_{i}$ es la cifra en la escritura de $N$ en base $B$ .

$r_{i}$ es el elemento de la cinta de Pascal de $D$ en base $B$ .

Algunas propiedades de la Cinta de Pascal

El número de restos posibles entre la división por $D$ es finito e igual a $D$ (de 0 hasta $D-1$ ). Por lo cual obligatoriamente se repite.
Si en la Cinta de Pascal aparece el $0$ , todos los siguientes elementos son $0$ porque si $B^{p}$ es un múltiplo de $D$ , todas las siguientes potencias, que son múltiplos de $B^{p}$ , son también múltiplos d e $D$ . En este caso, a partir del rango de $p$ , la Cinta de Pascal es constante, es decir periódico y con periodo $1$ .
Si el $0$ no aparece, y uno de los restos diferentes a $0$ se repite, entonces $B^{p}$ es congruente con $B^{m}$ , por lo cual $B^{p+k}$ es congruente con $B^{m+k}$ , con lo que se demuestra, que la Cinta de Pascal es, a partir del rango de $p$ periódica y de periodo $m-p$ . El número de restos posibles (El $0$ excluido) es $D-1$ , y el periodo es menor o igual a $D-1$ .
Se obtiene una Cinta de Pascal, donde su funcionamiento (Que determina el tipo de congruencia con módulo $c$ de un número) , es igual que cuando reemplazamos cada número de la Cinta de Pascal por cualquier número que sea congruente con el módulo $c$ . Por ejemplo, para $c=7$ , una Cinta de Pascal equivalente a $1,3,2,6,4,5...$ es $1,3,2,-1,-3,-2...$