3.6 Ejercicios

Ejercicio\(\PageIndex{1}\)

¿Cuál de las siguientes ecuaciones tiene soluciones enteras?

1. \(1137 = 69x + 39y\).
2. \(1138 = 69x + 39y\).
3. \(-64 = 147x + 84y\).
4. \(-63 = 147x + 84y\).

Ejercicio\(\PageIndex{2}\)

Que\(l\) sea la línea en\(\mathbb{R}^2\) dada por\(y = \rho x\), donde\(\rho \in \mathbb{R}\).

1. Demostrar que\(l\) se cruza\(\mathbb{Z}^2\) si y sólo si\(\rho\) es racional.
2. Dado un racional\(\rho > 0\), encontrar la intersección de\(l\) con\(\mathbb{Z}^2\). (Pista: establecer\(\rho = r_{1}\) y usar la Proposición 3.5.)

Ejercicio\(\PageIndex{3}\)

Aplica el algoritmo euclidiano para encontrar el divisor más común de los siguientes pares numéricos. (Pista: reemplace los números negativos por los positivos. Para el algoritmo de división aplicado a estos pares, ver ejercicio 2.1)

1. \(110, 7\).
2. \(51, -30\).
3. \(-138 , 24\).
4. \(272 , 119\).
5. \(2378 , 1769\).
6. \(270 , 175, 560\).

Ejercicio\(\PageIndex{4}\)

Este problema fue tomado (y reformulado) de [1].

1. Mosaico a\(188\) por\(158\) rectángulo por cuadrados usando lo que se llama un algoritmo codicioso. El primer cuadrado es\(158\) por\(158\). El rectángulo restante es\(158\) por\(30\). Ahora la elección óptima es de cinco\(30\) por\(30\) cuadrados. Lo que queda es un\(30\) por\(8\) rectángulo, y así sucesivamente. Explique cómo se trata de una visualización de la ecuación (3.3).
2. Considere la ecuación (3.1) o (3.2) y use a) para mostrar eso\[r_{1}r_{2} = \sum_{i=2}^{n} q_{i} r_{i}^2 \nonumber\] (Pista: asuma que\(r_{1} > r_{2} > 0, r_{n} \ne 0\), y\(r_{n+1} = 0\).)

Ejercicio\(\PageIndex{5}\)

Determinar si las siguientes ecuaciones diofantinas admiten una solución para\(x\) y\(y\). En caso afirmativo, encuentra una solución (particular). (Pista: Utilice uno de los algoritmos de la Sección 3.2.)

1. \(110x+7y = 13\).
2. \(110x+7y = 5\).
3. \(51x-30y = 6\).
4. \(51x-30y = 7\).
5. \(-138x+24y = 7\).
6. \(-138x + 24y = 6\).
7. \(272x + 119y = 54\).
8. \(272x + 119y = 17\).
9. \(2378x + 1769y = 300\).
10. \(2378x + 1769y = 57\).
11. \(270x + 175, 560y = 170\).
12. \(270x + 175, 560y = 150\).

Ejercicio\(\PageIndex{6}\)

Encuentre las soluciones para\(x\) y\(y\) de las siguientes ecuaciones diofantinas (homogéneas). En caso afirmativo, encuentra una solución (particular). (Pista: Utilice uno de los algoritmos de la Sección 3.2.)

1. \(110x+7y = 0\).
2. \(51x-30y = 0\).
3. \(-138x + 24y = 0\).
4. \(272x + 119y = 0\).
5. \(2378x + 1769y = 0\).
6. \(270x + 175, 560y = 0\).

Ejercicio\(\PageIndex{7}\)

Encuentre todas las soluciones para\(x\) y\(y\) en todos los problemas del ejercicio 3.5 que admitan una solución.

Ejercicio\(\PageIndex{8}\)

Utilizar el Corolario 3.11 para expresar los restos sucesivos\(r_{i}\) en cada uno de los ítems del ejercicio 3.3 como\(r_{1}x_{i}+r_{2}y_{i}\).

Ejercicio\(\PageIndex{9}\)

Utilizar el Corolario 3.12 para expresar\(x_{i}\) y\(y_{i}\) en los restos sucesivos\(r_{i}\) en cada uno de los ítems del ejercicio 3.3.

Ejercicio\(\PageIndex{10}\)

Considere la línea\(l\) en\(\mathbb{R}\) definida por\(l(\xi) = \begin{pmatrix} {r_{1}}\\ {r_{2}}\\ {r_{3}} \end{pmatrix}\xi\), where\(\xi \in \mathbb{R}\) y the\(r_{i}\) are enteros.

1. Demostrar que\(l(\xi) \in \mathbb{Z}^3 \backslash \{\vec{0}\}\) si y sólo si\(\xi = \frac{t}{\gcd(r_{1}, r_{2}, r_{3})}\) y\(t \in \mathbb{Z}\).
2. Demostrar que esto implica que si alguno de los\(r_{i}\) es irracional, entonces l no tiene puntos distintos de cero en común con\(\mathbb{Z}^3\).

Ejercicio\(\PageIndex{11}\)

Para este ejercicio, ver ejercicios 2.2 y 2.3. Dados tres polinomios\(p_{1}\) y\(p_{2}\) con coeficientes en\(\mathbb{Q}, \mathbb{R}\), o\(\mathbb{C}\). Definir\(\gcd(p_{1}, p_{2})\) como el polinomio de grado más alto que es un divisor de ambos\(p_{1}\) y\(p_{2}\). (Comentario: si haces esto con mucho cuidado, te darás cuenta de que en este problema realmente necesitas considerar clases de equivalencia de polinomios, en el sentido de que dos polinomios\(p\) y\(q\) son equivalentes si hay una constante distinta de cero\(c \in \mathbb{R}\) tal que\(p = cq\). Si bien no estamos persiguiendo los detalles aquí, es bueno tener esto en el fondo de tu mente.)

1. Describir un algoritmo basado en el algoritmo de división para polinomios para determinar el mayor divisor común\(d(x)\) de\(p_{1}(x)\) y\(p_{2}(x)\). (Pista: consulte el algoritmo euclidiano de la Sección 3.1. Para ver cómo aplicar el algoritmo de división a polinomios, ver ejercicio 2.2.)
2. Dar un criterio necesario y suficiente para la existencia de dos polinomios\(g(x)\) y\(h(x)\) satisfactorios\[p_{1}(x)g(x)+p_{2}(x)h(x) = d(x) \nonumber\] (Pista: lo mismo que el lema de Be ́zout.)
3. Aplicar el truco de la resolución “hacia atrás” en la Sección 3.2 para determinar un algoritmo encontrar polinomios\(g(x)\) y\(h(x)\) satisfacer\[p_{1}(x)g(x)+p_{2}(x)h(x) = d(x) \nonumber\] dónde ahora\(d = \gcd(p_{1}, p_{2})\). Esta es la solución particular.
4. Encuentre la solución general de\[p_{1}(x)g(x)+p_{2}(x)h(x) = 0 \nonumber\] (Pista: ver Proposición 3.5.)
5. Encuentra la solución general de\[p_{1}(x)g(x)+p_{2}(x)h(x) = e(x) \nonumber\] donde ahora\(e\) es un polinomio tiempos\(\gcd(p_{1}, p_{2})\). (Pista: ver Corolario 3.10.)
6. Aplicar lo anterior a\(p_{1}(x) = x^7-x^2+1, p_{2}(x) = x^3+x^2\), y\(e(x) = 2-x\). (Pista: enumeramos los pasos del algoritmo euclidiano:

\[(x^7-x^2+1) = (x^3+x^2)(x^4-x^3+x^2-x+1)+ (-2x^2+1) \nonumber\]

\[(x^3+x^2) = (-2x^2+1)(-\frac{1}{2}x-\frac{1}{2})+(\frac{1}{2}x+\frac{1}{2}) \nonumber\]

\[(-2x^2+1) = (\frac{1}{2}x+\frac{1}{2})(-4x+4)+(-1) \nonumber\]

\[(\frac{1}{2}x+\frac{1}{2}) = (-1)(-\frac{1}{2}x-\frac{1}{2}) \nonumber\]

Así\(\gcd(p_{1}, p_{2}) = 1\), o en otras palabras,\(p_{1}(x)\) y\(p_{2}(x)\) son relativamente primos.)

Ejercicio\(\PageIndex{12}\)

Dejar\(p(x)\) ser un polinomio y\(p′(x)\) su derivado.

1. Mostrar que si\(p(x)\) tiene una raíz múltiple\(\lambda\) de orden\(k > 1\), entonces\(p′(x)\) tiene esa misma raíz de orden\(k-1\). (Pista: Diferenciar\(p(x) = h(x)(x-\lambda)^k \).)
2. Utilice el ejercicio 3.11, para dar un algoritmo para encontrar un polinomio\(q(x)\) que tenga las mismas raíces que\(p(x)\), pero todas las raíces son simples (es decir, no múltiples raíces). (Pista: necesitas dividir\(p\) por\(\gcd(p, p′)\).)

Teorema 3.13 (Teorema Fundamental del Álgebra)

Un polinomio en\(\mathbb{C}[x]\) (el conjunto de polinomios con coeficientes complejos) de grado\(d \ge 1\) tiene\(d\) raíces exactamente, contando multiplicidad.

Ejercicio\(\PageIndex{13}\)

Supongamos que cada polinomio\(f\) de grado\(d \ge 1\) tiene al menos\(1\) raíz, probar el teorema fundamental del álgebra. (Pista: deja\(\rho\) ser una raíz y usa el algoritmo de división para escribir\(f(x) = (x-\rho)q(x)+r\) donde\(r\) tiene grado\(0\).)

Ejercicio\(\PageIndex{14}\)

Dejar\(f\) y\(g\) ser polinomios adentro\(\mathbb{Q}[x]\) con root\(\rho\) y supongamos que eso\(g\) es mínimo (Definición 1.13). Muéstrale eso\(g | f\). (Pista: utilizar el algoritmo de división de los ejercicios 2.2 y 2.3 para escribir\(f(x) = g(x)q(x)+r(x)\) donde\(r\) tiene grado menor que\(g\).)

Definición 3.14

La secuencia\(\{F_{i}\}^{\infty}_{i=0}\) de números de Fibonacci\(F_{i}\) se define de la siguiente manera

\[\begin{array} {ccc} {F_{0} = 0,}&{F_{1} = 1,}&{\forall i > 1 : F_{i+1} = F_{i}+F_{i-1}} \nonumber \end{array}\]

Ejercicio\(\PageIndex{15}\)

Denotar la media dorada, o\(\frac{1+\sqrt{5}}{2} \approx 1.618\), por\(g\).

1. Demostrar eso\(g^2 = g+1\) y así\(g^{n+1} = g^n +g^{n-1}\).
2. Demuestre eso\(F_{3} \ge g^1\) y\(F_{2} \ge g^0\).
3. Usa la inducción para mostrar eso\(F_{n+2} \ge g^{n}\) para\(n > 0\).
4. Usa el hecho de que\(5 \log_{10} \frac{1+\sqrt{5}}{2} \approx 1.045\), para demostrarlo\(F_{5k+2} > 10^k\) para\(k \ge 0\).

Ejercicio\(\PageIndex{16}\)

Considere las ecuaciones en (3.1) y asuma que\(r_{n+2} = 0\) y\(r_{n+1} > 0\).

1. Demuestre eso\(r_{n+1} \ge F_{2} = 1\) y\(r_{n} \ge F_{3} = 2\). (Pista:\(r(i)\) está aumentando estrictamente.)
2. Muéstrale eso\(r_{1} \ge F_{n+2}\).
3. Supongamos\(r_{1}\) y\(r_{2}\) en\(\mathbb{N}\) y\(\mbox{max} \{r_{1}, r_{2}\} < F_{n+2}\). Mostrar que el Algoritmo Euclidiana para calcular\(\gcd (r_{1}, r_{2})\) toma como máximo\(n-1\) iteraciones del algoritmo de división.

Ejercicio\(\PageIndex{17}\)

Usa los ejercicios 3.15 y 3.16 para mostrar que el Algoritmo Euclideano para calcular\(\gcd(r_{1}, r_{2})\) toma como máximo\(5k-1\) itera donde\(k\) está el número de decimales de\(\mbox{max}\{r_{1}, r_{2}\}\). (Esto se conoce como teorema de Lame ́.)

Ejercicio\(\PageIndex{18}\)

1. Escribe los números\(287\),\(513\), y\(999\) en base\(2\)\(3\), y\(7\), usando el algoritmo de división. No utilice un dispositivo de cálculo. (Pista: comenzar con base\(10\). Por ejemplo, de\[287 = 28 \cdot 10+7 \nonumber\]\[28 = 2 \cdot 10+8 \nonumber\]\[2 = 0 \cdot 10+2 \nonumber\] ahí que el número de en base\(10\) sea\(2 \cdot 10^2+8 \cdot 10^1+3 \cdot 10^0\).)
2. Demostrar que escribir\(n\) en base\(b\) toma sobre\(\mbox{log}_{b} n\) divisiones.

Ejercicio\(\PageIndex{19}\)

Supongamos que\(\{b_{i}\}_{i=1}^{n}\) son enteros positivos tales que\(\gcd (b_{i}, b_{j}) = 1\) para\(i \ne j\). Queremos saber todo lo\(z\) que satisfaga

\[\begin{array} {ccc} {z = b_{i} c_{i}}&{for}&{i \in \{1, \cdots, m\}} \nonumber \end{array}\]

1. Establecer\(B = \prod_{i=1}^{n} b_{i}\) y mostrar que el problema homogéneo es resuelto por\[z = _{B} 0 \nonumber\] (Pista: use corolario 3.10)
2. Comprobar que\[z = \sum_{i=1}^{n} \frac{B}{b_{i}} x_{i} c_{i} \nonumber\] es una solución particular.
3. Encuentra la solución general\[z = B \sum_{i=1}^{n} \frac{B}{b_{i}} x_{i} c_{i} \nonumber\] Esto se conoce como el resto chino Theroem.

Ejercicio\(\PageIndex{20}\)

Usa el ejercicio 3.19 para resolver

\[z = _{2} 1 \nonumber\]

\[z = _{3} 2 \nonumber\]

\[z = _{5} 3 \nonumber\]

\[z = _{7} 5 \nonumber\]

Ejercicio\(\PageIndex{21}\)

Asumir\(\gcd (F_{n}, F_{n+1}) = 1\). Usa el Ejercicio 3.19 para resolver:

\[z = _{F_{n}} F_{n-1} \nonumber\]

\[z = _{F_{n+1}} F_{n} \nonumber\]

donde\(F_{n}\) están los números Fibonacci de la Definición 3.14.

Ejercicio\(\PageIndex{22}\) (The Chinese remainder theorem generalized)

Supongamos que\(\{b_{i}\}_{i=1}^{n}\) son enteros positivos. Queremos saber todo lo\(z\) que satisfaga

\[\begin{array} {ccc} {z = b_{i} c_{i}}&{for}&{i \in \{1, \cdots, m\}} \nonumber \end{array}\]

1. Establecer\(B = \mbox{lcm} (b_{1}, b_{2}, \cdots, b_{n})\) y mostrar que el problema homogéneo es resuelto por\[z = _{B} 0 \nonumber\]
2. Demostrar que si hay una solución en particular entonces\[\forall i \ne j : c_{i} = _{\gcd (b_{i},b_{j})} c_{j} \nonumber\]
3. Formular la solución general cuando se mantenga la condición en b).

Ejercicio\(\PageIndex{23}\)

Asumir\(\gcd (F_{n}, F_{n+1}) = 1\). Usa el Ejercicio 3.21 para resolver:

\[z = _{6} 15 \nonumber\]

\[z = _{10} 6 \nonumber\]

\[z = _{15} 10 \nonumber\]

Véase también ejercicio 2.6.