Teoría de números elemental: Aritmética modular

Publicado por el 29 de septiembre de 2006 en Álgebra y Matemática discreta, Números enteros | 6 comentarios

Aritmética modular

Con las congruencias podemos establecer un conjunto de operaciones aritméticas, como:

Siendo a, b, c, d ∈ Z y m ∈ N, tales que a ≡ b (mod (m)) y c ≡ d (mod (m)). Entonces,

a + c ≡ b + d (mod (m))
a · c ≡ b · c (mod (m))

(Recordemos que el signo ≡ significa “congruente con” y no es lo mismo que el signo = que significa “igual a”)

A partir de esto, podemos definir las propiedades aritméticas para las sumas de congruencias:

  • Propiedad asociativa: a + (b + c) (mod (m)) = (a + b) + c (mod (m))
  • Elemento neutro: Existe un elemento 0 ∈ Zm, tal que a + 0 (mod (m)) = a (mod (m))
  • Elemento opuesto: Existe un elemento b ∈ Zm, tal que a + b = 0 (recordemos que 0 es el elemento neutro de la suma)
  • Propiedad conmutativa: a + b (mod (m)) = b + a (mod (m))

También podemos definir las propiedades aritméticas para el producto de congruencias:

  • Propiedad cancelativa: a · c ≡ b · c (mod (m)) y MCD (m, c) = 1, entonces a ≡ b (mod (m))
  • Propiedad asociativa: a · (b · c) (mod (m)) = (a · b) · c (mod (m))
  • Elemento neutro: Existe un elemento 1 ∈ Zm, tal que a · 1 (mod (m)) = a (mod (m))
  • Elemento inverso: Existe un elemento a-1 ∈ Zm para todo a ∈ Zm con MCD (a, m) = 1, tal que a · a-1 = 1 (recordemos que 1 es el elemento neutro del producto)

Además de todas estas propiedades también se cumple la propiedad distributiva: a · (b + c) (mod (m)) = (a · b) + (a · c) (mod (m))

(Más información en la Wikipedia)

Para acabar, os voy a dar unos ejemplos de usos de las congruencias:

  • En el DNI: La letra de tu NIF se realiza del siguiente modo: Número DNI (mod 23) y el resultado se pasa a una tabla que relaciona números con letras.
  • En la generación de números seudoaleatorios: Los números aleatorios que genera cualquier ordenador se calculan usando una sucesión basada en congruencias: Xn+1 = (a · Xn + c) (mod (m))
  • En criptografía: De este tema os hablaré dentro de poco, por ahora saber que las congruencias son la base de toda la criptografía moderna: RSA, El Gamal, …
Sigue leyendo

Sumatorio de enlaces I

Publicado por el 28 de septiembre de 2006 en Sumatorio de enlaces | 3 comentarios

Hoy voy a comenzar lo que probablemente será habitual poner cada cierto tiempo por algún gaussiano, y es lo que he llamado sumatorio de enlaces, un post que recoja unos cuantos enlaces que por algún motivo no son aptos para tener un post, ya sea por su poco contenido, estar tan bien explicados que no hace falta escribir nada más, o cualquier otro motivo semejante.

Así, que sin más dilación aquí viene el primer sumatorio de enlaces:

(Sumatorio de enlaces)

Sigue leyendo

La escoba en Zm

Publicado por el 28 de septiembre de 2006 en Juegos, Números enteros, Números primos | 7 comentarios

Hace un tiempo, exactamente en este comentario, dije que en mis primeros de carrera jugábamos a la Escoba en Zm. Este post va a servir para explicar cómo jugábamos.

La Escoba

Comencemos explicando qué es la Escoba (es decir, quien sepa jugar puede saltarse este punto y pasar al siguiente). La Escoba es un juego de cartas que se juega con la baraja española. Al comenzar el juego se reparten 3 cartas a cada jugador y se colocan 4 encima de la mesa. El valor de cada carta es el valor que marca su número, excepto para sota, caballo y rey que valen respectivamente 8, 9 y 10 puntos. El objetivo del juego es sumar 15 puntos con una de las cartas que tenemos en la mano y las cartas que creamos convenientes de las que hay en la mesa. Se juega por turnos. Si en alguno de nuestros turnos no podemos sumar 15 dejamos una de nuestras cartas en la mesa y pasamos el turno. Así hasta que terminan las cartas del mazo. Al final cada jugador cuenta sus puntos teniendo en cuenta que el que tenga más cartas suma 1 punto, el que tenga más oros suma otro, el que tenga más sietes suma otro y el que tenga el siete de oros suma otro. Si en algún momento conseguimos dejar la mesa sin cartas al sumar los 15 obtenemos una Escoba, que nos suma otro punto al final de la partida.

Espero haberme explicado más o menos bien. Si hay alguna duda echad un ojo al enlace que he puesto o preguntadlo en un comentario.

(Comentario: esas son las reglas de puntuación que he usado yo siempre; evidentemente cada persona tendrá su propia forma de puntuar. De hecho en el enlace que he puesto la puntuación es distinta. De todas formas eso no es importante ya que ahora se verá que la forma de puntuación de la Escoba en Zm es esencialmente distinta a todas ellas.)

La Escoba en Zm

La Escoba en Zm tiene las mismas reglas de juego que la Escoba normal. Donde cambia la cosa es en la forma de puntuar al final de cada partida. Quien tenga más oros se sigue llevando un punto, quien tenga más sietes otro y quien tenga el siete de oros otro. Cada Escoba conseguida sigue sumando también un punto. Lo que cambia es la forma de puntuar las cartas obtenidas. Como generalmente jugábamos 4 personas utilizaré ese ejemplo.

Lo primero de todo es saber qué es Zm. Este post de neok ayudará bastante. Suponiendo que ya sabemos de qué va el tema comenzamos:

Al comienzo de la partida se asigna un cierto Zm a cada jugador. Para seguir un orden se puede asignar Z2 al jugador que está a la derecha de quien reparte, Z3 al de su derecha, Z4 al siguiente y Z5 al último, al que reparte las cartas. Se juega la partida normal y al finalizar se cuentan las cartas de cada uno de los jugadores. Digamos que un jugador obtiene k cartas. La puntuación obtenida por ese jugador será k (mód m), siendo m el correspondiente al Zm que se le asignó al principio. Así se hace con todos los jugadores.

Evidentemente para que el juego sea totalmente justo hay que jugar tantas manos con jugadores haya (en nuestro caso 4 manos) y debe cumplirse que al finalizar esas manos todos los jugadores hayan jugado cada una de ellas con un Zm distinto.

Al finalizar cada mano se apuntan los puntos obtenidos por cada jugador y quien más tenga al finalizar todas las manos gana la partida.

Bueno, ¿qué cambia respecto al anterior método de puntuación?. Pues muy sencillo. Antes quien tenía más cartas al finalizar la mano se llevaba un punto. Ahora cabe la posibilidad de que quien tenga más cartas no se lleve ninguno. Veamos un ejemplo:

Jugador A: Z2
Jugador B: Z3
Jugador C: Z4
Jugador D: Z5

Supongamos que al finalizar la partida las cartas queden repartidas de la siguiente forma:

A: 15
B: 12
C: 8
D: 5

En este caso las puntuaciones son:

A: 1 [15 (mód 2) = 1]
B: 0 [12 (mód 3) = 0]
C: 0 [8 (mód 4) = 0]
D: 0 [5 (mód 5) = 0]

En este caso quien tenía más cartas puntúa y el resto no puntúa. Pero veamos este otro ejemplo:

A: 18
B: 10
C: 8
D: 4

Las puntuaciones quedarían así:

A: 0 [18 (mód 2) = 0]
B: 1 [10 (mód 3) = 1]
C: 0 [8 (mód 4) = 0]
D: 4 [4 (mód 5) = 4]

En este caso quien tiene más cartas no puntúa, y además el que saca más puntos es quien llevaba menos cartas.

Se debe cambiar de Zm en cada mano para todos los jugadores porque quien tenga el Zm más grande parte con ventaja, ya que es quien a priori puede conseguir la mayor puntuación (aunque ya hemos visto que no tiene por qué ser así). Y además se debe pedir que quien pueda hacer 15 esté obligado a hacerlo, es decir, no se puede pasar si se tienen posibilidades de hacer 15 en un turno. ¿Por qué?. Muy sencillo. Porque, por ejemplo, el jugador de Z5 puede ir contando las cartas que va obteniendo y, por ejemplo, pararse cuando lleva 9, pasando en todos los turnos siguientes. Así se asegura 4 puntos al finalizar la mano. Se pueden ir contando las cartas que vamos obteniendo para intentar sacar el número que nos interesa (por ejemplo, si tenemos varias opciones para hacer 15 en un turno podemos elegir la que más nos convenga), pero estamos obligados a hacer 15 si podemos.

Y creo que no me dejo nada. Al final de (en nuestro caso) las 4 manos sumamos los puntos de cada jugador en cada mano y quien tenga más puntos gana la partida.

Para hacerlo un poco más friki-matemático podemos jugar con los 4 primeros números primos: Z2, Z3, Z5 y Z7.

Espero haberme explicado bien y que os haya gustado el juego. Y ya sabéis, para cualquier duda, comentario, crítica o lo que queráis usad los comentarios a esta entrada.

Sigue leyendo
El polinomio de Shaw-Basho
Sep27

El polinomio de Shaw-Basho

Publicado por el 27 de septiembre de 2006 en Curiosidades | 53 comentarios

De casualidad me encuentro con el polinomio de Shaw-Basho. Su expresión es:

En principio no parece tener nada de especial, de hecho es un polinomio como otro cualquiera, pero tienes propiedades realmente interesantes.

Si lo evaluamos en 0, 1, 2 y en los números naturales posteriores obtenemos los siguientes resultados:

4, 12, 35, 89, 213, 511, 1194, 2622, 5346, 10150, 18093…

Nada especial en principio, ¿no?. Sigamos haciendo cuentas. Ahora vamos a escribir la secuencia que obtenemos al restar cada número menos el anterior:

8, 23, 54, 124, 298, 683, 1428, 2624, 4804, 7943…

Seguimos sin obtener nada aparentemente interesante. Volvamos a realizar la misma operación varias veces más. Curiosamente llegamos a una situación en la que obtenemos todo ceros. Aquí están las secuencias obtenidas:

SECUENCIA 1: 4, 12, 35, 89, 213, 511, 1194, 2622, 5346, 10150, 18093…
SECUENCIA 2: 8, 23, 54, 124, 298, 683, 1428, 2624, 4804, 7943, 12458…
SECUENCIA 3: 15, 31, 70, 174, 385, 745, 1296, 2080, 3139, 4515, 6250…
SECUENCIA 4: 16, 39, 104, 211, 360, 551, 784, 1059, 1376, 1735…
SECUENCIA 5: 23, 65, 107, 149, 191, 233, 275, 317, 359…
SECUENCIA 6: 42, 42, 42, 42, 42, 42, 42, 42, 42, 42…
SECUENCIA 7: 0, 0, 0, 0, 0, 0, 0…
SECUENCIA 8: 0, 0, 0, 0, 0, 0, 0…
SECUENCIA 9: 0, 0, 0, 0, 0, 0, 0…
SECUENCIA 10: 0, 0, 0, 0, 0, 0, 0…

Ahí lo tenemos, llega un momento en el que todos los números de la secuencia son ceros, y por tanto las siguientes también están formadas por ceros. Curioso, ¿verdad?.

Un momento, los números con los que comienzan las secuencias que no están formadas por ceros están en cursiva…uhmmm…¿Qué tienen de especial esos números?:

4, 8, 15, 16, 23, 42

¡¡Exacto!!. ¡¡Son los números de Lost!!. Absolutamente sorprendente…

Fuente: The Lost Sequence

Sigue leyendo

¿Cuánto vale cero elevado a cero? ¿Y cero factorial?

Publicado por el 26 de septiembre de 2006 en Aprenda como, Demostraciones, Números enteros | 354 comentarios

En nuestra época de colegio nos dicen que todo número elevado a cero vale uno, y también nos dicen que cero elevado a cualquier número vale cero, es decir:

\begin{matrix} a^0=1 \\0^b=0 \end{matrix}

Pero siguiendo estas dos afirmaciones nos encontramos con un problema:

¿Cuánto vale 0^0?

Según la primera de las afirmaciones valdría 1, pero según la segunda valdría 0. ¿Con cuál nos quedamos?.

Muchos diríais: 0^0 es indeterminación. Sí pero no. No, porque el caso que nos ocupa no es el de una función (sucesión) que tiende a 0 elevada a otra función (sucesión) que tiende también a 0. Es decir, no queremos calcular el límite de cualquier función que dé una indeterminación 0^0, sino que queremos saber cuál es el valor del número 0^0 (recalco esto porque es muy importante y suele llevar a errores: no es lo mismo un número que una función cuyo límite es ese número).

¿Cuál es la forma más coherente matemáticamente hablando para dar un valor a 0^0?. Pues a través de un límite. Sí, cierto, en el párrafo anterior he dicho que no estamos calculando cualquier límite que dé como indeterminación 0^0, pero no es eso lo que vamos a hacer. Vamos a utilizar una función concreta para encontrar ese valor. ¿Cuál?. Pues la más lógica: x^x. Vamos a calcular su límite cuando x tiende a 0. Lo haremos por el procedimiento normal: llamar A al límite y aplicar logaritmo a ambos lados de la igualdad. Utilizando después la regla de L’Hopital llegamos a la solución:

\displaystyle{\lim_{x \to 0} x^x=0^0=A}
\begin{matrix} \displaystyle{\log{A}=\lim_{x \to 0} \log{x^x}= \mbox{Propiedad de los logaritmos}=} \\ =\displaystyle{\lim_{x \to 0} x \cdot \log{x}=''0 \cdot (- \infty)} \end{matrix}

Tenemos otra indeterminación. Para resolverla pasamos xcomo \textstyle{\frac{1}{x}} al denominador y aplicamos la regla de L’Hopital en el paso *:

\begin{matrix} \displaystyle{\log{A}=\lim_{x \to 0} \frac{\log{x}}{\frac{1}{x}}=*=} \\ \displaystyle{\lim_{x \to 0} \frac{\frac{1}{x}}{\frac{-1}{x^2}}= \mbox{Operamos}=\lim_{x \to 0} (-x)=0} \end{matrix}

Tenemos entonces que \log{A}=0. Por tanto A=1

Es decir, el valor más coherente matemáticamente hablando (y por tanto el que se utiliza en los casos en los que es necesario) es:

0^0=1

Algo del estilo ocurre con 0!. Sabemos que n! = n \cdot (n - 1) \cdot (n - 2) \cdot \ldots \cdot 2 \cdot 1. Pero, ¿qué pasa con 0!?. Pues muy sencillo: 0! = 1. Al igual que en el caso anterior se utiliza este valor por convenio, pero la elección no es arbitraria. Podemos ver que es la elección más coherente con este razonamiento:

\begin{matrix} 4! = 3! \cdot 4 \rightarrow 3! = \frac{4!}{4} = 6 \\ 3! = 2! \cdot 3 \rightarrow 2! = \frac{3!}{3} = 2 \\ 2! = 1! \cdot 2 \rightarrow 1! = \frac{2!}{2} = 1 \\ 1! = 0! \cdot 1 \rightarrow 0! = \frac{1!}{1} = 1 \end{matrix}

Por tanto:

0!=1

Actualización: Leyendo los comentarios me doy cuenta de que igual no he explicado de la mejor manera posible lo que quería decir. Os acosejo que leáis los comentarios que he hecho explicando un poco más estos dos temas.

Sigue leyendo