Porque todo tiende a infinito…
En los últimos días se ha nombrado en los comentarios del post Una posible demostración maravillosa del UTF un resultado conocido como regla de los signos de Descartes, relacionado con el número de soluciones positivas de una ecuación polinómica. Este artículo va a servir para presentar esta regla, dar alguna pincelada de su historia y también para demostrarla.
(Leer el resto del post)
El lunes pasado, en el post donde se desarrollaba un método para resolver ecuaciones diofánticas lineales, comentábamos la existencia de un método para el cálculo del máximo común divisor que no desarrollamos. Dicho método se atribuye a Euclides y este post va a servir para presentarlo.
El problema inicial es el siguiente:
Encontrar el máximo común divisor entre dos números enteros positivos
y
.
Todos conocemos el método que se nos enseña en el colegio para ello:
Aunque es un método bastante útil y sencillo para conseguirlo que queremos tiene un evidente problema: si los números son muy grandes, o si sus factores primos lo son, la cosa se complica ya que el cálculo de la descomposición se torna bastante tedioso.
Por ello es interesante tener a mano otro método para casos en los que el procedimiento inicial se complique. El llamado algoritmo de Euclides nos servirá.
El algoritmo de Euclides nos dice lo siguiente:
Para calcular el máximo común divisor entre dos números enteros positivos
, y un resto,
. Si
, entonces
. Si no es cero dividimos el divisor,
, y otro resto,
. Si
, entonces
. Si no es cero volvemos a dividir divisor entre resto. Y así sucesivamente.
Esto es, el máximo común divisor entre
Si analizamos el algoritmo de Euclides se ve claramente que necesitamos demostrar que el máximo común divisor entre
Teorema:
y , con 
, coincide con el máximo común divisor de y 
, siendo el resto que se obtiene al dividir entre .Demostración:
Sean 
Por definición de máximo común divisor, se tiene que 
Por otro lado, por el algoritmo de la división se tiene que
de donde llegamos a
Por tanto 
Por otro lado, 
Por tanto
Como 
En esta sección del artículo vamos a ver un par de ejemplos de aplicación del algoritmo de Euclides. Vamos con ellos:
Cálculo de
Como hemos explicado antes dividimos el número mayor entre el menor; si el resto no es cero dividimos el divisor entre el resto; y así sucesivamente hasta que llegamos a un punto en el que el resto es cero. Los resultado de las divisiones (expresados como dividendo=divisor · cociente + resto) son:
*
Como marca el *, se tiene que 
Cálculo de
Vamos con el segundo ejemplo, con números más grandes en este caso. Expresamos los resultados parciales de la misma forma que en el ejemplo anterior:
*
Vemos que aunque los números son bastante mayores que los anteriores el número de operaciones necesarias para el cálculo es el mismo. Concluyendo, tenemos que, como marca el *, 
Este artículo ha sido promovido en Menéame. Si te ha gustado y quieres votarlo entra aquí y menéalo.
Supongamos que nos encontramos el siguiente problema:
Un hombre va a una tienda de ropa y compra 12 trajes, unos negros y otros grises, por 1200 €. Si los trajes negros valen 30 € más que los grises y ha comprado el mínimo posible de estos últimos, ¿cuántos trajes ha comprado de cada color?
Vamos a plantearlo:
La ecuación queda:
Haciendo cuentas nos queda lo siguiente:
Si estabais pensando que nos iba a quedar un sistema de ecuaciones sencillo de resolver estáis equivocados. Nos ha quedado una única ecuación con dos incógnitas. ¿Nos faltan datos? No. Podemos resolverla. Bienvenidos al maravilloso mundo de las ecuaciones diofánticas.
(Leer el resto del post)
Gracias a Tito Eliatron por la información que me envió sobre este tema hace ya un tiempo.
Recién terminada la Semana Santa planteo la siguiente pregunta: ¿sabéis qué criterio se sigue para asignar la fecha del Domingo de Resurrección cada año?
Yo me he hecho esa pregunta en más de una ocasión viendo que la variedad de fechas para ese día es relativamente grande. ¿Hay algún criterio para asignar fecha a ese día? En el caso de que lo haya (que por otra parte era lo más lógico), ¿en qué se basa ese criterio? ¿Su base es meramente religiosa o hay algo más?
Pues parece que hay algo más. Y, cómo no, lo que hay son matemáticas. Sí, matemáticas, aquí también están. Veámoslo.
A principios del siglo IV habían surgido varios grupos que calculaban a su manera la fecha del día de la Pascua de Resurrección. No había consenso, cada uno de ellos daba una fecha distinta, por lo que la confusión que rodeaba este asunto era grande. En el Concilio de Arlés (año 314) se obligó a todos los cristianos a celebrar la Pascua el mismo día (que sería fijado por el Papa), aunque no todos los grupos estuvieron de acuerdo en ello. Fue en el año 325, en el Concilio de Nicea, donde se alcanzó un principio de acuerdo.
Las normas que debía cumplir el día de Pascua de Resurrección eran las siguientes:
Pero con todo esto seguía habiendo diferencias entre la iglesia de Roma y la iglesia de Alejandría (principalmente relacionadas con el equinoccio de primavera y el cálculo de la edad de la Luna).
La solución final no llegó hasta el año 525, en el que Dionisio el Exiguo (cuyo nombre proviene de su pequeña estatura) sentó las bases del cálculo de la fecha de Pascua (que eran las del método alejandrino). Las premisas iniciales del método son las siguientes:
Con estas condiciones la Pascua quedaba encuadrada entre el 22 de marzo y el 25 de abril.
Durante el Renacimiento se construyeron tablas de cálculo para esta fecha, algunas de ellas relacionadas con el número aúreo. En la actualidad el método más sencillo para realizar este cálculo se debe a nuestro admirado Gauss.
Como hemos dicho antes, el método más sencillo para el cálculo de esta fecha se lo debemos a quien da nombre a este blog, Carl Friedrich Gauss (como podéis consultar en el extra que encontraréis más adelante, éste no es el método oficial, pero siempre da el mismo resultado). La base del mismo es la aritmética modular. Vamos a explicar en qué consiste:
Definimos diez variables que denotamos así: 
es el resto de la división de entre 
, es decir, 
. es el resto de dividir entre 
, es decir, 
.
es el resto de la división de entre 
, esto es, 
.
es el resultado de redondear por defecto el resultado de la división de entre 
, es decir, 
.
es el resultado de redondear por defecto el resultado de la división de 
entre $25$, esto es, 
.
es el resultado de redondear por defecto el resultado de la división de entre , es decir, 
.
es el resto de la división de 
entre 
, esto es, 
.
es el resto de la división de 
entre , es decir, 
. es el resto de dividir 
entre , o lo que es lo mismo, 
.
es el resto de la división de 
entre , es decir, 
.Calculando el valor de cada una de las variables para el año en cuestión, la fecha del Domingo de Resurrección será la siguiente:
, la fecha de Pascua de Resurrección será el día 
de marzo.
, la fecha de Pascua de Resurrección será el día 
de abril.Para esta regla existen dos excepciones:
, entonces la Pascua será el 18 de abril.Para ejemplificar el método vamos a calcular la fecha del Domingo de Resurrección de este año 2009 (que como sabemos es el día 12 de abril).
Para el año
los valores de las variables son los siguientes (como los cálculos son sencillísimos os dejo a vosotros la comprobación):
Como
, entonces la fecha es el
de abril, como en realidad es.
Extra: Gracias a nuestro gran amigo fede (¡qué haría yo sin ti algunas veces!) os puedo ofrecer este formulario mediante el cual podréis calcular la fecha del Domingo de Resurrección que él mismo ha programado (utiliza javascript, por lo que si no lo tenéis activado igual no os funciona) a partir de la descripción del método que podéis ver en la fuente de la Wikipedia inglesa que aparece al final de este artículo (hay un par de retoques de diseño que son míos; se aceptan todo tipo de sugerencias y ayudas). Para utilizarlo simplemente tenéis que escribir las cuatro cifras del año del que queréis calcular la fecha del Domingo de Resurrección (siempre un año mayor que 1582) y automáticamente os aparecerá dicha fecha:
y Si nos fijamos en la descripción del método vemos que las variables $latgex k,p$ y
| Años | M | N |
| 1583-1699 | 22 | 2 |
| 1700-1799 | 23 | 3 |
| 1800-1899 | 23 | 4 |
| 1900-2099 | 24 | 5 |
| 2100-2199 | 24 | 6 |
| 2200-2299 | 25 | 0 |
Fuentes:
Esta entrada estaba programada hace un tiempo, razón por la cual no había visto que Tito Eliatron había publicado el método descrito aquí hace unos días. Os dejo el enlace a ese post:
El 4 y 5 de Julio de este año, se celebrará el V Encuentro Andaluz de matemáticas discreta, el cual este año está organizado por el departamento de matemáticas de la Universidad de Cádiz.
Las áreas tratadas durante el encuentro serán:
El V Encuentro Andaluz de Matemática Discreta se desarrollará en el Auditorio de Conferencias del nuevo Palacio de Congresos y Exposiciones de La Línea de la Concepción.
(Más información en web de la Universidad de Cádiz)
(Vía Genciencia)
El algoritmo fue descrito en 1977 por Ron Rivest, Adi Shamir y Len Adleman (la sigla RSA es Rivest Shamir Adleman) en el MIT.
El cifrado RSA es un algoritmo de cifrado de clave pública (o asimétrico) por bloques, que como todos los cifrados de clave pública tiene dos claves: una pública, que se distribuye a los usuarios que quiera el propietario de ella, y otra privada, la cual es guardada en secreto por su propietario. Así cuando se envía un mensaje, el emisor usa la clave pública de cifrado del receptor para cifrar el mensaje y una vez que dicho mensaje llega al receptor, éste se ocupa de descifrarlo usando su clave oculta.
El algoritmo sigue los siguientes pasos:
Una vez tenemos las claves podemos pasar a cifrar/descfirar los mensajes:
La seguridad de este algoritmo radica en que no hay maneras rápidas conocidas de factorizar un número grande en sus factores primos utilizando computadoras tradicionales.
Un cifrado de clave pública (o asimétrica), es aquel cifrado que se basa en el uso de una pareja de claves, pública y privada, de las cuales una se usa para cifrar y la otra para descifrar.
Ambas claves están relacionadas por una función trampa, suele ser una función matemática. Las claves se calculan usando la función y la inversa de ésta, siendo la función inversa la función trampa al ser muy difícil o imposible de calcular.
Función irreversible
x ∈ A, f(x) fácil de calcular
y ∈ f(A), x = f-1(y) difícil de calcular
Función trampa
x = f-1(y) Es calculable conociendo la trampa de la función. Pero sin conocer dicha trampa, y = f(x) es unidireccional.
Además la trampa sólo se puede calcular con la clave privada.
Es aquel cifrado que sustituye cada letra o grupo de letras por otra letra o grupo de letras distinta/s para cifrar el texto en claro.
Los primeros y antiguos métodos de cifrado se basaban en este principio, aunque en aquella época no eran muy robustos ni difíciles de descifrar, pero les resultaban muy útiles.
Ya que he acabado la serie de posts sobre la Teoría de Números Elemental, en este post os voy a poner los enlaces a todos los posts que he hecho sobre este tema, para que podáis tenerlos a mano.
Vamos a terminar ya con la teoría de números elemental, que se me está haciendo demasiado larga.
Los matemáticos Chinos de la antigüedad creían que:
n primo 2n-1 ≡ 1 (mod (n))
Sin embargo se equivocaron y su condición sólo es válida en un sentido:
n primo => 2n-1 ≡ 1 (mod (n))
A los números que sin ser primos, cumplen la propiedad se les conoce como pseudoprimos.
Sea “p” primo y a ∈ Z no divisible por “p”. Entonces,
ap-1 ≡ 1 (mod (p))
Como podéis ver no es más que una mejora de la propiedad de los números pseudoprimos.
 |  |
