Tema 15: Ecuaciones Diofánticas PDF

# **Tema 15: Ecuaciones Diofánticas** ## **15.1. La Ecuación Lineal con Dos Incógnitas ax+by=c** Se usa el nombre de *ecuaciones diofánticas* para designar una amplia clase de ecuaciones algebraicas con más de una indeterminada y con coeficientes enteros. Las ecuaciones diofánticas buscan soluci...

# **Tema 15: Ecuaciones Diofánticas** ## **15.1. La Ecuación Lineal con Dos Incógnitas ax+by=c** Se usa el nombre de *ecuaciones diofánticas* para designar una amplia clase de ecuaciones algebraicas con más de una indeterminada y con coeficientes enteros. Las ecuaciones diofánticas buscan soluciones enteras (formadas únicamente por números enteros). El nombre de estas ecuaciones hace honor a Diofanto de Alejandría. ### **15.1.1. Teorema** La ecuación diofántica lineal ax + by = c tiene solución entera si y solo si d = mcd(a,b) es un divisor de c. Si (x₀, y₀) es una solución particular de esta ecuación, cualquier otra solución de la misma está dada por: x = x₀ + (b/d)λ y = y₀ - (a/d)λ donde λ∈Ζ **Demostración** - Supongamos que la ecuación tiene solución entera (x₀, y₀), es decir, ax₀ + by₀ = c. - Como d|a y d|b, *d* también divide a *ax₀* y *by₀*, y por lo tanto a *ax₀ + by₀* es decir, d|c. - Recíprocamente, supongamos que mcd(a,b) divide a c. - Según la identidad de Bezout, existen x, y tales que d = ax + by. - Los números x = x₀, e y = y₀ son enteros pues c es múltiplo de d, además, (x,y₀) es solución porque ax + by = ax₀ + by₀ = (ax + by)c/d = c. Esto prueba la primera parte del teorema. Para la segunda, por ser (x₀, y₀) una solución particular, es ax₀ + by₀ = c. Si (x₁, y₁) es cualquier otra solución, también será ax₁ + by₁ = c y al restar ambas igualdades, a(x₁-x₀) = b(y₀-y₁) Por ser d = mcd (a,b), podemos escribir a = dr, b = ds, para ciertos r,s ∈ Ζ tales que mcd(r,s) = 1. La igualdad (1) se escribe ahora dr (xi-xo) = ds (yo-y₁) y, tras simplificar, r(x₁-xo) = s (yo-y₁) Como r divide a s(yo-y₁) y r,s son coprimos, r es divisor de yo-y₁, luego yo-y₁ = rλ. Sustituyendo en (2), se tiene r(x₁ - xo) = srx, es decir, x₁ - x₁ = sλ, o bien, x₁ = xo + sλ, y toda solución puede ser escrita como indica el enunciado. Recíprocamente, si (x,y) es una solución particular, (x,y) = (x + x,yo-λ) es solución de la ecuación, para cada λ∈Z, puesto que: ax + by = a(x + (b/d)λ) + b(y₀ - (a/d)λ) = ax₀ + by₀ = c Puede no resultar sencillo dar "a simple vista" con una solución particular (x₀, y₀) de la ecuación. El Algoritmo de Euclides facilita un procedimiento para su obtención. ### **15.1.2. Determinación de una Solución Particular de la Ecuación Lineal** El método clásico de búsqueda de una *solución particular* de la ecuación ax + by = c, en la que d = mcd(a,b) es divisor de c, comienza determinando dos enteros x₁ e y₁ tales que ax₁ + by₁ = d, enteros que existen según la Igualdad de Bezout y que pueden deducirse de la aplicación del Algoritmo de Euclides para el cálculo de mcd(a,b) = d (ver 4.2.10). Una vez identificados, y según se comprobó en la demostración de la primera parte del teorema 15.11, una solución de la ecuación será x₀ = (c/d)x y₀ = (c/d)y ## **15.2. La Ecuación Lineal con n Incógnitas a₁x₁ + a₂x₂ + ... + a_nx_n = c** El siguiente teorema es la generalización evidente del teorema 15.1.1 para el caso de n incógnitas. Como ya está demostrado para n=2, puede probarse razonando por inducción sobre n y utilizando que es mcd (mcd (a₁,...,a,-1);a„) mcd(1,...,an). Supondremos, en este apartado 15.2, que todos los coeficientes a₁,...a_n son no nulos. ### **15.2.1. Teorema** La ecuación diofántica lineal a₁x₁ + a₂x₂ + ... + a_nx_n = c tiene solución entera si y solo si c es múltiplo de med (a₁, a₂,..., a_n). Podemos limitarnos a resolver las ecuaciones lineales a₁x₁ + a₂x₂ + ... + a_nx_n = c en las que mcd (a₁,a₂,...,a_n) = 1 pues, si no es así, basta dividir todos sus términos por d = mcd (a₁, a₂,...,an) y obtener la ecuación equivalente x₁ + x₂ + ... + x_n = c/d , en la que mcd (a₁, a₂,...,a_n) = 1. El siguiente resultado resuelve estas ecuaciones lineales si hay algún par de coeficientes a_i y a_j que sean coprimos. Supondremos, por comodidad, que son a₁ y a₂. ### **15.2.2. Teorema** Sea a₁x₁ + a₂x₂ + ... + a_nx_n = с una ecuación diofántica lineal en la que mcd(a₁,a₂,...,an) = 1 y mcd(a₁, a₂) = 1. Entonces, cualquier solución entera de dicha ecuación es de la forma: x₁ = a₁(c - a₃x₃ - ... - a_nx_n) + a₂μ x₂ = a₂(c - a₃x₃ - ... - a_nx_n) – a₁μ, x_k = x_k, si k≥3 donde λ₃,..., λ_n, μ∈Ζ donde (a₁,a₂) es una solución particular de la ecuación a₁x₁ + a₂x₂ = 1. **Demostración** - Sea (x₁, x₂,...,x_n) ∈ Ζⁿ una solución cualquiera de a₁x₁ + a₂x₂ + ... + a_nx_n = c. - Entonces, (x₁,x₂) es solución de la ecuación a₁x₁ + a₂x₂ = c- a₃x₃ - ... - a_nx_n - Como es mcd (a₁,a₂) = 1, y en la que el resto de los x_i, se suponen conocidos. - Según 15.1.1, como es mcd (a₁, a₂) = 1, si (a₁,a₂) es una solución particular de a₁x₁ + a₂x₂ = 1, entonces (a₁ (c- a₃x₃ - ... - a_nx_n) + a₂μ, a₂ (c- a₃x₃ - ... - a_nx_n) – a₁μ) es una solución particular de (3), por lo que cualquier solución de (3) es (a₁ (c- a₃x₃ - ... - a_nx_n) + a₂μ, a₂ (c - a₃x₃ - ... - a_nx_n) – a₁μ), es decir x₁ = a₁ (c- a₃x₃ - ... - a_nx_n) + a₂μ, x₂ = a₂(c - a₃x₃ - ... - a_nx_n) – a₁μ, donde μ∈Z. - Basta poner x_k = x_k ∈ Z , para k≥ 3 para concluir que (x₁,...,x_n) es de la forma indicada. - Recíprocamente, es inmediato comprobar que cualquier n-upla de la forma dada es solución de la ecuación. El siguiente resultado, de prueba inmediata, establece cómo resolver las ecuaciones lineales en las que mcd (a₁, a₂,..., a_n) = 1 y, en cambio, mcd(a_i, a_j) ≠ 1 para i ≠ j. ### **15.2.3. Teorema** Sea a₁x₁ + a₂x₂+..+a_nx_n = c una ecuación diofántica lineal en la que mcd (a₁,a₂,...,an) = 1, mcd (a₁, a_j) ≠ 1 si i ≠ j, y d = mcd (a₁,..., a_n-1). Entonces, (x₁, x₂,...,x_n) es solución entera de la ecuación si y solo si (x₁ + ... + x_n-1,x_n) es solución entera de la ecuación du + a_nx_n = c, cuyas incógnitas son (u,x_n). Según esto, para resolver a₁x₁ + ... + a_nx_n = c se comienza encontrando todas las soluciones (u,x_n) de la ecuación diofántica lineal con dos incógnitas du+a_nx_n = c. Una vez obtenidas, todo se reduce a resolver la ecuación lineal de n-1 incógnitas x₁+...+xm_1 = u en la que mcd(a₁,..., a_n-1) = 1. Si esta ecuación cumple las hipótesis de 15.2.2, se resuelve como allí se indica. De no ser así basta reducirla a una ecuación con n-2 incógnitas tal como se explica en 15.2.3. Repitiendo sucesivamente este proceso se llega a una ecuación lineal con dos incógnitas con solución conocida. # **15.3. Sistemas de Ecuaciones Lineales AX = C** Considérese el sistema de ecuaciones lineales diofánticas Σ_i=1^m a_ijx_j = c₁, i = 1,..., m . Si son A = (a_ij) ∈ M_mxn (Z) y C = (c_i) ∈ M_nx1 (Z), el sistema se escribe matricialmente AX = C. Damos ahora condiciones necesarias para que dicho sistema tenga solución entera: la primera se sigue del teorema de Rouche (ver 16.5.1) y la segunda de 15.2.1. ### **15.3.1. Teorema** Si el sistema de ecuaciones lineales AX = C tiene solución entera, han de cumplirse las dos condiciones siguientes: 1. rang (A) = rang(A|C), donde (AC) es la matriz ampliada del sistema. 2. c_i es multiplo de med (a_i1, a_i2,..., a_in), para cada i = 1,..., m ### **15.3.2. Teorema** El sistema diofántico lineal AX = C tiene solución entera si y sólo si rang (A) = rang (AC) = r y el máximo común divisor de todos los menores de orden r de la matriz A divide a todos los menores de orden r de la matriz (AC). # **15.4. La Ecuación x² - y² = n** ### **15.4.1 Teorema** Sea n∈N. La ecuación diofántica x² - y² = n tiene solución entera si y solo si n se puede factorizar como producto de dos números enteros de la misma paridad, es decir, ambos pares o ambos impares. En tal caso, las soluciones de la ecuación son: x = (λ + μ)/2 y = (λ - μ)/2 donde λ y μ recorren todos los pares de enteros de igual paridad tales que n = λμ. **Demostración** - Si la ecuación tiene solución (x₀,y₀), entonces n = x₀² - y₀² = (x₀ + y₀)(x₀ - y₀), donde λ = x₀ + y₀ y μ = x₀ - y₀ son de la misma paridad puesto que (x₀ + y₀)-(x₀ - y₀) = 2y₀ . - Recíprocamente, supongamos que n = λμ, donde λ y μ tienen igual paridad. - Si son x₀ = (λ+μ)/2, y₀ = (λ-μ)/2, es inmediato que x₀,y₀ ∈Z, pues si λ y μ son de la misma paridad, λ+μ y λ-μ son pares. Además (x₀,y₀) es solucion de la ecuación, ya que: ((λ+μ)/2)² - ((λ-μ)/2)² = λ² + 2λμ + μ² - ( λ² – 2λμ + μ²)/4 = 4λμ/4 = λμ = n ### **15.4.2. Observación** - Si en la ecuación x² - y² = n ocurre que n es impar, entonces λ y μ deben ser impares. - En cambio, si n es par, y μ deben ser pares, y resulta: - Si n no es múltiplo de 4, la ecuación no tiene solución. - Si n es múltiplo de 4, los cálculos se facilitan poniendo n = 4η, λ = 2λ₁, μ = 2μ₁, con lo que x = λ₁ + μ₁, y = λ₁ - μ₁ - y las soluciones son x = λ₁ + μ₁, y = λ₁ - μ₁ De 15.4.1. se deduce que factorizar un entero impar n equivale a resolver la ecuación diofántica x² - y² = n, pues cada factorización de n da lugar a una solución de dicha ecuación y viceversa. En base a esto, Fermat ideó un algoritmo para factorizar un natural impar ≥3) como producto de primos. Aunque el algoritmo es largo en ciertos casos, no requiere conocer todos los primos menores o iguales que √n y resulta cómodo si se puede descomponer como producto de dos factores próximos. ### **15.4.3. Algoritmo de Factorización de Fermat** Se comienza, para la posible factorización como producto de naturales de nimpar y no cuadrado perfecto (si fuese cuadrado perfecto, aplicaríamos el procedimiento an), buscando números xe y naturales tales que x² - y² = n, esto es, tales que n = j² para lo cual se determina el menor natural k tal que k² >n, es decir, tal que k> √n, y se estudia a continuación si alguno de los números k²-n, (k + 1)² - n, (k+2)² – n, (k + 3)² – п, ... es un cuadrado. Este proceso no es indefinido, porque eventualmente se llega hasta (ⁿ⁺¹/₂)² - n = (ⁿ⁺¹/₂)², que corresponde a la factorización trivial n = n·1, que es la última posible, pues si x > ⁿ⁺¹/₂, entonces y² > (ⁿ⁺¹/₂)² - n = (ⁿ⁺¹/₂)², es decir, y > ⁿ⁺¹/₂, y por tanto, x+y>ⁿ⁺¹/₂ + ⁿ⁺¹/₂ = n, lo que contradice el que sea x + y sea divisor de n, que lo es por ser n = x² - y² = (x + y)(x - y). En resumen, el valor de xen cualquier solución natural (x,y) de la ecuación cumple que √n < x < ⁿ⁺¹/₂ Si el único de estos x que hace de x² - n un cuadrado esx = ⁿ⁺¹/₂, entonces n no tiene otros factores que n y 1, lo que significa que nes primo. Si nes compuesto aplicaríamos el procedimiento a cada uno de los factores obtenidos hasta llegar a la descomposición deseada de nen factores primos. # **15.5. La Ecuación Pitagórica x² + y² = z²** Buscar las soluciones naturales de la ecuación x² + y² = z² es equivalente a encontrar todos los triángulos rectángulos con lados de longitud entera. Observemos en primer lugar que si (x₀,y₀,z₀) es una solución de la ecuación x₀² + y₀² = z₀², también lo es (ax₀, ay₀, az₀) para cualquier entero a, ya que (ax₀)² + (ay₀)² = a²x₀² + a²y₀² = a²(x₀² + y₀²) = a²z₀² = (az₀)² Por otra parte, si d mcd(x₀, y₀, z₀), entonces (^x₀/_d, ^y₀/_d, ^z₀/_d) también es solución y además mcd (^x₀/_d, ^y₀/_d, ^z₀/_d) = 1. Por tanto, para resolver el problema bastará buscar las soluciones naturales (x,y,z) tales que med (x, y, z) = 1, llamadas *ternas primitivas pitagóricas*, ya que las demás se obtendrán de éstas multiplicándolas por cualquier entero a no nulo. ### **15.5.1. Teorema** Consideremos la ecuación pitagórica x² + y² = z². Las soluciones naturales (x,y,z) de dicha ecuación tales que mcd(x,y,z) = 1 son: x = 2λμ y = λ² - μ² z = λ² + μ² donde λ y μ son dos naturales de distinta paridad tales que λ> μ y mcd(λ,μ) = 1. **Demostración** - Sea (x, y, z) ∈ N³ una solución de la ecuación x² + y² = z² tal que mcd(x, y, z) = 1. - Deducimos inmediatamente que mcd(x, y) = 1, pues si des divisor natural de xey, entonces d² es divisor de x² e y², luego también lo es de x² + y² = z², así es que d también divide a z, por lo que d = 1. Como es mcd(x,y)=1, xoy son impares, así es que suponemos que lo es y (si el impar fuese x obtendríamos, intercambiando los papeles de xey, la otra solución). Si también x fuese impar serían x = 2m-1, y = 2n-1 para ciertos m, n ∈ Ν. Entonces: z² = x² + y² = (2m – 1)² + (2n - 1)² = 4 (m² + n²-m-n)+2 pero esto es absurdo porque cualquier cuadrado es congruente con 0 ó 1 módulo 4. Por tanto, xes par y también lo es x², luego z² = x² + y² es impar y z es impar. Así, z² = x² + y² = (z + y)(z - y) donde z+y yz son pares. Existen, por tanto, u, v∈N tales que z+ y = 2u, z - y = 2v, x = 2ω, entonces 4ω² = x² = (z + y)(z - y) = 2u · 2v, luego w² = uv Comprobamos ahora que u uson coprimos. Si fuese med (u, v) = 1, existiría algún número primo p divisor de uyv, con lo cual también dividiría z + y + z - y) = z y u - v = (2u - 2v) ==(z+ y + z + y) = y y por tanto p sería divisor de zy = x², lo que, por ser p primo, conduce a que p es divisor de x, pero esto es imposible por ser mcd (x,y) = 1. Así pues, uy v son coprimos y su producto es un un cuadrado (w²), luego ambos son cuadrados y existen por tanto λ, με N tales que u=λ² y v = μ² de manera que w² = uv = λ⁴μ⁴, como w² = uv, λγμ son números naturales, se tiene que w = λμ, así es que x = 2ω = 2λμ Como y = x² – μ² es natural resulta que λ> μ, así es que sólo resta comprobar que mcd(λ, μ) = 1 y que Ayuson de distinta paridad. La primera se deduce de 1 = mcd (u, v) = mcd (1², μ²) = [mcd (λ, μ)]² y, para la segunda, si Ayu fuesen de igual paridad también lo serían d² y μ², así es que z = x² + μ² e y = x² – μ² serían ambos pares, por lo que x² = z² - y² y, por tanto, x, serían pares igualmente. Pero esto es imposible por ser mcd(x, y, z) = 1. La comprobación de que la terna (x, y, z) obtenida es solución de la ecuación es inmediata. ### **15.5.2. Observaciones** 1. Cualquier solución natural de la ecuación pitagórica x² + y² = z² es entonces: x = 2αλμ, y = a(λ² – μ²), z = α(λ² + μ²) (α∈Ν) 2. Para obtener todas las soluciones enteras de la ecuación pitagórica bastará con cambiar de signo alguna de las coordenadas de las soluciones naturales. 3. Las seis primjeras ternas primitivas pitagóricas (x,y,z) figuran en la tabla adjunta. | x = 2λμ | y = λ² – μ² | z = λ² + μ² | |---|---|---| | 3 | 4 | 5 | | 5 | 12 | 13 | | 7 | 24 | 25 | | 8 | 15 | 17 | | 9 | 40 | 41 | | 12 | 35 | 37 | El siguiente resultado, consecuencia geométrica del teorema anterior,, hace referencia a los triángulos *pitagóricos*, esto es, a los triángulos rectángulos cuyos lados tienen longitudes enteras. ### **15.5.3. Teorema** El radio de la circunferencia inscrita en un triángulo pitagórico es siempre un número natural. **Demostración** Si x, y, z son los lados del triángulo, donde z es la hipotenusa, entonces x² + y² = z² Si unimos el centro de la circunferencia inscrita con los tres vértices del triángulo, éste queda subdividido en tres triángulos T₁, T₂ y T₃. Obviamente, el área del triángulo de partida es la suma de las áreas de los T_i, i = 1,2,3, es decir, llamando r al radio de la circunferencia inscrita: ¹/₂xy = ¹/₂xr + ¹/₂yr + ¹/₂zr = r(x + y + z) ⇒ r = ^xy/_x+y+z Por el teorema anterior, las soluciones naturales de la ecuación pitagórica son de la forma: x = 2αλμ, y = a(λ² – μ²), z = α(λ² + μ²) donde a es cualquier natural y λ y μ son dos naturales de distinta paridad tales que λ> μ y mcd(λ, μ) = 1. Resulta así, r = ^{2αλμα (λ² - μ²)}/_{2αλμ + α (λ² - μ²) + αι} = ^{2α²λμ (λ + μ) (λ - μ)}/_{2αλ (λ + μ)} = αμ (λ - μ) que es un número natural. # **15.6. La Ecuación xⁿ + yⁿ = zⁿ: El último Teorema de Fermat** En el Teorema anterior hemos encontrado todas las soluciones de la ecuación pitagórica x² + y² = z². Pierre de Fermat (1601-1665) abordó el problema más general de buscar las soluciones enteras de la ecuación xⁿ + yⁿ = zⁿ para n> 2 y manifestó lo que se ha conocido desde entonces como Conjetura de Fermat o Último Teorema de Fermat: ### **15.6.1. Ultimo Teorema de Fermat** Si n>2, la ecuación xⁿ + yⁿ = zⁿ no tiene soluciones naturales. Fermat dijo tener una "demostración maravillosa de este resultado, pero no lo bastante breve para contenerla en el estrecho margen de la Aritmética de Diofanto. Nunca se encontró tal demostración y todos los intentos realizados en los tres siglos siguientes a la muerte de Fermat, tanto de encontrar una demostración de la veracidad de la conjetura, como de encontrar un caso que lo contradijera, resultaron fallidos. En los años 80, Faltings probó que el conjunto de soluciones de la ecuación es finito, y en los 90, Andrew Wiles presentó ante la comunidad matemática una demostración de la Conjetura apoyada en la teoría de curvas elípticas y formas modulares. ## **BIBLIOGRAFÍA** - Burton, David M. *Elementary Number Theory*. McGraw-Hill - Rosen, Kenneth. *Elementary Number Theory and Its Applications.* Addison Wesley Longman.