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$ […]

Posted in: Matemática Discreta by admin No Comments

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 […]

Posted in: Matemática Discreta by admin No Comments

MAD: Función φ de Euler

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 […]

Posted in: Matemática Discreta by admin No Comments

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 […]

Posted in: Matemática Discreta by admin No Comments

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 […]

Posted in: Matemática Discreta by admin No Comments