MAD: Sistemas de ecuaciones

Hoy abordaremos los sistemas de ecuaciones, bien de congruencias o de ecuaciones diofánticas.

Los sistemas de congruencias atienden al Teorema chino del resto:

Supongamos que n1, n2, …, nk son enteros coprimos dos a dos. Entonces, para enteros dados a1,a2, …, ak, existe un entero x que resuelve el sistema de congruencias simultáneas

\begin{align}<br /> x &\equiv a_1 \pmod{n_1} \\<br /> x &\equiv a_2 \pmod{n_2} \\<br /> &\vdots \\<br /> x &\equiv a_k \pmod{n_k}<br /> \end{align}

Más aún, todas las soluciones x de este sistema son congruentes módulo el producto N = n1n2nk.

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.

Ejercicio: ¿Cuál de estas variables es solución de la ecuación $15x-21y+35z=14$?
    1. a) $x=11-42k-7l$
      b) $y=-14+5k$
      c) $z=-5+3k+21l$
      d) Ninguna de las anteriores.
Posted in: Matemática Discreta por admin Comentarios desactivados en MAD: Sistemas de ecuaciones

MAD: Ecuaciones diofánticas de tres variables II

El pasado día analizamos el caso de una ecuación $ax+by+cz=n$,donde dos de los coeficientes de la ecuación 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, supongamos que $m.c.d(a,b)=1$, entonces planteamos la ecuación
$$ax+by=n-ck,$$
donde designamos $z=k$, la resolvemos como ya conocemos.

Ahora nos enfrentamos al problemas de no hayan dos coeficientes coprimos; es decir, $m.c.d(a_i,a_j)=1$ $\forall i\neq j$, $i,j=\{1,2,3\}$ con
$$a_1 x_1+a_2x_2+a_3x_3=n $$

En tal caso, elegimos dos coeficientes y determinamos $m.c.d(a_i,b_j)=d$ y planteamos la ecuación: $$du+a_kx_k=n,$$
con una nueva variable $u$ y donde $j\neq k\neq i$.

Esta ecuación tendrá solución al tener la de partida. Una vez resulta solo tendremos que afrontar la solución paramétrica de $$a_ix_i+a_jx_j=du$$

Ejercicio: Conociendo que $x=5-2m+n$, $y=10-5m+2n$ es solución de la ecuación $5x-2y-z=5$, la solución de la variable $z$ será:
    1. a) $z=n$
      b) $z=m$
      c) $z=k$
      d) Ninguna de las anteriores.
Posted in: Matemática Discreta por admin Comentarios desactivados en MAD: Ecuaciones diofánticas de tres variables II

MAD: Ecuaciones diofánticas 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 ecuación 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 designamos $z=\lambda$, la resolvemos como ya conocemos.

Ejercicio: Para cuántos valores de $n\in\mathbb{Z},\, 150\leq n\leq 250$ tiene solución ecuación $24x+36y=n$.
    1. a) 9
      b) 8
      c) 7
      d) Ninguna de las anteriores.
Posted in: Matemática Discreta por admin Comentarios desactivados en MAD: Ecuaciones diofánticas de tres variables

MAD: Ecuaciones diofánticas

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.

Estas serán

$$
\begin{array}{l}
X=x_0c’+\frac{b}{d}k\\
Y=y_0c’-\frac{a}{d}k
\end{array}
$$

donde $c=dc’$.

Ejercicio: ¿Cuál de los siguientes números es primo?
    1. a) 1750339
      b) 1753519
      c) 1768211
      d) Ninguna de las anteriores.
Posted in: Matemática Discreta por admin Comentarios desactivados en MAD: Ecuaciones diofánticas

MAD: Test de primalidad

En la última clase vimos el teorema de Euler que nos determina el inverso, cuando existe, de un elemento en $\mathbb{Z}_n$. Este teorema tenía un antecedente, que se conoce como el Teorema pequeño de Fermat:

Si $a,p\in\mathbb{Z}$ con $p$ primo y $p$ no divide a $a$, entonces $$a^{p-1}\equiv 1(p)$$

Consecuentemente si dado un número $n$ que no divida a $a$ se cumple $$a^{n-1}\not\equiv 1(n)$$
implicaría que $n$ no es primo, pues de lo contrario incumpliría el Teorema pequeño de Fermat.

Pues bien, este resultado lo podemos utilizar para chequear si un número es primo. Este test se denomina test de primalidad de Fermat.

Disponemos de un resultado que nos garantiza si un número es primo, el Teorema de Wilson:

El número $n\in\mathbb{Z},\, n>1$ es primo si, y sólo, si $$(n-1)!\equiv -1(n)$$

El problema es el cómputo del factorial que es treméndamente costoso para número muy grandes. Por ese motivo utilizamos los test de primalidad.

Un test de primalidad (o chequeo de primalidad) es un algoritmo que, dado un número de entrada $n$, no consigue verificar la hipótesis de un teorema cuya conclusión es que $n$ es compuesto.

El test de Fermat nos propone buscar si un número es compuesto probando las igualdades $$2^{n-1}\equiv 1(n),$$ $$3^{n-1}\equiv 1(n),$$ $$5^{n-1}\equiv 1(n),…$$ $$a^{n-1}\equiv 1(n),$$ hasta encontrar un valor de $1<a<n$ para el que no se cumpla.

Lo que ocurre es que podemos encontrar valores que verifican la igualdad siempre y no por ello son primos: son los conocidos números de Carmichael, o pseudoprimos.

Hay más test de este tipo, son conocidos como test probabilísticos de primalidad, pues no nos garantizan que es primo; más bien ofrecen una probabilidad de que sea primo.

El test de Fermat puede mejorarse utilizando el criterio de Euler:

Si $p\in\mathbb{Z}$ es primo y $p$ no divide a $a$, entonces $$a^\frac{p-1}{2}\equiv 1(p)\, \mbox{ ó, } a^\frac{p-1}{2}\equiv -1(p)$$

El test probabilístico de primalidad más utilizado es el de Rabin-Miller, basado en el resultado:

Sea $p\in\mathbb{Z},\, p>1$ primo impar y $k,m\in\mathbb{Z}$, tales que $p-1=2^km$, com $m$ impar. Entonces, para todo entero positivo $a$, menor que $p$, se cumple al menos una de los siguientes resultados:

  • Algún número de la serie $a^{2^km},a^{2^{k-1}m},…,a^{m}$ es congruente con -1 módulo $p$.
  • $a^m\equiv 1(p)$
Ejercicio: ¿Cuántos factores primos distintos tiene la descomposición factorial del número 10219452529?
    1. a) 6
      b) 8
      c) 4
      d) Ninguna de las anteriores.
Posted in: Matemática Discreta por admin Comentarios desactivados en MAD: Test de primalidad

MAD: Factorización de Fermat

Uno de los problemas que nos encontramos es la factorización de un número. Hoy veremos la factorización de Fermat.

El método de factorización de Fermat se basa en la representación de un número natural impar como la diferencia de dos cuadrados:
$$n=a^2-b^2.$$

Esa diferencia se puede factorizar algebraicamente como $(a+b)(a-b)$; si ninguno de esos factores es igual a 1, se trata de una factorización propia de $n$.

El procedimiento consiste en buscar un número $x$ mayor que $\sqrt{n}$ y tal que $x^2-n$ sea un cuadrado perfecto, entonces habremos encontrado la descomposición buscada.

Veamos un ejemplo. Tomemos el número $n=10058886427$, la parte entera de su raíz cuadrada es $\left \lfloor \sqrt{n} \right \rfloor=100293$.

  • Sea $x=100293+1$, calculamos $\left \lfloor x^2-n \right \rfloor=9$
  • Como 9 es un cuadrado perfecto, la descomposición que buscamos es:
    • $n=x^2-9$; es decir, $n=(x-3)(x+3)$
  • Por tanto, $n=100291\cdot 100297$

Este ejemplo tiene una sola iteración, pero puede complicarse más todavía:

  • $n=10233712469$
  • $x=\left \lfloor \sqrt{n} \right \rfloor+1=101162$
  • Repetimos
    • Es decimal $\sqrt{x^2-n}$ entonces
      • $x=x+1$
    • en caso contrario
      • $n=(x-\sqrt{x^2-n})\cdot (x+\sqrt{x^2-n})$

En este ejemplo:

  1. $\sqrt{101162^2-n}=194.35$
  2. $x=101163 \to \sqrt{101163^2-n}=490$
  3. $n=(101163-490)\cdot (101163+490)=100673\cdot 101653$

El algoritmo funciona rápido que $n$ es producto de dos factores cercanos, en otro caso puede alargarse. Veamos otros ejemplo:

  1. $n=2615836543$
  2. $\sqrt{n}=51145.25$
  3. $x=51145+1 \sqrt{x^2-n}=277.0794$
  4. $x=51146+1 \to \sqrt{x^2-n}=423.1619$
  5. $x=51147+1 \to \sqrt{x^2-n}=530.4347$
  6. $x=51148+1 \to \sqrt{x^2-n}=619.4013$
  7. $x=51149+1 \to \sqrt{x^2-n}=697.1062$
  8. $x=51150+1 \to \sqrt{x^2-n}=766.9798$
  9. $x=51151+1 \to \sqrt{x^2-n}=831$
  10. $n=(51152-831)\cdot (51152+831)=50321\cdot 51983$

En este caso 50321 es primo, pero 51983 no. Ahora habría que factorizar este número.

 

Podéis ver más de este método en:

 

Ejercicio: ¿Cuál de las soluciones expuestas lo es de la ecuación: $30X\equiv 18(78)$? ($a$, $b$ son dígitos distintos y $c$ un dígito que no tienen porqué ser distinto a los anteriores, y $k$ es un parámetro)
    1. a) $X\equiv \left[aa+cbk\right](78)$
      b) $X\equiv \left[ab+bck\right](78)$
      c) $X\equiv \left[ba+ack\right](78)$
      d) Ninguna de las anteriores.
Posted in: Matemática Discreta por admin Comentarios desactivados en MAD: Factorización de Fermat

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

¿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\}$.

 

Ejercicio: ¿Cuáles son las dos primeras cifras de $\phi(4702744728253)$
    1. a) 35
      b) 23
      c) 52
      d) Ninguna de las anteriores.
Posted in: Matemática Discreta por admin Comentarios desactivados en MAD: Ecuación de congruencias

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