MAD: Ecuación de congruencias

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

Ejercicio: Resolver 6X≡ 11 (35)
Posted in: Matemática Discreta by admin Comentarios desactivados en MAD: Ecuación de congruencias

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: Resolver 1²+2²+3²+4²+…+99²+100²≡ X (4)
Posted in: Matemática Discreta by 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 (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:

Ejercicio: Probad que si $an \equiv bn (m)$ y $mcd(m,n)=1$, entonces $a \equiv b (m)$
Posted in: Matemática Discreta by admin Comentarios desactivados en MAD: Congruencias

MAD: Sistema de ecuaciones diofánticas

Hoy hemos terminado el estudio de las ecuaciones diofánticas de tres variables, en particular, cuando ningún para de coeficientes son coprimos. Come veis el resultado es las ecuaciones paramétricas de una variedad afín de puntos enteros.

Para terminar planteamos un sistema de ecuaciones diofántico. Decimos un sistema de ecuaciones diofánticas a un sistema formado por ecuaciones diofánticas y que tiene solución entera. Solo trataremos el caso en el que podemos ver la solución como una resta en el espacio, y por tanto, se plantea el sistema de dos planos que se intersecan en una recta en el espacio.

Para resolverlos será suficiente con despejar de las dos ecuaciones una de las incógnitas dependientes y resolver la ecuación diofántica restante. Si tiene solución, esta nos llevará a la solución de la incógnita dependiente y la determinación si el sistema tiene o no solución.

Ejercicio: Resolver la ecuación diofántica 6x+10y+15z=37.
Posted in: Matemática Discreta by admin Comentarios desactivados en MAD: Sistema de ecuaciones diofánticas

MAD: Ecuaciones diofáticas de tres variables

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.

Ejercicio: Resolver la ecuación diofántica 3x+2y+6z=7.
Posted in: Matemática Discreta by admin Comentarios desactivados en MAD: Ecuaciones diofáticas de tres variables

MAD: Ecuaciones diofáticas

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.

Ejercicio: Resolver la ecuación diofántica $$4x+15y=37.$$
Posted in: Matemática Discreta by admin Comentarios desactivados en MAD: Ecuaciones diofáticas

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

Para calcular el $mcd(a,b)$ utilizaremos algoritmo de Euclides.

Un resultado muy importante es 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: Encontrar dos números enteros $x$ e $y$ tales que $2055x+123y=mcd(2055,123)$
Posted in: Matemática Discreta by admin Comentarios desactivados en MAD: Máximo común divisor

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.

 

Ejercicio:Probar que si $n\in\mathbb{Z}^+$ tiene un factor primo, $p\in\mathbb{Z}^+$, entonces $p<\sqrt{n}$
Posted in: Matemática Discreta by admin Comentarios desactivados en MAD: Números primos

MAD: Algoritmo de la división

El algoritmo de la división 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|$$

Ejercicio: Probar que el cuadrado de todo número entero impar puede escribirse de la forma $4k+1$ para algún entero $k$.
Posted in: Matemática Discreta by admin Comentarios desactivados en MAD: Algoritmo de la división

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 posibles 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: Probar que si $a|b$ y $a|c$, entonces $a|(bx+cy)$, para todo $x,y\in\mathbb{Z}$
Posted in: Matemática Discreta by admin Comentarios desactivados en MAD: Divisibilidad