Diario de Clases

Uno de nuestros cometido será resolver la ecuación de congruencias $$aX\equiv b (m)$$

Para comenzar trataremos los restos potenciales; es decir, $$a^i\equiv r_i(n).$$
Estos restos cumplen las siguientes propiedades:
$$\begin{align*}
a^0 &\equiv 1(n) \\
a &\equiv a(n) \\
a^k&\equiv r_k(n)\Rightarrow a^{k+1}\equiv a\cdot r_k(n)
\end{align*}$$

Además a partir de un resto que se repiten, se repiten todos en forma ciclica.

La utilización de los restos potenciales nos sirve para establecer un criterio de divisibilidad que permite saber las propiedades de un número para que sea divisible por otro:

Sea dados $m,n\in\mathbb{Z}^+$ para todo entero $$a=a_kn^k+a_{k-1}n^{k-1}+…+a_1n+a_0$$ si $n^i\equiv r_i(m)$ entonces $$a\equiv a_kr_k+…+a_0r_0(m)$$

Esto nos permite justificar, por ejemplo, que un número es divisible por 3 si la suma de sus dígitos es divisible por 3.

Utilicemos wiki para definir que entendemos por congruencia:

un término usado en la teoría de números, para designar que dos números enteros $a$ y $b$ tienen el mismo resto al dividirlos por un número natural $m\neq 0$, llamado el módulo; esto se expresa utilizando la notación $$a \equiv b (m).$$

Esta definición nos permitía construir clases de equivalencia de números enteros, también llamadas clases de congruencia, que puede ser dotadas de un sistema aritmético. Los conjuntos de estas clases son los conocidos $\mathbb{Z}_n$, que poseen estructura de anillo.

Recordemos que estos conjuntos también puede ser cuerpos, pero solo si $n$ es primo.

$\mathbb{Z}_p$ es un cuerpo si, y solo si, $p$ es primo

En la clase de hoy hemos recordados estos conjuntos y establecido alguna de sus propiedades. Como ejemplo os dejo estos enlaces:

• Congruencia
• Aritmética modular

Consideremos que tenemos un sistema de dos ecuaciones diofánticas de tres variables Con lo que hemos visto cada ecuación define una plano, que puede o no tener soluciones enteras, así el sistema dado por dos planos es una recta. Resolverlo es afrontar la ecuación diofántica de dos variables resultado de simplificar el sistema.

Por ejemplo: sea el sistema
$$
\left\{\begin{array}{ll}
a_1x+b_1y+c_1z=n_1 \\ a_2x+b_2y+c_2z=n_2
\end{array}\right.
$$
Podemos simplificar la variable $x$, multiplicando la primera por $a_2$, la segunda por $-a_1$ y sumando ambas igualdades:
$$
\left\{\begin{array}{ll}
a_2a_1x+a_2b_1y+a_2c_1z=a_2n_1 \\ -a_1a_2x-a_1b_2y-a_1c_2z=-a_1n_2
\end{array}\right. \to (a_2b_1-a_1b_2)y+(a_2c_1-a_1c_2)z=a_2n_1-a_1n_2
$$
El resultado es una ecuación diofántica de dos variables. Notar que convendría la elección de una variable a simplificar que facilite la ecuación resultante.

El pasado día introducimos las ecuaciones lineales diofánticas. En particular, abordamos la solución de la ecuación $$ax+by=c.$$ Hoy nos centramos en la ecuación $$ax+by+cz=n.$$
Como comentamos el día anterior, esta ecuación tiene solución si $m.c.d(a,b,c)|n$. En caso de tener solución podemos calcularla dependiendo de dos casos. El más sencillo es el que plantea cuando dos de los coeficientes de la ecuacion son coprimos. En tal caso, la ecuación plantea una solución parámetrica cuyo parámetro es la variable del coeficiente no coprimo. Es decir, si $m.c.d(a,b)=1$, planteamos la ecuación
$$ax+by=n-c\lambda,$$
donde desginamos $z=\lambda$, la resolvemos como ya conocemos.

Comenzamos con el tema de ecuaciones diofánticas. Recordad que llamamos ecuación diofántica a cualquier ecuación algebraica, generalmente de varias variables, planteada sobre el conjunto de los números enteros $\mathbb{Z}$; es decir, se trata de ecuaciones cuyas soluciones son números enteros.

Nosotros solo trataremos las ecuaciones diofántica lineal; es decir, la ecuación $$a_1x_1 + a_2x_2 + … + a_nx_n = C,$$ y, en concreto, solo de dos o tres variables.

Hemos visto el teorema que nos afirma que

$$a_1x_1 + a_2x_2 + … + a_nx_n = C,$$

tiene solución sii $d=mcd(a_1,a_2,…,a_n)$ divide a $C$.

Primero tratamos la ecuación diofántica de dos variables, $$ax+by=c$$ aprendiendo a resolverla en el caso de que pueda resolverse. Recordad que para ello necesitamos que $mcd(a,b)|c$. Nos apoyamos en el hecho de que la existencia de una solución particular, $$ax_0+by_0=mcd(a,b),$$ dada por el Teorema de Bezout, permitirá encontrar las infinitas soluciones.

El pasado día terminamos con el Teorema fundamental de la aritmética:

Teorema: Todo entero positivo se puede representar de forma única, salvo el orden, como producto de factores primos.

Este resultado es muy importante y nos ofrece consecuencias muy prácticas:

Teorema: Sean $n,m\in \mathbb{Z}-\{-1,0,1\}$, con $n=p_1p_2\cdots p_r$ y $m=q_1q_2\cdots q_s$, sus descomposiciones en factores primos, y $u_j\in\{-1,1\}\forall j\in\mathbb{N}$. Entonces $$n|m\Leftrightarrow \forall i\in\{1,\ldots, r\}\exists j\in\{1,\ldots, r\}\,|\, p_i=q_ju_j$$

Además podemos obtener las siguientes propiedades:

Teorema: Sean $n\in \mathbb{Z}^+$, con $n=p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_r^{\alpha_r}$ la descomposición en factores primos con $p_i\neq p_j\forall j\neq i,\alpha_i\in\mathbb{N}\forall i\in\{1,\ldots, r\}$. Entonces

• (Divisores de un número compuesto) los divisores de $n$ son los términos del producto $$(1+p_1+p_1^2+\ldots+p_1^{\alpha_1})\cdots(1+p_r+p_r^2+\ldots+p_r^{\alpha_r})$$
• (Número de divisores de un número compuesto) $$(\alpha_1+1)(\alpha_2+1)\cdots(\alpha_r+1)$$
• (Suma de los divisores de un número compuesto) $$\frac{p_1^{\alpha_1+1}-1}{p_1-1}\,\frac{p_2^{\alpha_2+1}-1}{p_2-1}\cdots\frac{p_r^{\alpha_r+1}-1}{p_r-1}$$
• (Producto de los divisores de un número compuesto) el producto de los divisores de $n$ es $\sqrt{n^k}$ siendo $k$ el número de divisores de $n$.

En la clase de hoy trataremos los números primos. Llamaremos número primo a todo número entero $p\in\mathbb{Z}$, $p>1$, que no tiene divisores más que el 1 y el mismo.

El siguiente resultado es muy importante:

Teorema: Si $p\in\mathbb{Z}$ es primo y $p|(a\,b)$, entonces, ó $p|a$ ó $p|b$

Para determinar los primos podemos utilizar la criba de Eratóstenes.

Como vemos al utilizar la criba de Eratóstenes observamos que los números primos aparecen constantemente; en efecto, el teorema siguiente lo justifica.

Teorema: El conjunto de los números primos es infinito

Terminamos con el Teorema fundamental de la aritmética:

Teorema: Todo entero positivo se puede representar de forma única, salvo el orden, como producto de factores primos.

El algoritmo de Euclides es un método antiguo y eficiente para calcular el máximo común divisor (mcd). Se basa en el siguiente resultado:

Teorema:
Si $a$ y $b$ son números enteros, $$mcd(a,b)=mcd(b,r),$$ donde $r$ es el resto del algoritmo de la división para $a$ y $b$ ($a=qb+r$).

Utilizando este resultado calculamos el mcd(a,b) de dos enteros (ambos >0, suponemos a > b) definiendo q_i y r_i recursivamente mediante las ecuaciones:

a = bq₁ + r₁  (0<r₁<b)

b = r₁q₂ + r₂  (0<r₂<r₁)

r₁ = r₂q₃ + r₃  (0<r₃<r₂)

….

r_k-3 = r_k-2q_k-1 + r_k-1  (0<r_k-1<r_k-2)

r_k-2 = r_k-1q_k  (r_k=0)

Del teorema anterior, se sigue que:

$$mcd(a,b)=mcd(b,r_1)=mcd(r_1,r_2)=\ldots=mcd(r_{k-2},r_{k-1})=r_{k-1}$$

Una curiosidad es que el número de pasos necesarios para calcular el mcd de dos números es menor que 5 veces el número de dígitos del menor de ellos.

Este algoritmo lo vamos a utilizar precisamente en uno de los resultados más importantes, el que conocemos como teorema de Bezout:

Teorema:
Si $a$ y $b$ son números enteros, entonces existen enteros $x$ e $y$ tales que $$ax + by =mcd(a,b)$$

Comenzamos explicando El algoritmo de la división, que intenta dar consistencia al procedimiento habitual de división entre números enteros, recordando que esta no existe como tal, ya que la división no siempre existe. Sin embargo podemos dar un resultado que nos ayuda a comprender que entendemos por división en los números enteros.

Teorema: Dados dos números enteros $a$ y $b$, con $a$ no nulo, la división euclídea asocia un cociente $q\in\mathbb{Z}$ y un resto $r\in\mathbb{Z}$, únicos, que verifican: $$b=q\,a+r,\quad 0\leq r<|a|$$

El siguiente tema tratado en le máximo común divisor:

Consideremos dos números enteros Si $a$ y $b$ distintos de cero, decimos que $c$ es un divisor común de $a$ y $b$ si $c|a$ y $c|b$. Cuando existen, únicamente, como divisores comunes 1 y -1 de los números $a$ y $b$ , estos se llaman coprimos o números primos entre sí.

Un número entero $d$ se llama máximo común divisor de los números $a$ y $b$, $d=mcd(a,b)$, cuando:

1. d es divisor común de los números $a$ y $b$ y
2. $c$ es divisor de $a$ y $b$, entonces $c|d$.

En la próxima sesión veremos el algoritmo de Euclides como método para calcular el mcd().

El concepto de divisibilidad es uno de los más importantes que veremos en Teoría de números. Con él pretendemos dar una sustitución de la división que no siempre es posible en el conjunto de los números enteros.

Decimos que un número entero $b$ es divisible entre un entero $a$ (distinto de cero) si existe un entero $c$ tal que: $$b = a · c.$$
Se suele expresar de la forma $a|b$, que se lee: $a$ divide a $b$, o $a$ es un divisor de $b$, o, también $b$ es múltiplo de $a$.

Utilizando esta definición hemos probado propiedades de la divisibilidad como

• $1|a$ y $a|0$ para todo $x\in\mathbb{Z}$.
• Si $a|b$, entonces $|a|<|b|$.
• Si $a|b$ y $b|a$, entonces $a=\pm b$.
• Si $a|b$, entonces $a|(bx)$ para todo $x\in\mathbb{Z}$.
• Si $a|b$ y $b|c$, entonces $a|c$.