Diario de Clases

Los pasados días hemos trabajado en los cimientos para abordar la ecuación de congruencias $$aX\equiv b (n)$$

Ahora podemos establecer los criterios que nos permitirán conocer cuándo existe solución:

La ecuación $aX \equiv b (n)$ tiene solución si, y sólo si, el $mcd(a,n)|b$

El procedimiento más sencillo es cuando $mcd(a,n)=1$, que en cuyo caso siempre tiene solución y esta se obtiene buscando el inverso de $a$ en $\mathbb{Z}_n$.

¿Qué ocurre si $mcd(a,n)=d$ y $d|b$? En tal caso la solución que buscamos dependerá de la solución de

$$\frac{a}{d}X_0 \equiv \frac{b}{d} \left(\frac{n}{d}\right)$$

En tal caso, las soluciones será varias y vendrás dadas por:

$$X\equiv \left[X_0+\frac{n}{d}k\right](n), $$

donde $k\in \{0,1,2,\ldots,d-1\}$.

En el día de hoy hemos visto la función $\varphi $ de Euler. Esta función se define como

$$\varphi (n)=|\{m\in\mathbb{Z}^+|m<n, mcd(n,m)=1\}|.$$

Esta función cumple propiedades muy interesantes, como

• Si $p$ es primo, $\varphi (p)=p-1$
• Si $p$ es primo, $\varphi (p^\alpha)=p^{\alpha -1}(p-1)$
• Si $mcd(n,m)=1$ es $\varphi (nm)=\varphi (n)\varphi (m)$

Estos resultados nos sirven para exponer el Teorema de Euler:

Si $a,n\in\mathbb{Z}$ con $mcd(n,a)=1$, entonces $a^{\varphi (n)}\equiv 1(n)$

Este resultado ofrece además una forma de obtener el inverso de un número en $\mathbb{Z}_n$, siempre que este exista.

La descomposición de un numero entero en sus factores primos nos permite formular un resultado práctico para calcular la función $\varphi$

Si $n\in\mathbb{Z}$ es ${\displaystyle n=p_{1}^{k_{1}}\cdots p_{r}^{k_{r}}}$, entonces $$\varphi (n)=n\sum_{i=1}^r\left(1-\frac{1}{p_i}\right)$$

$\quad $

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

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.

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.

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)$$