viernes, 1 de julio de 2011

TEORÍA DE NÚMEROS

Breve historia de la teoría de números

Prehistoria

Podemos decir que la teoría de números empezó con el matemático griego Diofanto de Alejandría en el siglo III d.c. Diofanto escribió  trece libros (siete de los cuales se han perdido) dedicados a la resolución de ecuaciones algebraicas, intentando dar métodos para encontrar sus soluciones enteras o racionales.  Algunos ejemplos de los problemas que trataba en su libro son: ¿Qué números son suma de dos números al cuadrado? ¿Qué números son suma de tres números al cubo?Pero la contribución (indirecta) más importante de Diofanto fue a partir de la traducción al latín de los seis primeros libros con el nombre de Aritmética en 1621 por C.G. Bachet. Esta
traducción fue la que inspiró al verdadero padre de la teoría de números, Pierre de Fermat.

Fermat (1601-1665)

Pierre de Fermat es uno de los matemáticos más importantes de la historia. Aunque de hecho no era matemático "profesional" sino juez. Vivió durante la mayor parte de su vida en Toulouse, dedicandose en las horas libres a las matemáticas. Entre los resultados más importantes que obtuvo podemos destacar la invención (junto con Descartes) de las ahora llamadas coordenadas cartesianas, que permiten "traducir" los problemas geométricos a problemas algebraicos.
Pero los resultados que le han hecho más famoso fueron sin duda los que obtuvo trabajando inspirado en el libro de Diofanto, que dieron origen a la teoría de números. Aunque debido a
la forma de trabajar de Fermat, que no publico sus resultados en vida y solo divulgaba a
través de cartas a sus amigos y colegas, tenemos pocas indicaciones de cuales eran sus métodos para resolver los problemas.
Entre los resultados más conocidos que obtuvo (o anunció) hay:
  • El llamado "Pequeño teorema de Fermat":  Para todo número primo p y para todo número natural a no divisible por p tenemos que p divide a    ap-1-1.

El resultado más famoso de Fermat en la actualidad no es de hecho un resultado suyo, aunque se le denomina el "ultimo teorema de Fermat". Parte de su fama es debida a la manera como
formuló el resultado y también porque se han tardado más de 350 años para darle la razón. La historia empieza después de su muerte en que su hijo publico la edición que tenia Fermat del libro de Diofanto junto con las anotaciones originales de Fermat. En una de ellas, concretamente al margen de la parte en que Diofanto habla de las ternas pitagóricas, Fermat dejo escrito el siguiente enunciado (traducido al lenguaje moderno):
Para cualquier numero natural n mayor o igual que 3, la ecuación:
A  + B  = C
no tiene soluciones (naturales) salvo que A, B o C sean cero.
(Vease aquí una reproducción de estas anotación)
Y añade:
Tengo una demostración maravillosa de este resultado pero este margen es demasiado estrecho para contenerla.
A partir de ese momento muchos de los matemáticos más importantes de la historia intentaron demostrarlo sin éxito has que recientemente, en 1994, Andrew Wiles consiguió demostrar este resultado; aunque no con los métodos que podía conocer Fermat. Queda aún la duda si Fermat tenía o no la demostración de este Teorema....(yo me inclino a pensar que no).

Ternas pitagóricas

El problema de las ternas pitagóricas es:
Como encontrar todos los triángulos rectángulos con lados  A, B y C todos ellos números naturales?






Este problema fue resuelto por Diofanto aunque parece que la solución ya era conocida por los babilonios mucho antes. La solución que expongo aquí es la misma que dio Diofanto pero, claro está, en notación matemática moderna.
Recordemos que el teorema de Pitágoras nos dice que para que exista un triángulo de esta
forma se tiene que cumplir que
                                                A  + B = C
O sea que la pregunta se transforma en: que números A y B naturales cumplen que la suma de sus cuadrados es un cuadrado?  Por ejemplo, A=1 y B=2 no lo verifican ya que la suma de sus cuadrados es 5, que no es un cuadrado. Por otra parte A=3 y B=4 si que lo verifican, ya que
la suma de sus cuadrados es 9+16=25 que es 5 al cuadrado.
A una solución (A,B,C) se la llama una terna pitagórica. Muchos ejemplos de ternas pitagóricas ya eran conocidos por los babilonios:
(3,4,5) , (6,8,10) , (5,12,13), ......................, (4961,6480,8161),........
Ejercicio: Encuentra mas ternas pitagóricas. Hay alguna terna pitagórica con C=7?
Vamos a ver que existe una fórmula que nos da todas las soluciones. Lo haremos en 4 pasos.

Paso 1:

La primera observación es que existen dos tipos de soluciones: las que se obtienen a partir de una menor multiplicando por un número y las que no. Por ejemplo la solución (6,8,10) ha sido obtenida multiplicando la solución (3,4,5) por 2. Por otra parte la solución (5,12,13) no se puede obtener así ya que el único número que divide a 5 es el mismo 5, que no divide a 12.Observemos que de esta forma siempre podemos obtener soluciones ya que si
(A,B,C) es una solución y D es un número cualquiera, entonces
    (DA)+(DB) = D(A+ B) = DC=(DC)
y por lo tanto (DA,DB,DC) es también una solución.
Nos interesará encontrar soluciones (A,B,C) que no se puedan dividir a A, a B y
a C por un mismo número (o sea que A, B y C sean primos entre sí). Llamaremos a estas soluciones primitivas y a partir de ahora solo trataremos estas.
Paso 2:
Sea (A,B,C) una solución primitiva. Entonces no puede ser que exista un número D>1 que divida a A y B y no divida a C, ya que si D divide a A y B, entonces
D divide a  A  + B = C , y por lo tanto D divide a C. En particular A y B no pueden ser los dos pares. Veamos que no puede ser que sean los dos impares:
supongamos que lo fueran; entonces A=2I+1 y B=2J+1 para ciertos I y J. De donde tenemos queC= A  + B = (2I+1)  + (2J+1) =  4I +4I +1 + 4J +4J +1=4(I + I +J +J) +2
Por lo tanto 2 dividiría a C, y por lo tanto 2 dividiría a C, de donde obtenemos que 4 dividiría a C. Pero 4 no divide a  4(I+I +J+J) +2, ya que no divide 2. (Usando la teoría de congruencias podríamos haber hecho este paso de forma mas rápida estudiando la ecuación módulo 4.)
Por lo tanto sabemos que uno de los dos es par y el otro es impar. Podemos suponer cambiando el orden que A es par y B es impar (y por lo tanto C es impar).
Paso 3:
Escribimos la ecuación  C= A  + B, pasando B restando al otro lado, como
A= C - B=(C-B)(C+B)
Tenemos que, como C y B son impares, tanto (C-B) como (C+B) como A son pares. Escribiremos A=2U,  C-B=2V  y C+B=2W para ciertos U, V y W. Obtenemos así la ecuación
(2U)=(2V)(2W)  y por lo tanto  U=VW,
y ademas, que C=V+W y que B=W-V.
Como no existe ningún número D que divida a B y a C a la vez (por el paso 1), tampoco puede existir ningún número D que divida a V y a W a la vez, ya que entonces D dividiría a V+W=C y a W-V=B.
Pero su producto VW=U es un cuadrado, por lo tanto cada uno de ellos es un cuadrado. Digamos que
V=M   y   W=N
para ciertos M y N números.  Tenemos por tanto que B=N-M,  C=N+M  y que A=4U=4VW=4MN, de donde A=2MN.
Paso 4:
Del paso 3 tenemos que si tenemos una terna pitagórica primitiva (A,B,C) con A par, entonces existen dos números N y M tales que
A=2NM,    B=N-M  y  C=N+M.
Observemos que N y M no pueden tener un divisor común ya que entonces A, B y C lo tendrían. Además N y M no pueden ser los dos impares, ya que entonces X e Y serian divisibles por 2.
Solo nos falta ver que dados cualquier N y M sin divisores comunes, entonces los tres números A, B y C construidos arriba son una terna pitagórica primitiva. Pero
A+B=(2NM)+(N-M)=4NM+N+M-2NM=N+M+2NM=(N+M)=C
y por lo tanto son una solución de nuestra ecuación.
 
Teorema: El conjunto de las ternas pitagóricas es el conjunto de los  múltiplos de ternas de la forma
( 2NM , N-M , N+M )
con  N y M números sin divisores comunes, N>M, con N o M par.
 Por ejemplo, la terna (4,3,5)  se obtiene de N=2 y M=1; la terna (12,5,13) de N=3 y M=2; y la terna (6480, 4961, 8161)  de N=81  y M= 40.
Por otra parte tenemos un método para construir ternas pitagóricas: por ejemplo de N=72 y M=5 obtenemos (720,5159,5209).

Algunas conjeturas para números primos

  • La conjetura de los primos gemelos: Diremos que dos números primos p y q son gemelos si q=p+2. Por ejemplo 3 y 5, 5 y 7, 11 y 13, 29 y 31, etc. . La conjetura dice que existen infinitos primos gemelos.
  • La conjetura de Goldbach (mencionada por primera vez en una carta de C Goldbach a Euler en 1742): Cualquier número par más grande que 2 es suma de dos números primos. Algunos ejemplos:
  • 4=2+26=3+38=5+3
    10=7+312=7+514=11+3
    16=13+318=13+520=17+3
    Esta conjetura ha sido verificada hasta 100000000000000, pero aun no se ha encontrado un argumento matemático que demuestre que es cierta para todo número par. De hecho existen resultados ya muy "cercanos" a la conjetura:
    • Se sabe que cualquier número par es suma de 6 o menos números primos(Ramaré, 1995).
    • Se sabe también, demostrado por Chen en 1966, que cualquier número par "suficientemente grande" es suma de un numero primo más el producto de dos números primos. El problema es que no esta claro que es lo que se quiere decir con suficientemente grande....
    • Observase que si la conjetura de Goldbach es cierta, entonces cualquier numero impar mayor que 5 ha de ser suma de 3 o menos números primos, llamada la conjetura de Goldbach impar. Vinogradov probó en 1937 que si n es un número impar suficientemente grande, entonces n es suma de tres números primos. Se deduce de esto que cualquier número par suficientemente grande es suma de 4 números primos o menos. Se ha visto que este "suficientemente grande" puede tomarse 1043000(aun demasiado grande para poder comprobarlo por ordenador).
    • También se sabe que si la Hipótesis de Riemann es cierta, entonces la conjetura de Goldbach impar implica la conjetura de Goldbach (par). De hecho, también se ha visto (Deshouillers, Effinger, Te Riele y Zinoviev en 1997) que si la Hipótesis de Riemann generalizada es cierta, entonces la conjetura de Goldbach también es cierta. Así que, ánimo y a probar la Hipótesis de Riemann!
     
  • ¿Existen infinitos primos de la forma n +1?
  • Dirichlet probó que en cualquier progresión aritmética, o sea de la forma {a + bn | nN},  con  a, b coprimos entre si, existen infinitos números primos. Posteriormente Chevotarev demostró que, fijado b, y si denominamos fi(b):=#{a | 0<a<b y a primo con b} tenemos que, para cada a, el número de primos de la forma a+bn es 1/fi(b) el número de primos totales. Por ejemplo, el numero de primos que en forma decimal acaban en 1 (o en 3, o en 7, o en 9) es un 25% de los totales. Vease por ejemplo el calculo hecho aquí.
  • ¿Existe siempre un número primo entre n  y (n + 1)  ?
  •  Se sabe que siempre hay un primo entre n y 2n, la llamada conjetura de Bertrand, que fue probada por Chebichev.  
  • ¿Hay infinitos primos de Fermat? Aun más, ¿hay algún primo de Fermat además de los cuatro primeros?
  • Un primo de Fermat es un número primo de la forma 2+1. Es posible ver de forma relativamente fácil que si 2+1 es primo, entonces n es también una potencia de 2. Tenemos que  
    n=1n=2n=4n=8n=16n=32
    351725765537641*6700417
    (para n=32 es producto de dos primos). La pregunta es si encontraremos algún otro primo según vayamos tomando potencias de 2.
     
  • ¿Hay infinitos primos de Mersenne?
  • Un primo de Mersenne es un primo de la forma 2-1. Es posible ver fácilmente que si 2-1 es primo, entonces n también tiene que ser un número primo. Denotaremos por M(i) el i-ésimo número de Mersenne. Los primeros números de Mersenne son    
    n=2n=3n=5n=7n=13n=17
    M(1)=37311278191M(6)=131071
    El número de Mersenne más grande que se conoce es M(38)=26.972.593-1 (1 de Julio de 1999). En esta página web se puede leer toda la información sobre números de Mersenne que hay, y incluso bajarse un programa para buscar más números de Mersenne. 


Particiones


Dado un número natural N , ¿de cuantas maneras diferentes podemos expresarlo como suma de otros naturales?
El primer paso a hacer es clarificar el problema. Diremos que dos expresiones de N como
suma de naturales son la misma si permutando los números que aparecen en la suma podemos pasar de una a la otra. Así
6=2+1+2+1    y  6=1+1+2+2
son expresiones iguales de N=6.
Una expresion de este tipo la llamaremos una partición de N. Llamaremos p(N) el número de
particiones de N. Tenemos que:
 
p(n)345678910111213141516171819202122232425
   n357111522304256771011351762312973854906277921002125515751958
Aquí tenemos una lista de todas las particiones de 6:
 6, 5+1, 4+1+1, 4+2, 3+1+1+1, 3+2+1, 3+3, 2+1+1+1+1, 2+2+1+1, 2+2+2, 1+1+1+1+1+1.
La función p(N) crece de forma muy rápida. Por ejemplo tenemos que  (¡ejercicio!)
 p(100)=190.569.292  ,   p(200)=3.972.999.029.388    y
p(1000)=24.061.467.864.032.622.473.692.149.727.991


En esta página de Dario Alpern hay un applet de java que permite calcular las particiones de un número.


La primera pregunta que nos podemos hacer es: ¿Hay alguna fórmula para p(n)?
La respuesta a esta pregunta depende de que es lo que entendemos por "fórmula".
Por ejemplo, la fórmula más famosa (desde mi punto de vista) para las particiones de n se debe a Euler , y dice:

              1
     =  1 + p(1) x + p(2) x2 + p(3) x3 + ... 
  (1-x)(1-x2)(1-x3)...
Dicho de otra forma: si tomamos el producto infinito

   1           1              1 
    .      .   ......
 (1-x)     (1-x )      (1-x3)
entonces este producto esta bien definido para los numeros reales "cerca del 0" (de hecho para los números reales con valor absoluto menor que 1) y su serie de Taylor alrededor del 0 es la serie con coeficientes p(n).
Comentario: Si tenemos una función f(n) definida para los números naturales n, la función F(x) definida por la suma infinita F(X):=f(0)+f(1)x+f(2)x +f(3)x+..... se le llama la función generatriz de f(n). Aunque parezca estraño, a veces es más facil estudiar la funcion generatriz F que la propia función f, y deducir propiedades de f a partir de propiedades de la función F.
¿Cómo se demuestra la validez de esta fórmula? Observemos primero que

      1 
 =1+x+x2+x3+x4+......
   (1-x) 
de donde, sustituyendo x por x en la fórmula anterior, obtenemos una fórmula para cada uno de los miembros del producto infinito anterior. Ahora ya solo tenemos que multiplicar todas estas sumas infinitas para obtener la fórmula buscada, observando que para obtener el coeficiente de x solo tenemos que multiplicar las n primeras sumas infinitas, y solo hasta el grado n. De hecho esta "demostración" no tiene en cuenta los problemas de convergencia de la función, problema que dejamos como ejercicio para los más rigurosos....
Claro que esta fórmula no es realmente muy útil si lo que uno quiere es calcular p(n) de una forma rápida y eficinte (por ejemplo con el ordenador).
Podemos dar alguna fórmula que se adapta un poco mejor al cálculo de p(n), suponiendo conocido p(m) para todo (o para algunos) m menor que n.
Por ejemplo:
 


       p(n)=S (-1)(k+1) ( p(n - k(3k-1)/2)+p(n-k(3k+1)/2))
 
donde la suma S esta evaluada en todos los números enteros k  tales que  k(3k+1)/2 y k(3k-1)/2 estan entre 1 y n, y (-1)^(k+1) es 1 si k es impar y -1 si k es par. O sea que


       p(n)=p(n-1)+p(n-2)-p(n-5)-p(n-7)+p(n-12)+p(n-15)-..........
 

 Otra fórmula que nos relaciona p(n) con la suma s(k) de todos los divisores de n (usualmente denotada sigma(k)) es la siguiente

                   1       n
      p(n) =     S     s(k) p(n-k)
                   n      k=1
donde  p(0)=1 (si se quiere por definición).
Para calcular s(k) observese que si k tiene como factorización en primos k=(p1a1)(p2a2)...(p2at) entonces la suma de los divisores de k es
 
                t      pj(aj+1)  -  1
   s(k)  =  P    
              j=1       pj - 1
donde P indica el producto desde j=1 hasta t.Finalmente podemos dar fórmulas asintóticas para p(n), o sea fórmulas que nos dan p(n) aproximadamente, y cuya aproximación es más buena como más grande sea n. La siguiente fórmula fue conjeturada por Hardy y Ramanujan y probada por Rademacher en 1937. Dice que
 
                        epi  raiz (2n/3)
       p(n) ~=     
                       4n raiz 3
donde e es el número e (=2.718183...), pi es el número pi(=3.14159...), raiz  es la raiz cuadrada, y ~= quiere decir asintoticamente igual, o sea que:
Dos funciones f(x) y g(x) son asintoticamente iguales (f~=g) si el limite cuando x tiende a infinito de f(x)/g(x) es 1.
Una fórmula más fácil de demostrar y que nos da a veces una estimación bastante buena (aunque peor que la fórmula de Rademacher) es
 
     p(n) <  epi raiz (2n/3)

Finalmente tenemos las conjeturas de Ramanujan (probadas de hace ya tiempo)
 
El número p(5m+4) es divisible por 5 para todo m.
El número p(7m+5) es divisible por 7 para todo m.
El número p(11m+6) es divisible por 11 para todo m.


Fracciones continuas


Las fracciones continuas tratan de dar una expresión a los números reales más conveniente para estudiar sus propiedades aritméticas que la expresión en decimales.
Empezaremos por un ejemplo concreto para un número racional concreto.
Tomemos 127/52=2,442307692308. Su parte entera es 2, y podemos escribir
12723

=2+
5252
Cambiamos luego 23/52 por la fracción equivalente 1/(52/23) y repetimos el proceso para la fracción 52/23. Obtenemos:
526

=2+
2323
de donde, substituyendo en la primera igualdad, tenemos
 
1271

=2+
526
2+
23
Podemos ahora seguir este proceso para 6/23 , cambiandola por 1/(26/6)
 
265

=3+
66
y el mismo proceso para 5/6 para obtener
 
61

=1+
55
Aquí el proceso se para. Obtenemos finalmente
1271

=2+
521
2+
1
3+
1
1+
5
La expresión obtenida se llama la fracción continua de 127/52. Usaremos la siguiente notación para escribir esta fracción continua:
127

=[2,2,3,1,5]
52
Observemos que este proceso se puede hacer para cualquier número racional, y ademas siempre se acaba tras un número finito de pasos. La razón fundamental para este hecho reside en el llamado algoritmo de Euclides (que sirve a la vez para calcular el máximo común diviso de un número).Supongamos tenemos una fracción del tipo a/b, con a y b números enteros positivos. Designamos por q1 el cociente entero de a/b, o sea la parte entera de este cociente. Entonces tenemos que

a=q1·b+r2,  con r2<b
Tomemos ahora la división de b por r2, y sea q2 el cociente entero y r3 el resto. Tenemos
b=q2·r2+r3,  con r3<r2
Y de la misma forma vamos obteniendo
r2=q3·r3+r4,  con r4<r3
r3=q4·r4+r5,  con r5<r4
. . . . . . . . . . . . . . . . . .
Los restos de las divisiones obtenidos cumplen que
b>r2>r3>r4>. . . . .>=0 
con lo que para alguna n debemos tenemos que rn+1=0. De las igualdades anteriores obtenemos que
a

=[q1,q2,q3,. . .,qn]
b
La expresión obtenida después de suprimir de una fracción continua todos sus términos a partir de k se llama la fracción k-ésima reducida Dk. Así las fracciones reducidas para 127/52 son:
D1=2,  D2=2+(1/2)=5/2,  D3=17/7,  D4=22/9,  D5=127/52.
Observase que x=9 y y=-22 (números que aparecen en la expresión de D4) son una solución de la ecuación
127x+52y+1=0 
Este hecho no es un coincidencia. Tenemos que si tomamos la ultima fracción reducida Dn-1 de a/b y la expresamos como P/Q, entonces x=Q y y=-P son siempre una solución entera de
la ecuación
a·x+b·y=(-1)n
Vease aquí para aprender a resolver ecuaciones del tipo a·x+b·y=c en los números enteros.
En particular podemos ver que estas ecuaciones o bien no tienen solución o bien tienen infinitas.Nos podemos preguntar ahora: que sucede con los números reales que no son racionales?
Para verlo estudiaremos el caso de la raíz cuadrada de 2:
Empezaremos por la siguiente observación: (Ö2-1)(Ö2+1)=1, y 1 es la parte entera de raíz de 2!
Podemos por lo tanto hacer lo siguiente:
1
Ö2-1=
2+(Ö2-1)
Repitiendo este proceso obtenemos que
 
1
Ö2=1+
1
2+
2+(Ö2-1)
con lo cual tenemos que
Ö2=[1,2,2,2, . . . ] 
repitiendose indefinidamente el 2.
Vemos así que a diferencia del caso de los números racionales, la fracción continua asociada a un número real no racional (o sea un número irracional) es siempreinfinita (por qué?). Por cierto que esto nos demuestra que Ö2 es un número irracional.¿Cuándo cumple la fracción continua asociada a un número real r que se repite indefinidamente (o sea que es periódica)? Pues esto es lo que nos responde el siguiente
TeoremaLa fracción continua asociada a r es periódica si y sólo si r es solución de una ecuación de segundo grado (que usualmente se les llama cuadráticos).
La demostración de este teorema es un poco larga y engorrosa, así que la dejaremos para otro dia. En todo caso diremos que la parte más fácil es demostrar que si es periódica, entonces es solución de una equación de segundo grado. La otra parte, que en cierta forma consiste en dar un método para encontrar la fracción continua de una raiz cuadrada es mucho más difícil.
Si quieres ejemplos concretos de la fracción continua de un número r cuadrático puedes ir  aquí. Si al contrario quieres el número cuadrático asociado a una fracción continua periodica concreta puedes ir aquí.
Por último mencionaremos que el estudio de las fracciones continuas es una pieza clave para la resolución de las llamadas ecuaciones de Pell(-Fermat): si d un número natural, se trata de encontrar todas las soluciones con X e Y naturales de la equación:

X - d Y= 1
Vease por ejemplo aquí  un programa online que da las soluciones "minimales" dado un d concreto. Observese que si d es un cuadrado entonces la ecuación no tiene ninguna solución (salvo X=1, Y=0).



Que números son resta de un cuadrado

menos un cubo?


Ya comentamos en una sección anterior que para en los enteros una ecuación "cuadrática" en los números enteros, o sea encontrar todas las soluciones (X,Y) con X e Y números enteros
de la ecuación:
aX+bXY+cY+dX+eY+f=0
se utilizaban las fracciones continuas. Este problema esta extensamente tratado en muchas partes. Por ejemplo, una pagina web muy interesante donde enseña a resolver estas ecuaciones es:
Métodos para resolver Ax^2 + Bxy + Cy^2 + Dx + Ey + F = 0.
de Darío Alpern. Además tiene un programa online que da todas las soluciones en:
Resolución de ecuaciones cuadráticas de dos variables enteras.Esta vez hablaremos de un problema mucho más difícil y aun no resuelto completamente.
La pregunta que nos proponemos al principio es la siguiente: Dado k un número entero, cuantas (y cuales son) parejas de números enteros X e Y verifican que
Y-X=k  ?
A esta ecuación se la llama a veces la ecuación de Bachet (1621), aunque fue Fermat el primero que estudió algunos casos particulares. También se la llama la ecuación de Mordell ya que fue L.J. Mordell quien la estudio en más detalle (en su tesis). Aunque parece un problema del mismo nivel que el anterior (o quizá más fácil!), la verdad es la opuesta. Vamos a ver algún ejemplo, estudiando los primeros casos que aparecieron históricamente:Fermat (1650):
Fermat puso como problema a la comunidad matemática inglesa probar que las únicas soluciones de la ecuación
Y = X - 2
son  X=3 e Y=5,  y X=3 e Y=-5. Esta es la ecuación de Bachet-Mordell para k=-2.Observase que, si (X,Y) es solución de la ecuación de Bachet-Mordell, entonces (X,-Y) también lo es. A partir de ahora solo contaremos las soluciones con Y positivo.
Nadie en ese momento supo explicar por que, hasta que Euler en 1738 dio una demostración de ese hecho, pero era incompleta, ya que se basaba en un hecho que no se probó hasta 150 años después!
Euler (1738):
Euler uso el método del descenso inventado por Fermat para demostrar que las únicas soluciones de
Y = X + 1
son las "obvias": (-1,0), (0,1) y (2,3).Lebesque (1869):
Usando que si una ecuación con coeficientes enteros tiene solución entonces la tiene módulo
p para todos los primos p, Lebesque consiguió demostrar que la ecuación
Y = X + 7
no tiene ninguna solución entera.Nagell (1930)
T.Nagell demostró que la ecuación
Y = X + 17
tiene exactamente 8 soluciones con la Y positiva. Las soluciones son :
(-2, 3) , (-1, 4) , (2, 5) , (4, 9) , (8, 23) , (43, 282) , (52, 375) , (5234, 378661) .
 Podemos ver que en cada uno de los casos el número de soluciones es finito. Esta observación es de hecho un teorema muy profundo (y difícil de demostrar!) de Thue
Teorema (Thue 1917) Dado k, solo existen un número finito de soluciones enteras de la ecuación de Bachet Y = X + k.
El problema con este teorema es que no nos responde las preguntas:
Existe alguna "formula" que nos diga, dado k, cuantas soluciones tiene la ecuación?
Existe algún método para encontrarlas todas?
Baker, en 1966, dio un criterio que nos permite en principio encontrar todas las soluciones:
 Si (x,y) es una solución de la ecuación Y = X + k entonces
|x| < exp(1010|k|)10000
Podemos así en teoría, dado k, ir probando todos los x's que verifican la desigualdad y así
encontraremos todas la soluciones. Pero la verdad es que este método no es muy práctico, además de que la cota no es demasiado buena (como mínimo para k pequeños). Por ejemplo, se sabe que para todos los k desde 1 hasta 100 tenemos que |x|<10000. El caso mayor es para k=24 que tenemos la solución (8158, 736844) (y 3 soluciones más pequeñas!).Para valores de k entre 1 y 100 se saben cuales son todas las soluciones (resuelto definitivamente por O. Hemer, "Notes on the Diophantine equation y - k=x ", Arkiv för Matematik, volumen 3, paginas 67-77 (1954)). También se conocen para todos los valores de k entre -100 y -1 (véase el articulo de W. J. Ellison, F. Ellison, J. Pesek, C. E. Stahl y D. S. Stall, "The Diophantine equation y - k=x", en J. Number Theory, vol 4 (1972), paginas 107-117.).
Ahora ya podemos responder la pregunta del título de la página para valores de k pequeños:
los números naturales menores que 100 que no son resta de un cuadrado menos un cubo son exactamente:  k=6, 7, 11, 13, 14, 20, 21, 23, 29, 32, 34, 39, 42, 45, 46, 47, 51, 53, 58, 59, 60, 61, 62, 66, 67, 69, 70, 74, 75, 77, 78, 83, 84, 85, 86, 87, 88, 90, 93, 95, 96.

Finalmente, puedo decir que usando las técnicas introducidas por Mordell uno se reduce a resolver unas ciertas ecuaciones, llamadas de Thue, y que para estas ecuaciones se tiene un método que permite resolverlas en un número no muy largo de pasos (si k no es muy grande).
Véase por ejemplo el articulo de J. Gebel,  A. Pethö, y H. Zimmer, "On Mordell's equation",
en Compositio Math. vol. 110 (1998), no. 3, paginas 335-367.

Un libro donde se hace un recuento de todo lo que se sabia hasta 1969 es el de L.J. Mordell, Diophantine equations, Academic Press 1969. En castellano se puede consultar el libro de Alan Baker "Breve introducción a la teoría de números" publicado por Alianza Universidad.


El postulado de Bertrand


Para todo número natural n , siempre existe un número primo  p mayor que n
y menor que 2n
Los números primos son los componentes fundamentales de todos los números enteros,   así como los átomos lo son de la materia. De este modo, el estudio de los números primos es fundamental para entender a fondo las propiedades de los números naturales. Recordemos que un número p es primo si sus únicos divisores son él mismo y 1. Se tiene que todo número natural se expresa como producto de números primos (de forma única salvo permutaciones).
La pregunta más básica que podemos hacernos sobre los números primos es: ¿cuantos números primos hay?
Una primera respuesta a la pregunta podría ser: hay infinitos.
En efecto, tal como nos explico Euclides ya hace muchos siglos, si tenemos un número n finito de primos, digamos p1,p2,p3,... ,pn ,entonces N=p1.p2.p3...pn+1 no es divisible por ninguno de ellos (¿por que?), con lo cual existe algún otro primo.
Por cierto que de este argumento deducimos que, si denotamos por pn el enésimo número primo por orden creciente (p1=2, p2=3, p3=5,...), entonces para algún m>n, pm divide a  p1.p2.p3...pn+1, de donde se deduce por inducción que pn<2n (Ejercicio!). Este es un primer resultado sobre cual es el tamaño del primo enésimo.

Otra posible respuesta podría ser responder a la pregunta: ¿cuantos números primos hay menores que un número dado?
Esto es lo que nos dice el teorema fundamental de los números primos: el número de primos menores o iguales que x es asintóticamente igual a  x/log(x).
Este resultado, conjeturado por A.M.Legendre y  C.F. Gauss, fue demostrado por J. Hadamard y (de forma independiente) por  C. de la Vallée Poussin en 1896 utilizando métodos de análisis complejo. En 1949 P. Ërdos y A. Selberg encontraron una demostración que usa "solo" resultados de teoría de números y un poco de análisis real.
De este resultado se deduce que pn es aproximadamente igual a n·log(n) si n es muy grande.
Para ver un comentario sobre este resultado mirar aquí (en castellano) o bien aquí (en ingles y mucho más completo).
 

Aun otra posibilidad seria preguntarnos como están distribuidos los números primos dentro de los números reales. Por ejemplo:  si damos dos números naturales n y m, ¿cuando podemos asegurar que existe un número primo entre ellos dos?
Una primera respuesta a este problema nos la da el postulado de Bertrand: En 1845 el matemático francés Joseph Bertrand verificó que para cada entero n entre 2 y 6,000,000 existe siempre como mínimo un primo entre n y 2n.
Este resultado pero para todo número n fue demostrado por primera vez por el matemático ruso P.L. Chebychev en 1851.
Vamos a dar una demostración "elemental" de este postulado, o sea una demostración donde se usan solo resultados "elementales" de matemáticas. Esta demostración es debida a P. Ërdos, uno de los matemáticos mas geniales de este siglo, que la descubrió cuando tenia solo 18 años.
Necesitaremos primero recordar algunos resultados sobre números combinatorios.
Números combinatorios
Ahora ya estamos preparados para ver la demostración del postulado de Bertrand:

El postulado de Bertrand (llamado también el teorema de Chebichev):    Para todo número natural n>1 siempre existe un número primo p mayor que n y menor que 2n.
 
La demostración se divide en varias partes, y se basa en un estudio bastante delicado de algunos números combinatorios. Usaremos la letra p para denotar a un número primo. Dado un número natural n y un número primo p, la máxima potencia de p que divide a n la llamaremos la valoración p-ádica de n y la denotaremos vp(n).
 
Primera parte:  Los números combinatorios C(2m+1,m)
 Vamos a considerar el coeficiente binomial C(2m+1,m) , que llamaremos M, o sea
M=C(2m+1,m)=(2m+1)= (2m+1)! 
mm!(m+1)!
Sea p un número primo tal que m+1 < p <= 2m+1. Entonces p divide al numerador de M pero no al denominador, por lo tanto p divide a M. Por lo tanto el producto de todos estos primos divide a M, y tenemos que

P p  <= M
m+1<p<=2m+1


Por otra parte, la expansión binomial de (1 + 1)2m+1 tiene dos términos iguales a M, C(2m+1,m) y C(2m+1,m), así 2M <22m+1 y por lo tanto M < 22m, de donde tenemos

P p  < 22m
m+1<p<=2m+1


Segunda parte:  Acotación del producto de todos los primos menores que n.
Vamos a deducir del resultado anterior el siguiente
Teorema:
 Para todo número natural n se verifica que 
<font face="symbol"><font size="+3">P</font></font> p  22n
p<=n


Demostración:
Vamos a demostrarlo por inducción sobre n.
Para n=2 tenemos que
P p = 2  24=16
p<=2


y para n=3 tenemos que
P p = 2·3 = 6  26=64
p<=3


que son ciertas claramente.
Supongamos ahora que hemos visto la desigualdad para todo número menor que n y vamos a demostrarla para n.
Si n es par y mayor que 2, entonces n no es primo (ya que es divisible por 2) y por lo tanto
P p= P p <22(n-1) < 22n
p<=n
p<=n-1


Si n es impar, sea n = 2m + 1. Por la formula demostrada arriba tenemos que
P p 22m
m+1<p<=2m+1


y por lo tanto
P p= P p  P p 22(m+1)22m=24m+2
p<=n
p<=m+1
m+1<p<=2m+1


donde hemos aplicado que por inducción sabemos el resultado para m+1.Por otra parte tenemos que
22n = 24m + 2
y por lo tanto la desigualdad buscada.
Vamos a usar este resultado para demostrar el postulado de Bertrand por reducción al absurdo. Pero aún nos falta estudiar otro número combinatorio en detalle.
Tercer paso: El número combinatorio C(2n,n).
Vamos a encontrar una acotación inferior para el número combinatorio C(2n,n). Del binomio de Newton tenemos que
22n =2+C(2n,1)+C(2n,2)+... +C(2n,2n-1),
donde hemos agrupado el primer y ultimo término (cada uno de ellos igual a 1) en el primer 2. Dado que C(2n,m)<C(2n,n) para todo m diferente de n (y que 2<C(2n,n)), tenemos que
22n <2nC(2n,n),
ya que hay 2n sumandos en la fórmula anterior.
Último paso: La demostración del postulado de Bertrand (por Ërdos)
Por reducción al absurdo. Supongamos que exista un número n tal que no hay ningún número primo mayor que n y menor que 2n. Consideremos el número
N=C(2n,n)=(2n)= (2n)! 
n(n!)2
Los números primos mayores que n y menores que 2n dividen el numerador pero no el denominador, por lo tanto dividen a N. Dado que por hipótesis no hay tales primos, ningún primo mayor  que n divide a N.Vamos a demostrar que de hecho ningún primo mayor que (2/3)n divide a N (este es, según Ërdos, el punto clave de la demostración).
Efectivamente, supongamos que tenemos p>2 un número primo cumpliendo que
2n/3 < p < n
Entonces, multiplicando por 2 tenemos que
n < 4n/3 < 2p < 2n
y multiplicando por 3 tenemos que
2n=6n/3 < 3p
Por lo tanto p divide a n! y p2 no divide a n!, mientras que p2 divide a (2n)!  y p3 no divide a (2n)!. Así que la valoración p-ádica de (n!)2 y de (2n)! es la misma, de donde p no divide a N.
(Obsérvese que la condición p>2 es cierta si n>4, cosa que supondremos a partir de ahora ya que hasta n=4 si que se cumple el postulado de Bertrand).Vamos a dar una acotación para la valoración p-ádica de N, vp(N), válida para todo primo p. Tenemos que
vp(N)=vp((2n)!)-2vp(n!) = S([2n/pr]-2[n/pr])


r>0
usando la fórmula que encontramos en la sección de números combinatorios.
Observemos que para todo número real x se tiene que [2x]-2[x] es igual a 0 o a 1 (dependiendo de si la parte fraccionaria de x es menor o mayor que 0.5), por lo tanto
vp(N) es igual al número de sumandos no cero del sumatorio. Dado que si pr>2n entonces
tanto [2n/pr] como [n/pr] valen 0, tenemos que como mucho hay log(2n)/log(p) sumandos.
Como el número de sumandos es un número entero (evidentemente!), obtenemos
vp(N) < [log(2n)/log(p)]
válida para todo primo p.
 El siguiente paso de la demostración es ver que
Si  p> raiz (2n), entonces vp(N) = 0 o vp(N) = 1.
Efectivamente, si p> raiz (2n), entonces  log(p)>log(2n)/2, y por lo tanto log(2n)/log(p)<2.
De la fórmula anterior tenemos que
vp(N) < [log(2n)/log(p)]<2
Por otra parte, usando la misma fórmula podemos encontrar una acotación para pv
si v denota a vp(N). En efecto
p< plog(2n)/log(p) = 2n
por la definición del logaritmo (usar por ejemplo que log(2n)/log(p)=logp(2n) donde
loges el logaritmo en base p).
Bueno, respiremos un momento antes de subir la última cuesta que nos llevará a la cima.Vamos a dividir N como el producto de los primos hasta raiz (2n) y los primos de raiz (2n) hasta
(2/3)n. Sabemos que no hay más por hipótesis.

N=P pvp = (P pvp)(P pvp) <(P 2n )(P p)<(2n)raiz(2n)·2(4/3)n

p<=2n


p<=  (2n)


 (2n)<p<=(2/3)n 



p<= (2n)


p<=(2/3)n



Usamos el símbolo vp para denotar la valoración p-ádica de N, y hemos usado todos los resultados anteriores.
Por otra parte sabemos por el tercer paso que
22n /(2n) < N ,
de donde obtenemos que
22n /(2n) < N <(2n)raiz (2n)·2(4/3)n .
Vamos a deducir una contradicción de este hecho, con lo cual la hipótesis inicial no será cierta. La desigualdad anterior es equivalente a
2(2n/3)=2(2/3)n  < (2n)(raiz (2n) + 1).
Vamos a ver que esta desigualdad no es cierta si n>967.
En efecto, tomando logaritmos en la desigualdad obtenemos
(2n/3) log(2) < (raiz (2n) + 1) log(2n)
Llamemos x=raiz (2n). Entonces tenemos la desigualdad
(x2/3) log(2) < (x + 1) log(x2)
y por lo tanto
x2 < (6/log(2))(x + 1) log(x)<(6/log(2))(2x)log(x)=(8/log(2))(x log(x))
o sea
x <(8/log(2))  log(x)
Consideremos la función
f(x)=x-(8/log(2)) log(x)
Su derivada es
f'(x)=1-(8/log(2)) (1/x)
que vale cero solo cuando x=(8/log(2)), siendo positiva si x>(8/log(2)). Por lo tanto f(x) es creciente a partir de (8/log(2)). Dado que f(44)=.32454705>0, f(x)>0 si x>=44. Por lo tanto
la desigualdad se cumple solo si x<44, o sea si n < (44)2/2 = 968.
Conclusión: Si n>969, entonces existe un número primo mayor que n y menor que 2n.¿Y si n<=968? Entonces esta claro que se cumple el postulado de Bertrand. Por ejemplo,
considerando los números primos:
2, 3, 5, 7, 13, 23, 43, 83, 163, 317, 521, 1039
que tienen la propiedad que cada uno es mayor que el antecesor pero menor que su doble.
Fin de la demostración
Comentario:  Este argumento se puede modificar para dar la demostración del Teorema de J.J.Sylvester : Para todo n>1 y para todo k menor o igual que n/2 se verifica que existe un primo mayor que k que divide a C(n,k). (Este resultado generaliza claramente el postulado de Bertrand).

Ejercicio Final: Demostrar (usando el postulado de Bertrand si se quiere) que n! nunca puede ser un cuadrado.

La conjetura de Catalan

 
Si a,b,c y d son enteros mayores que uno y 
ab=cd+1 
entonces a=3, b=2, c=2 y d=3. 
La conjetura de Catalan cuando a y c solo toman los valores 2 y 3
Demostración de Levi ben Gershom, también conocido como Gersonides (1288-1344), en 1342.Fijamos base a=2 y c=3.  Así nos preguntamos cuales son los números enteros x e y tales que
2x=3y+1
Consideremos la ecuación modulo 8. Entones tenemos que
2x= 2 (mod 8) si x=1
2x= 4 (mod 8) si x=2
2x= 0 (mod 8) si x>2
y que
3y= 3 (mod 8) si y es impar.
3y= 1 (mod 8) si y es par.
Por lo tanto tenemos que

{4 si y es impar 
2x=3y+1=

2 si y es par
con lo cual solo podemos tener solución si x=1 y si x=2. Así obtenemos las soluciones
x=1, y=0, y x=2, y=1.Ahora fijamos la base a=3 y c=2. Se trata así de resolver la ecuación
2x=3y-1
Como antes obtenemos que

{2 si y es impar 
2x=3y-1=

0 si y es par
Así, para y impar solo hay la solución x=1, y por lo tanto y=1.
Pero para y par no podemos usar este argumento. Lo que haremos es lo siguiente:
como x es par podemos escribir y=2k para cierto entero k. Entonces tenemos
2x=32k-1=(3k-1)(3k+1)
Aha! Cada uno de los factores tiene que ser una potencia de 2! Por lo tanto
2r=3k+1
para cierta r. Pero esta ecuación ya la hemos resuelto antes y solo tiene solución para k=0 y 1,
o sea que la ecuación original solo puede tener solución para y=0 y y=2. Pero para x=0 no tiene solución así que la única solución es x=3 y y=2:
23=32-1.
La conjetura de Catalan cuando b y d solo toman los valores 2 y 3
Dicho de otro modo: se trata de demostrar que si la diferencia entre un cuadrado y un cubo es igual a 1 o a -1, entonces estos números son 9 y 8.Parece ser que el primero que conjeturo este resultado fue P. Fermat. En 1738, L. Euler demostró este resultado basandose en el método del descenso inventado por Fermat.
 
 
  
Eugène Charles Catalan (1844)
En 1844, el matemático belga E.C. Catalan conjeturó la conjetura que ahora conocemos por su nombre: las únicas potencias consecutivas son el 8 y el 9. Catalan publicó sobretodo resultados sobre fracciones continuas y en teoría de números algebraica. 
Por lo que yo se, Catalan solo demostró el caso particular de la ecuación en que b=c y d=a, o sea la ecuación

xy-yx=1
Vamos a ver que la única solución en enteros positivos de esta ecuación es x=3 y y=2.
Consideremos primero el caso x=1; la ecuación se convierte en 1-y=1, cuya única solución es y=0.

Si x=2, tenemos la ecuación  2y-y2=1. Observemos, gracias a la formula del binomio de Newton,
2y=(1+1)y=1+y+y(y-1)/2+....+y(y-1)/2+y+1>2+2y+y(y-1)=2+y+y2
si y>3. Substituyendo en la ecuación obtenemos que 
1=2y-y2  >  2+y+y2-y2=2+y > 2
Así tenemos que la única posibilidad es y=3.

Vamos a ver ahora que si  xy-yx=1 y x>=3, entonces y>x. En efecto, veamos que  xy-yx>0 solo si y>x. O sea que  xy>yx si y>x. Tomando logaritmos a ambos lados de la desigualdad, obtenemos que y·ln(x)>x·ln(y) y por lo tanto que y/ln(y)>x/ln(x). Si consideramos la función f(x)= x/ln(x), tenemos que la función es creciente si x>e  (e denota el número e, base de los logaritmos neperianos). Para demostrarlo, tomemos su derivada 
f'(x)=(1/ln(x))·(1-1/ln(x)); 
es mayor que cero siempre que 1-1/ln(x)>0, o sea si ln(x)>1, y por lo tanto si x>e. Dado que la función es creciente, si y>x>e tenemos que  xy-yx>0.
Finalmente vamos a demostrar que si x>=3, entonces  xy>yx+1. Dado que y>x, entonces y-x>=1. Llamaremos z=y-x. Tenemos las siguientes igualdades: 
 xy= xy-x= xz= xz
 yx (y/x)x(1+z/x)x((1+z/x)x/z)z

Vamos a usar ahora un resultado que dejamos como ejercicio de análisis para el lector: si t es cualquier numero real mayor que uno, tenemos que 
(1+1/t)t<e
Usaremos este resultado para t=x/z en la igualdad anterior. Obtenemos así que 
 xy> xz> 3z>3
 yx ezeze
Por otra parte, tenemos que 
1+1/yx < 1+1/xx < 1+1/33 = 1+1/27 = 1,037 < 1,1 < (3/e)
Al final tenemos que 
xy/yx>1+1/yx
de donde obtenemos la desigualdad buscada. 


El teorema de Tijdeman (1976)
 
En 1976, Tijdeman demostró, basandose en resultado previos de Baker, un teorema que convertia la canjetura de Catalan en un problema casi resuelto:
 
Teorema:Existe un número C (efectivamente computable) tal que si x, y, m, n son números naturales cumpliendo que xm-yn=1, entonces   xm, yn < C.
 
Este resultado implica claramente que el número de soluciones (a,b,c,d) de la ecuación de Catalan es finito.
Además, calculando la constante C y sustituyendo todos los posibles a,b,c y d, deberíamos poder ver si realmente hay alguna otra solución. El problema es que hasta ahora el mejor resultado que se tiene sobre la constante que aparece en el teorema es demasiado grande.
Por ejemplo, se sabe que si m y n son números primos (claramente nos podemos reducir
a este caso), digamos p y q, y si x e y son solución de la ecuación   xp-yq=1, entonces
max{p,q}<1.06 1026
min{p,q}<1.31 1019
max{x,y}<exp(exp(exp(exp(730))))
  El teorema de Mihailescu (2002)
  En Abril del año 2002, el matemático de origen rumanés Preda Mihailescu anunció que tenía una demostración de la conjetura de Catalan. Aunque el artículo aun no ha sido publicado, parece que de momento los expertos consideran que la demostración es válida. Esta se basa en el resultado de Tijdeman junto con acotaciones un poco más buenas de este resultado.

El resultado mas fuerte previo a este resultado era también de Mihailescu, del año 2000, cuando probó que si existía una solución de la ecuación de Catalan, entonces los exponentes tenían que ser primos dobles de Wieferich, o sea primos p y q tales que p
(q – 1) es congruente con 1 módulo q2, y q(p – 1) es congruente con 1 módulo p2.

En este articulo demuestra que también para estos primos el resultado es cierto. Además, usa la teoría de Iwasawa, que ha demostrado su potencia en algunos de los resultados mas fuertes obtenidos últimamente en la teoría de números algebraica.

Para consultar más información de este resultado se puede mirar la pagina personal de Mihailescu:
http://www-math.uni-paderborn.de/~preda/
o bien un preprint de Y.F. Biluhttp://www.ufr-mi.u-bordeaux.fr/~yuri/


Aritmética Modular: Congruencias

 
Las congruencias fueron introducidas formalmente por K. F. Gauss en su obra Disquisitiones Arithmeticae para estudiar problemas aritméticos relacionados con la divisibilidad, aunque posteriormente se han aplicado a muchos de los problemas de la teoría de números.Sean a y  b números enteros  y m>0 un número natural. Diremos que a y b son congruentes modulo m si m divide a a-b, y lo designaremos como
a=b (mod m).
Por ejemplo, los números que son congruentes a 0 módulo m son exactamente los múltiplos de m. La congruencia es una relación de equivalencia, puesto que verifica las propiedades reflexiva
a=a (mod m),
simétrica
a=b (mod m) si y solo si b=a (mod m),
y transitiva
a=b (mod m) y b=c (mod m), entonces a=c (mod m),
como se puede comprobar fácilmente.Así podemos agrupar los números enteros en familias disjuntas formadas por los números que son congruentes módulo m; obtenemos exactamente m familias, llamadas las clases de congruencia de m: son las familias de números congruentes con i módulo m variando i entre 0 y m-1.
Por ejemplo, las clases de congruencia módulo 2 son exactamente dos familias, la de los números pares y la de los números impares.
De la misma forma, hay exactamente 3 clases de congruencia módulo 3, formados por los números múltiplos de 3, los números múltiplos de 3 mas 1 y los números múltiplos de 3 mas 2 (o menos 1).
Designaremos por Z/mZ (zeta módulo m) las clases de congruencia módulo m; tenemos así, por ejemplo, que
 Z/3Z={ 0, 1, 2 }.
Las propiedades más importantes de las congruencias es que respetan la suma y la multiplicación de números enteros:
  • Si a=b (mod m) y c=d (mod m), entonces  a+c=b+d (mod m)
  • Si a=b (mod m) y c=d (mod m), entonces ac=bd (mod m)
(Ejercicio!).Por lo tanto podemos definir una suma y un producto en el conjunto Z/mZ, de forma que obtenemos un anillo: un conjunto con una operación suma que es un grupo conmutativo, una operación producto que es asociativa, con elemento neutro (el 1) y conmutativa, y que cumple la propiedad distributiva.
El primer problema importante a resolver es saber cuales  números tienen inverso respecto al producto módulo m y cuales no. Vamos a ver un ejemplo:
Supongamos m=6. Tenemos así que todo número entero es congruente a uno de los números siguientes: 0, 1, 2, 3, 4 y 5. Observemos que 2·3=6=0 (mod 6) y que 3·4 = 12 =0 (mod 6). Por otra parte 5·5=25=24+1=6·4+1=1 (mod 6). Tenemos así que 5 tiene inverso 5 módulo 6  (observando que 5 = -1 (mod 6) esta claro),  y en cambio 2, 3 y 4 no tienen inverso módulo 6.
El conjunto de invertibles módulo 6 es así {1,5} y el de no invertibles {0,2,3,4}; estos últimos son exactamente los que tienen algún factor común con 6 y los invertibles los que son primos con 6.
En general tenemos
Proposición: El conjunto de elementos de Z/mZ que tienen inverso por la multiplicación corresponde exactamente al conjunto de clases de congruencia de números que son primos con m.
Por ejemplo, para m=10 tenemos que los invertibles módulo 10 son {1, 3, 7, 9}; el inverso de
1 es 1, el inverso de 3 es 7  (ya que 3·7=21=1 (mod 10) ) y el inverso de 9 es 9.
No es difícil ver que si a es un elemento invertible módulo m, siempre existe un número natural r tal que ar=1 (mod m); el mínimo número natural r que verifica esta propiedad se llama el orden de a módulo m.
Por ejemplo, si m= 20, y a=17, si tiene que
17 = -3 (mod 20)
172=(-3)2=9 (mod 20)
173=(-3)3=-27=-7=13 (mod 20)
174=(-3)4=92=81=1 (mod 20)
de forma que el orden de 17 módulo 20 es 4.
En efecto, dado que el conjunto de elementos invertibles módulo m forma un grupo respecto la multiplicación, si denotamos por f(n) el número de elementos de este conjunto, entonces podemos tomar r=f(n). Tenemos queTeorema (Fermat-Euler)  Si m>0 es un número natural, sea f(n) es la cantidad de números naturales entre 0 y m que son primos con m:
f(n):={ 0<a<n   |   a es primo con m }.
Entonces para todo número entero a primo con m se tiene que
af(n)=1 (mod m).
Por ejemplo tenemos que si p es un número primo f(p)=p-1, ya que todos los números entre 1 y p-1 son primos con p.
Ejemplo:  3= 729 = 7 · 104 + 1 = 1 (mod 7)
En general se tiene queTeorema:  Sea m un número natural. Entonces
f(m)= m · P {p primo que divide a m} (1-1/p).
Por ejemplo,
f(30)= 30 · (1-1/2) (1-1/3) (1-1/5) = 15 · (1-1/3) · (1-1/5) = 10 · (1-1/5) =  8
y, efectivamente, hay 8 números entre 0 y 30 primos con 30: 1, 7, 11, 13, 17, 19, 23, 29.
Además tenemos que
18=1 (mod 30) ,  78=5764801= 192160·30+1=1 (mod 30) ,
11= 214358881 = 7145296 · 30 +1 =1  (mod 30) ,
138=815730720 = 27191024·30 + 1= 1 (mod 30) ,
178=6975757440 = 232525248·30 + 1 = 1  (mod 30) ,
198=16983563040 = 566118768·30+1=1 (mod 30),
238=78310985280 = 2610366176·30+1=1 (mod 30),
298=(-1)8 = 1 (mod 30),
Finalmente tenemos una propiedad muy importante de la función f(n).
Propiedad: Si n y m son dos números enteros primos entre si, entonces f(n·m)=f(n)·f(m).
Por ejemplo, si queremos calcular f(35), dado que 35=7·5, tenemos que
f(35)=f(7)·f(5)=6·4=24
(recordando que f(p)=p-1 si p es un número primo).

Vamos a ver alguna aplicación rápida de las congruencias. Por ejemplo, vamos a demostrar que un número es divisible por 9 si y solo si la suma de sus cifras decimales es divisible entre 9.
Recordemos primero que un número n es divisible entre 9 si y solo si
n=0 (mod 9)
Las cifras decimales de n son los números n0, n1, ..., nr entre 0 y 9 tales que
n = n0 + 10 · n1 + ... + 10r · nr
Dado que
10 = 1 (mod 9)
tenemos que
10= 1 (mod 9)
y por lo tanto
n =  n0 +  n1 + ... +  n(mod 9)
tal como queríamos ver.
Para finalizar, os propongo un par de ejercicios para resolver usando los resultados anteriores. El primero no es difícil (tenéis que usar el teorema de Fermat-Euler). El segundo es mucho más difícil. Si me mandáis una solución y me gusta la pondré en esta pagina.
  • Calcular las dos ultimas cifras de 13162.
  • Demostrar que un numero n es primo si y solo si (n-1)! =-1 (mod n).

Fuente:  http://usuarios.multimania.es/teoriadenumeros/

No hay comentarios:

Publicar un comentario en la entrada