Diario de clases

En el día de hoy comenzamos haciendo algunos ejercicios que nos recuerden los restos potenciales:

• Probar que 8 divide a $5^{2n-1}+3^{2n-1}$ para todo natural $n$[podéis verlo en el link]
• Calcular el resto de la división de $1020102^{1020102}$ entre 19[podéis verlo en el link]
• Probar que si $p$ es primo y $p\not| a$ entonces, $a^{ (p-1)}\equiv 1(p)$

El siguiente paso es determinar si un elemento de $\bar{b}\in\mathbb{Z}_n $ tiene inverso. Esto solo se nos cumplirá en el caso de que $mcd(b,n)=1$. Pero lo importante es saber cómo calcular el inverso. Para eso utilizamos los siguientes ejercicios:

• Calcular el inverso de $\bar{7}$ en $\mathbb{Z}_{201} $[podéis verlo en el link]
• Calcular el inverso de $\bar{17}$ en $\mathbb{Z}_{112} $[podéis verlo en el link]
• Calcular el inverso de $\bar{115}$ en $\mathbb{Z}_{115} $[podéis verlo en el link]

También 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)$$

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 \pmod{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. Por ejemplo:

• Si ${\displaystyle a\equiv b{\pmod {m}}}$, entonces también ${\displaystyle b\equiv a{\pmod {m}}}$
• Si ${\displaystyle a\equiv b{\pmod {m}}}$ y ${\displaystyle b\equiv c{\pmod {m}}}$, entonces también ${\displaystyle a\equiv c{\pmod {m}}}$.
• Si $a$ es coprimo con $m$ y ${\displaystyle a\equiv b{\pmod {m}}}$, entonces $b$ también es coprimo con $m$.
• Si ${\displaystyle a\equiv b{\pmod {m}}}$ y $k$ es un entero, entonces también se cumple
  • ${\displaystyle a(\pm)k\equiv b(\pm)k{\pmod {m}}}$,
  • ${\displaystyle ka\equiv kb{\pmod {m}}}$,
  • ${\displaystyle a^{k}\equiv b^{k}{\pmod {m}}\qquad k>0}$
• Si además $k$ es coprimo con $m$ entonces podemos encontrar un entero ${\displaystyle k^{-1}\,}$, tal que ${\displaystyle kk^{-1}\equiv 1{\pmod {m}}}$
  • En este caso  tiene perfecto sentido hablar de la división y podemos decir que ${\displaystyle {\frac {a}{k}}\equiv {\frac {b}{k}}{\pmod {m}}}$, entendiendo que ${\displaystyle a/k=ak^{-1}\,}$.

Como consecuencia de lo anterior, si tenemos dos congruencias con igual módulo:
${\displaystyle a\equiv b{\pmod {m}}}$ y ${\displaystyle c\equiv d{\pmod {m}}}$,
podemos sumarlas, restarlas o multiplicarlas de forma que también se verifican las congruencias

• ${\displaystyle a+c\equiv b+d{\pmod {m}}}$
• ${\displaystyle ac\equiv bd{\pmod {m}}}$

Todas estas y más las tenéis en estos enlaces:

• Congruencia
• Aritmética modular

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.

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

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

Colorario:[Propiedad arquimediana] Dados dos números enteros $a$ y $b$, con $b>a>0$, entonces existe un $q\in\mathbb{Z}$ talque $$a(q-1)< b < aq$$

Veamos una algoritmo para obtener el cociente y el resto de la división entera: Sean $a,b\in\mathbb{Z}$, con $b>a>0$ y sea $q_0\in\mathbb{Z}$ talque $r_0=b-aq_0>a$, calculamos

mientras $r_n>a$. Entonces, $b=a\left(\sum_{i=0}^nq_i\right)+r_n$.

Si quisiéramos realizar un programa que lo calcule sobraría con asignar $q_i=1\forall i$ y obtendríamos lo que buscamos:
$$\begin{array}{l}
i=1;\\
r[i]=b-a; \\
while(r[i]>a) \\
\qquad r[i++]=r[i]-a; \\
endwhile \\
print(‘Cociente =\%d’,i-\,-))\\
print(‘resto =\%d’,r[i-\,-]))\\
\end{array}
$$

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

Teorema:[Bezout] Si $d=mcd(a,b)$, entonces
$$\exists x,y\in\mathbb{Z};\, ax+by=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$.

En la presentación del día de hoy hemos visto

• Presentación
• Objetivos de la asignatura
• Metodología y Evaluación
• Bibliografía

Objetivos, Metodología y Evaluación

El contenido de la asignatura está centrado en tres bloques:

• Teoría de números
• Teoría de grafos
• Combinatoria y Lógica

En la guía se detallan en la guía de Grado podéis encontrar la metodología y la evaluación.

Bibliográfica

Básica

• García Merayo F., Matemática Discreta. Ed. Paraninfo, 2015
• García Merayo F., Hernández G., Nevot A. Problemas resueltos de Matemáticas Discreta., Ed. Paraninfo, 2018
• www.ingebook.com

Aconsejable

• Vieites A. M., y otros. Teoría de grafos. Ejercicios y problemas resueltos. Paraninfo, 2014.
• Lipschutz S., Lipson M. 2000 Problemas resueltos de matemática discreta. McGraw-Hill, 2004
• Bujalance, E. y otros. Elementos de Matemática Discreta. Ed. Sanz y Torres, Madrid, 2005
• Bujalance, E. y otros. Problemas de Matemática Discreta. Ed. Sanz y Torres, Madrid, 2005
• Grimaldi, R. P. Discrete and Combinatorial Mathematics. Pearson New International Edition, 2013