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

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 ∈ Z_m, tal que a + 0 (mod (m)) = a (mod (m))
• Elemento opuesto: Existe un elemento b ∈ Z_m, 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 ∈ Z_m, tal que a · 1 (mod (m)) = a (mod (m))
• Elemento inverso: Existe un elemento a^-1 ∈ Z_m para todo a ∈ Z_m 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: X_n+1 = (a · X_n + 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, …

Autor: Fran | Publicado el 29 de September de 2006
Comments Off
Categorías: Matemáticas discreta, Números enteros

Teoría de números elemental: Congruencias

Después de mi parón por los examenes de Septiembre, aquí vuelvo para dar la puntilla definitiva a mi serie de posts sobre la teoría de números elemental. Así que aquí viene quizá lo más importante (en mi opinión) de la teoría de números elemental, las congruencias.

¿Qué es una congruencia?

Es una relación de equivalencia (no me quiero meter a explicar que es una relación de equivalencia, por eso os pongo el enlace) que cumple la siguiente propiedad:

Sean a, b ∈ Z, m ∈ N, entonces “a” y “b” son congruentes si:

a mod (m) = b mod (m) ó b – a = K·m (siendo K ∈ Z)

Cuando dos números son congruentes se denota de la siguiente manera:

a ≡ b (mod (m))

Definimos “mod” como la operación módulo, que es el resto de la división euclídea de dos números:

r = a mod (m) a = m·q + r

(Más información en Wikipedia)

Conjuntos cocientes

Como las congruencias son relaciones de equivalencia, se pueden definir para cada elemento del conjunto en el que se da la relación, las clases de equivalencia.

La clase de equivalencia de cualquier elemento “a” perteneciente al conjunto “A”, se define como el conjunto:

[a] = {b ∈ A : aRb} (donde R es la relación de equivalencia)

Aplicando esto a los números enteros y a las congruencias, tenemos que:

a ≡ b (mod (m)) en Z tiene como clases de equivalencia a:

[o] = {…., -2·m, -m, 0, m, 2·m, ….}
[1] = {…., 1-2·m, 1-m, 1, 1+m, 1+2m, ….}
….
[m-1] = {…., -1-m, -1, m-1, 2·m-1, 3·m-1, ….}

(Más información en Wikipedia)

Sabiendo ya que son las clases de equivalencia, podemos pasar a explicar qué son los conjuntos cocientes. El conjunto cociente de A por R, se denota A/R, es el conjunto cuyos elementos son las clases de equivalencia por R de los elementos de A, es decir:

A/R = {[a] : a ∈ A}

Aplicando esto a los números enteros y a las congruencias, tenemos que:

Siendo a ≡ b (mod (m)) y sus clases de equivalencia [0], [1], …, [m-1], su conjunto cociente es:

Z_m = {[0], [1], …, [m-1]} [Para los números enteros y las congruencias se denota Z_m en lugar de Z/(mod (m))]

(Más información en Wikipedia)

—

Aunque no quería meterme demasiado en el tema de las relaciones de equivalencia, he tenido que explicar que son las clases de equivalencia y conjuntos cocientes sin haber explicado antes nada de relaciones de equivalencia ni de relaciones binarias, lo he hecho lo más sencillo posible y orientado a las congruencias en lugar de a cualquier relación, así que espero que lo entendáis bien, de todos modos ahí tenéis los comentarios para exponer vuestras dudas.

Autor: Fran | Publicado el 21 de September de 2006
Comments Off
Categorías: Matemáticas discreta, Números enteros

Teoría de números elemental: Primos relativos

¿Qué son los primos relativos (o coprimos)?

Sean a, b ∈ Z, se dice que son primos relativos (o coprimos) “a” y “b” si no tienen ningún factor primo en común, es decir, si no tienen otro divisor común más que 1 ó -1, o cumplen que el mcd (a, b) = 1.

(Más información en Wikipedia)

Teorema de la identidad de Bézout

Sean a, b ∈ Z con d=mcd (a, b), entonces existen x, y ∈ Z tales que ax + by = d. En particular si “a” y “b” son primos relativos, entonces existen x, y ∈ Z tales que ax + by = 1.

(Más información en Wikipedia)

Autor: Fran | Publicado el 11 de August de 2006
Comments Off
Categorías: Matemáticas discreta, Números enteros, Números primos, Teoremas

Teoría de números elemental: MCD y mcm

¿Qué son el máximo común divisor (MCD) y el mínimo común múltiplo (mcm)?

Sean a, b ∈ Z y a, b distintos de cero simultáneamente.

Se dice que un número entero “d” es el Máximo Común Divisor, denotado por mcd (a, b), al mayor de los divisores comunes de “a” y “b”. Si “a” y “b” fueran iguales a cero, se toma por convenio que el mcd (0, 0) sea igual a cero.

Se dice que un número entero “d” es el mínimo común múltiplo, denotado por mcm (a, b), al menor de los enteros que son divisibles tanto por “a” como por “b”.

Así partiendo del teorema fundamental de la aritmética:

mcd (a, b) = p₁^{min (a₁, b₁)} · p₂^{min (a₂, b₂)} · p₃^{min (a₃, b₃)} · … · p_nmin (a_n, b_n)

mcm (a, b) = p₁^{max (a₁, b₁)} · p₂^{max (a₂, b₂)} · p₃^{max (a₃, b₃)} · … · p_nmax (a_n, b_n)

(Anotación: Puede que haya factores elevados a cero)

Además, mcd (a, b) · mcm (a, b) = a · b

(Más información en Wikipedia: MCD y mcm)

Cálculo del MCD usando el algoritmo de euclídes

El Máximo Común Divisor también se puede calcular usando el algoritmo de euclídes (que viene del siglo III a. C.). Se fundamenta en el siguiente resultado:

Sean a, b ∈ Z, “b” distinto de cero y sea “r” el resto de la división euclídea de “a” por “b”. Entonces:

• Los divisores comunes de “a” y “b” son divisores de “r”.
• Los divisores comunes de “b” y “r” son divisores de “a”.
• mcd (a, b) = mcd (b, r)
• mcd (a, 0) = a

Con estos datos realizamos la división euclídea, de la siguiente forma, siendo r₀ = a, r₁ = b.

r₀ = r₁ · q₁ + r₂ (siendo r₂ menor que r₁ y mayor o igual a cero)
Se “mueven” las “r’s” hacia la izquierda.
r₁ = r₂ · q₂ + r₃ (siendo r₃ menor que r₂ y mayor o igual a cero)
Se “mueven” las “r’s” hacia la izquierda.
…….

Así seguiríamos “moviendo” las “r’s” hacia la izquierda hasta que en un paso algún resto (r_m) sea igual a cero, y por la propiedad mcd (a, b) = mcd (b, r) antes mencionada, tendríamos que mcd (a, b) = mcd (r₀, r₁) = .. = mcd (r_n, 0) = r_n.

(Más información en Wikipedia)

Autor: Fran | Publicado el 10 de August de 2006
Comments Off
Categorías: Matemáticas discreta, Números enteros, Teoremas

Teoría de números elemental: Números primos

¿Qué son los números primos?

Se dice que todo número natural mayor que uno (n ∈ N, n > 1) es un número primo, si sus únicos divisores en el conjunto de los números naturales (N) son 1 y “n”. De este modo se dice también que todo número no primo es un número compuesto.

(Más información en Wikipedia)

Teorema fundamental de la aritmética

Todo número entero mayor que uno (m ∈ Z, n > 1), se decompone, como producto de números primos, de manera única salvo el orden de los factores.

Esto es, existen unos números primos únicos p₁, p₂, p₃, …, p_n ∈ N y unos únicos a₁, a₂, a₃, …, a_n ∈ N, tales que:

m = p₁^a₁ · p₂^a₂ · p₃^a₃ · … · p_n^a_n

(Más información en Wikipedia)

Autor: Fran | Publicado el 9 de August de 2006
Comments Off
Categorías: Matemáticas discreta, Números enteros, Números primos, Teoremas

Teoría de números elemental: Divisibilidad

¿Qué es la divisibilidad?

Decimos que un número entero “b” es divisible por otro entero “a” (distinto de cero) si existe un tercer entero “c” tal que b = a·c. Se expresa como a|b, que se lee “a” divide a “b” (o “a” es divisor de “b”, o también “b” es múltiplo de “a”).

Por ejemplo, 6 es divisible por 3, ya que 6 = 3·2; pero no es divisible por 4, pues no existe un entero “c” tal que 6 = 4·c.

Propiedades

Sean a, b, c ∈ Z; entonces:

1. Se tiene 1|a, a|0, a|a.
2. Si a|b y b|a entonces b=±a.
3. Si a|b entonces a|b·x (∀x ∈ Z)
4. Si a|b y b|c entonces a|c.
5. Si a|b y a|c entonces a|(b+c).

(Más información en Wikipedia)

Teorema de la división euclídea

Sea a, d ∈ Z, tal que d sea distinto de cero (sea nulo). Entonces, existen unos únicos q, r ∈ Z, tales que a=d·q+r con r mayor o igual a cero y menor que el valor absoluto de “d”.

Siendo “a” el dividendo, “q” el cociente, “d” el divisor y “r” el resto que será siempre positivo. Este método de división es la que se enseña en los colegios.

(Más información en Wikipedia)

Como veís no os mentía en que la teoría de números elemental era entendible para gente no matemática.

• Meneame
• Divúlgame
• Divoblogger
• Bitacoras
• Reddit
• Delicious
• Facebook
• Twitter

Autor: Fran | Publicado el 8 de August de 2006
Comments Off
Categorías: Matemáticas discreta, Números enteros, Teoremas

Teoría de números

La teoría de números es la rama de matemáticas puras que estudia las propiedades de los números enteros y contiene una cantidad considerable de problemas que son fácilmente comprendidos por los no matemáticos. De forma más general, este campo estudia los problemas que surgen con el estudio de los enteros.

Según los métodos empleados y las preguntas que se intentan contestar, la teoría de números se subdivide en varias ramas:

• En la Teoría de Números Elemental, se estudian los números enteros sin emplear técnicas procedentes de otros campos de las matemáticas.
• En la Teoría de Números Algebraica (Aritmética algebraica), el concepto de número es extendido para incluir a los números algebraicos, números que surgen como raíces de polinomios con coeficientes racionales.

Sabiendo que es la teoría de números realizaré una serie de posts en los que trataré de explicaros los teoremas, propiedades y cálculos básicos en los que se basa la Teoría de Números Elemental.

Autor: Fran | Publicado el 7 de August de 2006
Comments Off
Categorías: Matemáticas discreta, Números enteros