MAD: Función φ de Euler

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

 

Ejercicio: ¿Cuál es el resto de la división de $12345678987654321^{12321}$ entre 12?
    1. a) 1
      b) 3
      c) 9
      d) Ninguna de las anteriores.
Posted in: Matemática Discreta por admin Comentarios desactivados en MAD: Función φ de Euler

MAD: Restos potenciales

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.

 

Ejercicio: ¿Cuáles son los dos últimos números de la potencia $1313131313131313^{131313}$?
    1. a) 53
      b) 13
      c) 1
      d) Ninguna de las anteriores.
Posted in: Matemática Discreta por admin Comentarios desactivados en MAD: Restos potenciales

MAD: Congruencias

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:

 

Ejercicio: ¿Cuánto suman todos los divisores del número 294?
    1. a) 880
      b) 724
      c)684
      d) Ninguna de las anteriores.
Posted in: Matemática Discreta por admin Comentarios desactivados en MAD: Congruencias

MAD: Números primos

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

 

Ejercicio: ¿Cuál de las siguientes soluciones, $(x,y)$, se corresponde a la ecuación $2233x+1124y=mcd(2233,1124)$? ($a,b\in\{0,\ldots,9\}$)
    1. a) $(-a5,b49)$
    1. b) $(-5a,4b9)$
    1. c) $(-a,b49)$
    1. d) Ninguna de las anteriores.
Posted in: Matemática Discreta por admin Comentarios desactivados en MAD: Números primos

MAD: Algoritmo de Euclides

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 qi y ri recursivamente mediante las ecuaciones:

a = bq1 + r1  (0<r1<b)

b = r1q2 + r2  (0<r2<r1)

r1 = r2q3 + r3  (0<r3<r2)

….

rk-3 = rk-2qk-1 + rk-1  (0<rk-1<rk-2)

rk-2 = rk-1qk  (rk=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)$$

 

Ejercicio: Si $b,a\in\mathbb{Z}$, $b>a>0$, y $m.c.d(a,b)=d$, entonces $m.c.d\left(\frac{a}{d},\frac{b}{d}\right)=$
    1. a) 1
    1. b) $max\left(\frac{a}{d},\frac{b}{d}\right)$
    1. c) $min\left(\frac{a}{d},\frac{b}{d}\right)$
    1. d) Ninguna de las anteriores.
Posted in: Matemática Discreta por admin Comentarios desactivados en MAD: Algoritmo de Euclides

MAD: Algoritmo de la división y máximo común divisor

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

$b$ $a$
$r_0=b-aq_0$ $q_0$
$r_1=r_0-aq_1$ $q_1$
$r_2=r_1-aq_2$ $q_2$
$\vdots$ $\vdots$
$r_n=r_{n-1}-aq_n$ $q_n$

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().

 

Ejercicio: ¿Qué afirmación es cierta? Para todo $a,b,c\in\mathbb{Z}$
    1. a) Si $a|c$ y $b|c$, entonces $(ab)|c$
    1. b) Si $a|b$ y $a|c$, entonces $a|(bc)$
    1. c) Si $a|b$ y $b|c$, entonces $(ab)|c$
    1. d) Ninguna de las anteriores.
Posted in: Matemática Discreta por admin Comentarios desactivados en MAD: Algoritmo de la división y máximo común divisor

MAD: Divisibilidad

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

 

Ejercicio: ¿Qué afirmación no es cierta?
      a) Todo anillo tiene elemento inverso para la multiplicación.
      b) $\mathbb{Z}$ es un anillo unitario conmutativo.
      c) Un cuerpo no tiene divisores de cero.
Posted in: Matemática Discreta por admin Comentarios desactivados en MAD: Divisibilidad

MAD: Presentación

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
Posted in: Matemática Discreta por admin Comentarios desactivados en MAD: Presentación

ALG: Repaso

Hoy repasamos ejercicios.


Os he añadido esta lectura para el periodo vacacional que se avecina. Está bien despejarse la mente, y si bien lo podéis hacer con una buen película, también con la lectura.

Muret, la batalla que acabó con la Gran Corona de Aragón

Muret, la batalla que decidió la Gran Corona de Aragón

El libro lo podéis encontrar en la web de la editorial o en amazon. Espero que os sea una amena lectura.
Me despido deseándoos una Feliz Navidad y un próspero Año Nuevo 2020 .

 

Ejercicio: Consideremos la matriz $\mathbf{A}=\left[\begin{smallmatrix} 1 & 2 \\ 3 & 2\end{smallmatrix}\right]$. Entonces $\mathbf{A}^7$
a)$\left[\begin{smallmatrix} 6553 & 6554 \\ * & 9830\end{smallmatrix}\right]$
b)$\left[\begin{smallmatrix} 6553 & * \\ 9258 & 9830\end{smallmatrix}\right]$
c)$\left[\begin{smallmatrix} * & 6553 \\ 9831 & *\end{smallmatrix}\right]$
Posted in: Álgebra Lineal por admin Comentarios desactivados en ALG: Repaso

ALG: Matrices diagonalizables

Si el pasado día vimos cómo diagonalizar una matriz hoy veremos algunas de sus propiedades.
Recordemos que dado $\mathbf {A} \in M^{n\times n}(\mathbb {K} )$, una matriz cuadrada con valores sobre un cuerpo $\mathbb {K}$, decimos que $\mathbf{A}$ es diagonalizable si, y sólo si, $\mathbf{A}$ se puede descomponer de la forma: $$\mathbf{A}=\mathbf{P}\mathbf{D}\mathbf{P}^{-1}$$
donde $\mathbf{D}$ es una matriz diagonal cuya diagonal principal está formada por los elementos los autovalores de $\mathbf{A}$ pareciendo cada uno tantas veces como indique su multiplicidad algebraica, y $\mathbf{P}$ es la matriz cuyas columnas son los autovectores; es decir, los vectores que constituyen una base del subespacio propio asociado a cada autovalor siguiendo el orden establecido en $\mathbf{D}$.

Propiedades: Si $\mathbf{A}$ es diagonalizable mediante $\mathbf{A}=\mathbf{P}\mathbf{D}\mathbf{P}^{-1}$, entonces:

  • $$\mathbf{A}^n=\mathbf{P}\mathbf{D}^n\mathbf{P}^{-1}$$
  • Como $e^\mathbf{A}=\sum _{{k=0}}^{\infty }{\frac {{\mathbf {A}}^{k}}{k!}}$, es $$e^{{\mathbf {A}}}={\mathbf {P}}e^{{\mathbf {D}}}{\mathbf {P}}^{{-1}}$$

Cónicas

Otra aplicación importante es en el estudios de las cónicas. Una cónica es por definición el lugar geométrico de la ecuación:
$$ax^2+by^2+2cxy+dy+fx=e$$
que equivale a
$$[x\,\,y]\begin{bmatrix} a&c\\ c&b\end{bmatrix}\begin{bmatrix} x\\ y\end{bmatrix}+[d \,\,f]\begin{bmatrix} x\\ y\end{bmatrix}=e$$
Como la matriz $A=\begin{bmatrix} a&c\\ c&b\end{bmatrix}$ es diagonalizable, existirá $A=PDP^t$, de modo que
$$e=\vec{v}^tPDP^t\vec{v}+[d\,\, f]\vec{v}=\vec{v}^tPDP^t\vec{v}+[d\,\, f]PP^t\vec{v}$$
Si ponemos $P^t\vec{v}=\vec{u}$, la cónica quedará como:
$$e=\vec{u}^tD\vec{u}+[d\,\, f]P\vec{u}.$$
De donde podremos ver que $$e=\lambda_1 \vec{u}_1^2+\lambda_2 \vec{u}_2^2+\alpha\vec{u}_1+\beta\vec{u}_2,$$ donde $\lambda_i$ son los autovalores de $A$ y $\vec{u}_i$ van en la dirección de la base ortonormal de los autovectores de $A$.

 

Ejercicio: Consideremos la matriz $\left[\begin{smallmatrix} 1 & 2 \\ 3 & 2\end{smallmatrix}\right]$. ¿cuál de la siguientes matrices es una matriz que la diagonaliza:
a)$\left[\begin{smallmatrix} 1 & 2 \\ -1 & 3\end{smallmatrix}\right]$
b)$\left[\begin{smallmatrix} 1 & 2 \\ 3 & -1\end{smallmatrix}\right]$
c)$\left[\begin{smallmatrix} -1 & 2 \\ 3 & 1\end{smallmatrix}\right]$

Posted in: Álgebra Lineal por admin Comentarios desactivados en ALG: Matrices diagonalizables