En la anterior entrega vimos dos conceptos muy útiles para nuestro propósito: Las congruencias y los restos potenciales. Tengo que añadir que mi hermano ya sabe hacer reglas de divisibilidad con este método y sólo tiene 11 años… así que esto puede aprenderlo cualquiera.

—————————————————————————————————————————————————————————-

“RESOLVER” CONGRUENCIAS:

La forma en que le he explicado a mi hermano las congruencias ha sido muy simple: “Las congruencias son una operación más”. Es decir, le he dicho que a las sumas, restas, multiplicaciones, divisiones, potencias y raices tiene que añadir las congruencias. (Y de paso le he metido las ecuaciones sin que se entere )

Si yo os pongo lo siguiente: 1 + X = 4 , estoy seguro de que todos sabriais decirme que, para que se cumpla la ecuación, la X tiene que valer 3, es decir, X = 3.

Con las congruencias es igual, sólo que la ecuación está “encubierta”. a ≡ b (mod n) significaba que (a – b) se puede dividir entre n. Por tanto si yo os digo que 7 ≡ 1(mod 3) os estoy diciendo que (7 – 1) es 6 y que 6 se puede dividir por 3.

Si ahora os pregunto, ¿qué valor puede tener la X para que la siguiente congruencia sea correcta?

5 ≡ X (mod 3)

A nadie debería costarle ver que 5 – X tiene que ser divisible por 3… así que nos vale por ejemplo X = 2. Así de simple es “resolver” una congruencia. Aunque en realidad no estamos “resolviendo” nada (de ahí las comillas)… hay infinitos valores de X que nos dan soluciones válidas. Para nuestro propósito siempre nos vamos a quedar con la solución más cercana a 0 que podamos encontrar (recordemos que X puede tener también valores negativos).

Si sabeis encontrar valores de X (viva la cuenta de la vieja) sabeis resolver congruencias al nivel que necesitamos. Ahora sólo necesitais saber una cosa, las congruencias que vamos a resolver son de esta forma:

10 ≡ X (mod n) donde n va a ser el número para el que queramos encontrar las reglas de divisibilidad.

—————————————————————————————————————————————————————————-

HOWTO RESTOS POTENCIALES:

Vamos a aprender a calcular los restos potenciales de b módulo n con una pequeña receta… sólo hay que seguir estos dos pasos, teniendo en cuenta siempre que usamos las congruencias del tipo 10 ≡ X (mod n):

1. r(0) = 1 (el primer resto r(0) siempre será 1)
2. r(i+1) es igual al resto de la división entera de [X*r(i)] / n

(Por cierto, la división entera es la que hacíamos de pequeños, sin usar decimales)

Calculándo esos tarde o temprano nos encontraremos con uno de estos casos:

• r(i) = 0 …. si en algún momento uno de los restos es 0, todos los siguientes también serán 0.
• r(i) = r(j) … si dos restos se repiten entramos en un bucle y se irán repitiendo los siguientes. Tendremos que r(i+1) = r(j+1).

Lo creais o no, ya sabemos calcular los restos potenciales para cualquier congruencia… aunque claro, todo esto lo vamos a ver mucho mejor con un buen ejemplo.

—————————————————————————————————————————————————————————-

EJEMPLO 1:

Calcular los restos potenciales para la siguiente congruencia: 10 ≡ X (mod 2).

Lo primero es conseguir un “buen” valor para la X. Siempre vamos a tener dónde elegir, aquí seguramente se nos pasarán por la cabeza el 10 o el 8… ya que 10 – 10 = 0 y 10 – 8 = 2, pero a nosotros nos interesa que la X tenga un valor tan próximo a 0 como sea posible… fijaos que el mismísimo 0 nos sirve: 10 – 0 = 10 y el 10 se puede dividir por 2, con lo que X = 0 cumple la congruencia.

Ahora que ya tenemos un buenísimo valor de X, la congruencia nos queda 10 ≡ 0 (mod 2)… ya podemos seguir para calcular los restos pues tenemos los dos valores que necesitamos: X = 0 y n = 2.

r(0) = 1 (SIEMPRE!!)

r(1) es el resto de la división [X*r(0)]/n. Es decir: el resto de (0*1)/2. Al hacer la división 0/2 vemos que el cociente es 0 y EL RESTO también. Por tanto: r(1) = 0.

No necesitamos calcular r(2) porque ya sabemos que será igual a 0. Tal y como os dije más arriba, siempre nos vamos a encontrar con un r(i) = 0 o un r(i) igual a uno de los restos anteriores, en el primer caso todos los siguientes serán 0 y en el segundo se irán repitiendo los restos a partir del primer valor repetido.

—————————————————————————————————————————————————————————-

EJEMPLO 2:

Vamos a hacer lo mismo con la congruencia: 10 ≡ X (mod 3).

Lo primero es buscar un buen valor de X, tan cercano a 0 como sea posible. En seguida os dareis cuentas de que lo mejor será tomar X = 1, ya que 10 – 1 = 9, que se puede dividir por 3.

La congruencia nos queda: 10 ≡ 1 (mod 3). Por tanto X = 1 y n = 3.

Calculemos los restos potenciales:

r(0) = 1 (¡este es así siempre!)

r(1) es el resto de la división [X*r(0)]/n. Es decir: el resto de (1*1) /3. Al hacer la división 1/3 vemos que el cociente debe ser 0 y EL RESTO 1.

Como r(1) = r(0) no necesitamos calcular r(2), ya que se van a sepetir todos los “r” que haya entre r(1) y r(0)… en este caso sólo están ellos mismos así que todos los r(i) que necesitemos calcular valdrán 1.

—————————————————————————————————————————————————————————-

Como decía mi abuelo, “con esto y un bizcocho buena sombra nos cobija“… es igual, mi abuelo estaba loco… Sólo nos falta aprender a utilizar estos conocimientos para crear reglas de divisibilidad, cosa que haremos en el próximo post.

Es posible que esto también os haya sonado a chino, pero en realidad es muy sencillo. Mientras escribía esto mi hermano ha hecho (él solito) reglas de divisibilidad para los números 7, 13 y 15 (y ha empezado con el 17). Estoy seguro de que cualquiera de vosotros es capaz de seguir las instrucciones que os he dado para calcular restos potenciales, sólo teneis que intentarlo, es un proceso totalmente mecánico y que se aprende en seguida. Lo mejor sería que repitiéseis los dos ejemplos que os he dado y, si os salen, intentarlo con el 4 y el 5 que son sencillísimos. (Pista: En ambos casos nos encontramos restos iguales a 0)
Lo primero que ha hecho mi hermano ha sido escribir un número al azar de 20 cifras (por lo menos) y ha ido corriendo a decirle a mi padre si sabe si se puede dividir por 2, por 3, por 5, por 7… que jodío, hace un rato él tampoco sabía. xD

Como siempre: Cualquier duda será contestada en los comentarios y si veis que, por zoquete, me he equivocado en algo echádmelo en cara para que subsane mis errores antes del día del juicio.

6 incautos »