En este y en un próximo escrito pretendo abordar con el suficiente detenimiento este teorema fundamental de la aritmética.

De entrada, como muestra de que el mundo intelectual es un pañuelo, y de lo relacionadas e imbricadas que están la lógica filosófica y la matemática, recordaré que, sin ir más lejos, la célebre gödelización se basa en este teorema.

--Ahora bien --preguntará quizá alguien--, ¿qué es eso de la gödelización?

A lo que se puede responder que:

--La gödelización no es más que la representación de cualquier fórmula de la lógica de predicados mediante un número natural, el cual número es producto de un conjunto de factores primos con sus correspondientes exponentes.

--Ya puestos –seguirá preguntando el susodicho alguien--, ¿en qué consiste el teorema fundamental de la aritmética?

--Pues es aquel teorema que establece –sería la respuesta-- que cualquier número natural compuesto tiene una única descomposición posible en factores primos.

Yendo a lo de la gödelización, se trata de asignar a cada símbolo de la lógica un número entero positivo o “número de Gödel”. Pongamos por caso:

p = 1, q = 2, ^ = 3, { = 4, } = 5, ~ = 6, ¬ = 7, …

Entonces, si tenemos una fórmula lógica cualquiera, a sus componentes les asignamos los números primos correlativos a partir del 2. Así,

p ~ q ----> 2 3 5,

a partir de lo cual el "número de Gödel" de esos símbolos se obtiene afectando cada uno de los enteros primos con el correspondiente número del símbolo. En este caso:

p ~ q = 2*(3^6)*(5^2) = 2*729*25 = 36450.

Si, a la inversa, nos encontrásemos con ese número de Gödel, sería sencillo averiguar inmediatamente de qué fórmula lógica se trata, descomponiendo ese número en factores primos:

36450 = 2*(3^6)*(5^2) = p ~ q

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

Veamos ahora una primera demostración del teorema fundamental de la aritmética antes enunciado. Una vez más se tratará de recurrir al viejo y bien acreditado procedimiento indirecto de reducción al absurdo.

Es decir, supongamos que, si existe un entero > 0 descomponible en dos productos diferentes de primos, habrá uno menor que todos los demás, llamémosle m, para el que también se verifique esa propiedad:

m = p1p2p3…pr = q1q2q3…qs, [1]

donde los números 1,2,3… y las letras r y s son subíndices, y los correspondientes p y q son factores primos en orden creciente:

p1 < p2 < p3 < … < pr
q1 < q2 < q3 < … < qs

Resulta ahora que p1 tiene que ser distinto de q1, pues, si fuera iguales, dividiendo (*) por p1 = q1 obtendríamos dos descomposiciones distintas para un entero x < m, lo que se contradice con la elección que hicimos de m como el menor de los números para el que eso es posible. Así pues,

p1 > q1, o bien p1 < q1.

Supongamos que p1 < q1 (si fuese p1 > q1, el razonamiento sería éste mismo, solo que intercambiando las letras p y q). Obtengamos entonces el número natural

m’ = m – p1q2q3 … qs [2]

Teniendo en cuenta (*),

m’ = p1p2p3…pr – p1q2q3…qs = p1(p2p3…pr – q2q3…qs) [3]
m’ = q1q2q3…qs – p1q2q3…qs = (q1 – p1)q2q3…qs [4]

Dado que p1 < q1, de [4] resulta que m’ es un entero positivo, pero, por [2], m’ < m. De donde se deduce que la descomposición de m’ debe ser única. Pero, según [3], p1 es un factor de m’, de modo que, por [4] se concluye que p1 ha de ser factor de (q1 – p1) o bien de q2q3…qs.

La última hipótesis es imposible, dado que p1 es menor que todas las q. Por lo tanto, p1 debe ser un factor de (q1 – p1), por lo que existirá un h tal que

q1 – p1 = h*p1, o sea, q1 = (h + 1)*p1,

lo que contradice el hecho de que q1 es un número primo. Esta contradicción significa que la hipótesis inicial era absurda, y, por tanto, el teorema fundamental de la aritmética queda demostrado.

Teorema fundamental de la aritmética, II

En este y el siguiente post me propongo abordar el entretenido Teorema Fundamental de la aritmética desde el punto de vista de los Elementos (libro VII, 1 y 30-1; libro IX, 14) de Euclides. Para lo cual será necesario tocar de entrada el llamado algoritmo del inmortal matemático griego.

Un ‘algoritmo’ (palabra derivada del nombre del gran algebrista persa al-Jwarizmi) es un procedimiento o conjunto de procedimientos usados para resolver un problema. Veamos en qué consiste el de Euclides.

Por la matemática elemental o primaria sabemos que “dividendo es igual a divisor multiplicado por cociente más resto, si lo hay”. Lo cual, expresado con símbolos, es

a = bq + r, 0≤ r < b. [1]

Ejemplos: 717 = 5*143 + 2, 624 = 8*78 + 0.

Pues bien, de este sencillo hecho aritmético se deduce el algoritmo de Euclides, utilizado para hallar de un modo fácil, seguro y elegante el MCD, o máximo común divisor de dos números naturales.

Sean a y b dos enteros cualesquiera distintos de cero. Consideremos el conjunto de todos los números que dividen simultáneamente a a y b. Solo hay un número finito de estos divisores (pues, como es lógico, ninguno podrá ser mayor que a o que b), y entre ellos habrá uno mayor que todos los demás, al que llamamos d. Pues bien, este número d es el MCD, lo cual se suele escribir

(a, b)= d, que se lee: "el máximo común divisor de a y b es d".

Por ejemplo, (27, 117) = 9, máximo común divisor este que no es demasiado difícil hallar, ya que 27 = 3^3, 117 = 13*3^2, donde la máxima parte común es evidentemente 3^2. Ahora bien, si los números a y b son más grandes, la cosa se complica a veces de manera notable y, si se va de prisa, es aconsejable hacer uso de un algoritmo como el euleriano siguiente.

De la expresión [1] se sigue que

(a, b) = (b, r), [2]

y ello porque todo número h que divide a a y b,

a = mh, b = nh,

dividirá así mismo a

r = a – bq = mh – nhq = h(m – nq).

Y, recíprocamente, según puede comprobarse de manera análoga, todo número que divide a b y r divide también a a. En consecuencia, todo divisor común de a y b es también divisor común de b y r, y al revés.

Por lo tanto, siendo el conjunto formado por todos los divisores comunes a a y b idéntico al formado por todos los divisores comunes a b y r, resulta que el mayor de los divisores comunes a a y b ha de ser igual al mayor de los divisores comunes a b y r, con lo que queda demostrada la igualdad [2].

Hagamos uso de tal igualdad en un caso concreto y veamos qué ocurre. Sean, por ejemplo, los números a = 5733 y b = 2310. Dividiendo uno por otro y prosiguiendo según [2], vamos hallando

5733 = 2310*2 + 1113 --> (5733, 2310) = (2310, 1113)
2310 = 1113*2 + 84 --> (2310, 1113) = (1113, 84)
1113 = 84*13 + 21 --> (1113, 84) = (84, 21)
84 = 21*4 + 0 --> (84, 21) = (21, 0) = 21.

De modo que (5733, 2310) = 21.

En el tercero y último post de esta serie veremos un corolario y un lema a partir de los cuales podremos volver a demostrar, pero esta vez a la manera euclidiana, el Teorema Fundamental de la aritmética

 

Teorema fundamental de la aritmética, y III

Al igual que hizo don Benito Spinoza con su Ética, en los Elementos Euclides expone su algoritmo more geometrico demonstrato, lo cual no deja de resultar un tanto chocante para el lector moderno.

Como hemos visto, por divisiones consecutivas

a = bq1 + r1 (0 < r1 < b)
b = r1q2 + r2 (0 < r2 < r1)
r1 = r2q3 + r3 (0 < r3 <r2)
. . . . . . . . . . . . . . .
r(n-2) = r(n-1)qn + rn (0 < rn <r(n-1))
r(n-1) = rnq(n+1) + 0, [1]

de donde

(a, b) = rn,

es decir, que el MCD de dos números (a,b) es igual al último resto mayor que cero en la sucesión [1]. Lo cual es evidente, ya que

(a,b) = (b,r1), (b,r1) = (r1,r2),…, (r(n-1),rn) = (rn,0) = rn.

Pues bien, a partir de las igualdades [1] se deduce el siguiente importante

Corolario: Si d = (a,b), entonces existen dos enteros m y n tales que d= ma + nb.

En efecto, según [1], b > r1 > r2 > … > 0, y

r1 = a – bq1 = m1.a + n1.b,

con m1 = 1 y n1 = -q1

r2 = b – r1.q2 = b – q2.(a – bq1) = -q2.a + b(1 + q1) = m2.a + n2.b,

con m2 = -q2 y n2 = 1 + q1, etc.

Ejemplo.

(187, 77) = 11
187 = 2*77 + 33, 77 = 2*33 + 11, 11 = 1*11 + 0
33 = 187 -2*77,
11 = 77 – 2*33 = 77 – 2(187 - 2*77)
11 = -2*187 + 5*77

No es difícil imaginar la importancia de este corolario para la resolución de ecuaciones diofánticas. Pero vayamos ya con el lema que nos va a permitir demostrar con rapidez y al modo euclidiano el Teorema Fundamental que venimos fatigando:

Lema. Si un número primo p divide a un producto ab, entonces divide a uno de esos factores, a ó b.

Si el primo p no divide a a, entonces (a, p) = 1, y en consecuencia será posible hallar m y n tales que

1 = ma + np --> b = mab + npb.

Pero si p divide a ab, será ab = pr, de modo que

b = mpr + npb = p(mr + nb),

es decir: que p divide a b, con lo que queda demostrado el lema.

Ese resultado puede extenderse trivialmente a productos de más de dos factores: a(bc), (ab)(cd), etc. De donde se sigue de manera inmediata el Teorema Fundamental de la aritmética.

Supongamos, en efecto, que tenemos dos descomposiciones distintas de un entero N:

N = p1p2p3…pr = q1q2q3…qs

Como p1 divide al segundo miembro, ha de dividir también al tercero y a cada uno de los factores qk. Pero qk es primo, por lo cual p1 = qk, y es este un factor que podemos suprimir de las anteriores igualdades. Y así sucesivamente, lo que prueba que las dos descomposiciones anteriores son idénticas. QED.