Pascal e a divisibilidade

No eido da aritmética, unha das súas dificultades é o de determinar de xeito sinxelo se un número é exactamente divisíbel por outro; se se trata de números pequenos, podemos simplemente facer a división e ver se da un resultado exacto (=sen resto), pero se un ou dous números participantes (dividendo, divisor) son moi grandes, a división pódenos levar moito tempo.

É por iso que dende tempos inmemoriais os calculistas buscaron 'trucos rápidos' que lles axudasen nesta tarefa. Así tódolos números pares (rematados en 0, 2, 4, 6 ou 8) son divisíbeis por 2; tódolos números cuxas cifras sumadas dan 3 ou mútiplos de 3 son divisíbeis por 3; tódolos números cuxo último par de dixitos é divisíbel por 4 son divisíbeis por 4; tódolos números que rematan en 0 ou 5 son divisíbeis por 5; tódolos números divisíbeis por 2 e por 3 son divisíbeis por 6, etc...

No século XVII, Blaise Pascal, fedellando nestes terreos, descubriu un método (pedantemente, un algoritmo) de computar divisibilidades a partir dos díxitos dun número. O seu punto de partida é o seguinte:

1) Collamos un número calquera, q, do que desexamos saber se divide exactamente un número p.

2) comprobemos cal é a expansión decimal de q: querse dicir, dividamos 1/q e vexamos qué nos sae no cociente e nos restos.

3) Os restos son os que nos interesan, xa que teñen certas propiedades (na maioría dos casos, con carácter cíclico; limitación a un ciclo non maior que q-1) que nos permiten elaborar unha ecuación coa que podemos comprobar se p é divisíbel por q de xeito máis doado que facendo a división. 

Para visualizalo, collamos un par de números concretos, por exemplo q=11 e p=3409.

O primeiro paso consiste na comprobación da expansión decimal de 1/11. Vexamos:

1/11 = 0, resto = 1; 10/11 = 0, resto 10; 100/11 = 9, resto 1; 10/11 = 0, resto 10, e así, sucesivamente e ata o infinito.

Vemos que a expresión decimal de 1/11, a partir dos cocientes vai ser 0.09090909090..., onde os dous díxitos 09 repítense indefinidamente, constituíndo o periodo (cun tamaño de 2 díxitos). 

Dicíamos que a Pascal non lle interesan a expansión decimal nin os cocientes, senón os restos, que tamén se repiten, oscilando entre 1 e 10. O ciclo de 11, xa que logo, é de 2 membros (o ciclo podería ser de ata 11-1 = 10 membros -non é o caso- ou de calquera dos divisores de 10 -neste caso, 2, que é, en efecto, divisor de 10).

Se nos fixamos na expansión decimal de 1/11, percibimos que nos permite representar calquera potencia de 10 coma o resultado da ecuación 11X+R (onde X é calquer número e R o resto); así, 1 (10^0) é 11 por 0 mais 1; 10 (10^1) é 11 por 0 mais 10; 100 (10^2) é 11 por 9 mais 1; 1000 (10^3) é 11 por 90 mais 10, e así, sucesivamente.

Porqué nos interesan as potencias de 10? Pois porque os números que empregamos habitualmente teñen esa base, e poden representarse sinxelamente coma sumas de potencias de 10; por exemplo, o número p, do que queremos comprobar a súa divisibilidade,  no noso caso concreto era 3409. O que ás veces esquecemos (dado o interiorizado que o temos) é que o conxunto de díxitos 3409 'significa' que temos que facer a seguinte operación para chegar a el:

3 x 1000 + 4 x 100 + 0 x 10 + 9 x 1

Ou o que é o mesmo, poñendo a 10 e os seus mútiplos como potencias:

3 x 10^3 + 4 x 10^2 + 0 x 10^1 + 9 x 10^0

Xeralizando, podemos dicir que a ecuación que nos da un número en base decimal calquera N sería N=Ax10^α + Bx10^α-1 ... Zx10^0. No caso que nos ocupa, como p ten 4 díxitos, a súa ecuación abstracta sería p = Ax10^3 + Bx10^2 + Cx10^1 + Dx10^0, válida para calquer número de 4 cifras, neste caso, e onde A, B, C... son os coeficientes (o número que multiplica á correspondente potencia de 10).

Se collemos, xa que logo, esta última ecuación e substituímos nela as potencias de 10 polos equivalentes na forma 11X+R que vimos antes, podemos facer as seguintes manipulacións alxebraicas:

Ax10^3 + Bx10^2 + Cx10^1 + Dx10^0 = Ax(11x90+10) + Bx(11x9+1) + Cx(11x0+10)+Dx(11x0+1) 

= 10A + 11x90A + B + 11x9B + 10C +  11x0C + D + 11x0D

Agrupamos os números, poñendo nun lado todos os que teñen a 11 como multiplicador, e temos

=10A + B + 10C +D + 11x( 90A+9B+0C+0D)

Ímoslle chamar ao resultado de dentro do paréntese "H". Para o que nos ocupa, é igual a cantidade da que se trate. O importante é que a ecuación para calquera número p de 4 cifras fica en

p  = 10A + B  + 10C + D + 11H

Este ecuación proporciónanos a chave para saber se p (que, insistimos, pode ser calquera número de 4 cifras; logo comprobarémolo para o noso p particular, cuxo valor puxéramos en 3409) é divisíbel por 11. Para que o sexa, está claro que os seus constituíntes teñen que ser divisíbeis por 11. É evidente que 11H é divisíbel por 11, pero qué pasa co resto dos sumandos (10A+B+10C+D)? Pois que para que p sexa divisíbel por 11, esa suma ten que selo tamén.

Con isto chegamos ao paso final. Podemos substituír  p por 3409 e A, B, C e D polos seus coeficientes (A=3; B=4; C=0; D=9); podemos ignorar a suma de H e deixala coa letra.

3409 = 10x3 + 4 + 0x10 + 9 + 11H

3409 = 43 + 11H

3409 será divisíbel por 11 se 43 tamén o é. Como non é o caso, podemos afirmar que 3409 NON é exactamente divisíbel por 11.

Todo este proceso pode parecer máis tedioso que simplemente proceder a facer a división, pero o caso é que se tedes a 'fórmula' do divisor (á que se chega, como vimos para q = 11, logo de analizar a expansión decimal de 1/q e os seus restos), e se o dividendo, no canto de ser un número relativamente pequeno e de 4 cifras ten moitas máis (100 por exemplo), resulta moitísimo máis rápido e sinxelo aplicar o algoritmo aquí descrito que facer a división longa. Por suposto, no caso dun número de 100 díxitos, teríamos tamén que traballar con 100 coeficientes, pero a fórmula en sí non se complicaría demasiado polo carácter periódico dos restos: sería da forma 10A+B+10C+D+10E+F+10G+H... e así sucesivamente.