Criterio Del 7

Tema 3: Ecuaciones diofánticas, congruencias y criterios de
divisibilidad
J. Sendra, E. Martín, A. Méndez y C. Ortiz
Marzo 2011
Índice
Guía del tema II
1. Ecuaciones Diofánticas 1
2. Congruencias 4
3. Sistemas de Numeración y criterios de divisibilidad 10
I
Matemática Discreta. Curso 2010/11. 2o semestre. (Dpto. Matemática Aplicada a la I.T.T.) E.U.I.T.Telecomunicación (U.P.M.)
Guíadel tema
Asignatura: Matemática Discreta
Titulo de la Unidad: Ecuaciones diofánticas, congruencias y criterios de divisibilidad
Semanas de impartición en el cuatrimestre: Del 21 de marzo al 1 de abril
Requisitos para seguir con aprovechamiento el tema
Manejar con soltura el algoritmo de la división.
Conocer y manejar relaciones de equivalencia.
Atención y paciencia para asimilar losresultados.
Conocer y utilizar el principio de inducción matemática.
Objetivos
Objetivo general: Conocer y manejar ecuaciones diofánticas, congruencias y sistemas de numeración
Objetivos Específicos:
Manejar los restos de las divisiones.
Conocer y resolver las ecuaciones diofánticas.
Manejar el concepto de congruencia.
Aplicar propiedades básicas de las congruencias.
Conocer el Teorema Pequeño deFermat.
Calcular el inverso de un número en Zm.
Resolver Ecuaciones con congruencias.
Entender el Teorema de los restos chinos y saber aplicar el método para resolver un sistema de
congruencias.
Conocer los comandos más básicos de Maple en relación con congruencias.
Deducir criterios de divisibilidad a partir de resultados generales,
Aplicar los resultados para conocer los divisores de unnúmero entero no negativo.
Contenidos teóricos
II
Matemática Discreta. Curso 2010/11. 2o semestre. (Dpto. Matemática Aplicada a la I.T.T.) E.U.I.T.Telecomunicación (U.P.M.)
Ecuaciones Diofánticas
Congruencias
Sistemas de numeración y criterios de divisibilidad
Evaluación Se entregarán los ejercicios propuestos antes de la fecha límite 11 de abril de 2011
III
Matemática Discreta. Curso2010/11. 2o semestre. (Dpto. Matemática Aplicada a la I.T.T.) E.U.I.T.Telecomunicación (U.P.M.)
1. Ecuaciones Diofánticas
Se llama ecuaciones diofánticas a una amplia clase de ecuaciones algebraicas con más de una indeterminada
en Z y Q. En primer lugar, se estudian las ecuaciones lineales diofánticas de la forma ax + by = n. A
continuación, se analiza la ecuación diofántica de la forma x2¡y2 = ncon n > 0, así como la ecuación, también
llamada pitagórica, de la forma x2 + y2 = z2. Se termina la sección enunciando la famosa conjetura de Fermat.
Teorema 1.1. Sean a, b y n 2 Z. La ecuación lineal ax + by = n tiene solución entera x0; y0 si y sólo si
d = mcd(a; b) divide a n.
Demostración. Si la ecuación tiene soluciones enteras x0; y0 entonces ax0 +by0 = n. Ahora bien, como d j ax0
y d jby0 se tiene que d j n. Supongamos ahora que d j n, es decir existe r 2 Z tal que n = dr. Si n = 0 entonces
x0 = 0 e y0 = 0 es una solución trivial de la ecuación. Si n 6= 0 entonces d 6= 0 y existen u; v 2 Z tales que
au + bv = d. Multiplicando por r ambos lados de esta ecuación se tiene a(ur) + b(vr) = dr = n, de donde se
deduce que x0 = ur, y0 = vr es una solución de la ecuación ax0 + by0 =n. ¤
Algoritmo para encontrar una solución.
Sea la ecuación diofántica ax + by = n. En primer lugar se calcula el mcd(a; b) mediante el algoritmo
de Euclides:
a = bq1 + r1
b = r1q2 + r2
...
rt¡2 = rt¡1qt + rt
rt¡1 = rtqt+1
donde rt = mcd(a; b) = d. Por tanto despejando de la penúltima ecuación se tiene:
rt¡2 ¡ rt¡1qt = d
y substituyendo el valor de rt¡1 de la ecuación anterior a ésta,se obtiene:
rt¡2 ¡ (rt¡3 ¡ rt¡2qt¡1)qt = d
que es equivalente a:
¡rt¡3qt + rt¡2(1 + qtqt¡1) = d:
Siguiendo este proceso de substitución ascendiendo por las igualdades, se obtiene
aq¤1 + bq¤2 = d
1
Matemática Discreta. Curso 2010/11. 2o semestre. (Dpto. Matemática Aplicada a la I.T.T.) E.U.I.T.Telecomunicación (U.P.M.)
donde q¤1; q¤2 son expresiones en función de q1; ¢ ¢ ¢ ; qt. Por...