de cada par de enteros en los ejercicios 1 al 10.
1. 60, 90
3. 220, 1400
4. 315, 825
5. 20, 40
6. 331, 993
7. 2091, 4807
8. 2475, 32670
9. 67942, 4209
10. 490256, 337
11. Para cada par de números a, b en los ejercicios 1 al 10, encuentre
enteros s y t tales que sa + tb = mcd(a, b).
12. Encuentre dos enteros a y b, cada uno menor que 100, que maximicen
el número de iteraciones del ciclo “while” del algoritmo
5.3.3.
13. Demuestre que el algoritmo 5.3.3 encuentra correctamente el mcd(
a, b) aun cuando se eliminen las líneas 3 y 4.
14. Escriba una versión recursiva del algoritmo euclidiano. Pruebe
que su algoritmo es correcto.
15. Si a y b son enteros positivos, demuestre que mcd(a, b) = mcd(a,
a + b).
16. Demuestre que si a > b ≥ 0, entonces
mcd(a, b) = mcd(a – b, b).
17. Con base en el ejercicio 16, escriba un algoritmo que calcule el
máximo común divisor de dos enteros no negativos a y b, ambos
diferentes de cero, que use la resta pero no las operaciones de
módulo.
18. ¿Cuántas restas requiere el algoritmo del ejercicio 17 en el peor
caso para números en el intervalo de 0 a m?
19. Amplíe las tablas 5.3.1 y 5.3.2 al intervalo de 0 a 21.
20. ¿Exactamente cuántas operaciones de módulo requiere el algoritmo
euclidiano en el peor caso para números entre 0 y 1,000,000?
21. Pruebe que cuando el par fn+2, fn+1 se introduce en el algoritmo
euclidiano, n ≥ 1, se requieren exactamente n operaciones de
módulo.
22. Demuestre que para cualquier entero k > 1, el número de operaciones
de módulo requeridas por el algoritmo euclidiano para calcular
el mcd(a, b) es el mismo que el número de operaciones de
módulo requeridas para calcular mcd(ka, kb).
23. Demuestre que el mcd(fn, fn+1) = 1, n ≥ 1.
24. Demuestre que si p es un número primo, a y b son enteros positivos
y p|ab, entonces p|a o p|b.
25. Dé un ejemplo de enteros positivos p, a y b donde p|ab, p /\ a y
p b.
26. Sean m y n enteros positivos. Sea f la función de
X = {0,1, . . . , m – 1}
en X definida por
f (x) = nx mod m.
Pruebe que f es uno a uno y sobre si y sólo si mcd(m, n) = 1.
Los ejercicios 27 al 31 muestran otra manera de probar que si a y b son
enteros no negativos, ambos diferentes de cero, existen enteros s y t tales
que
mcd(a, b) = sa + tb.
Sin embargo, a diferencia del algoritmo euclidiano, esta demostración
no conduce a una técnica para calcular s y t.
27. Sea
X = {sa + tb|sa + tb > 0 y s y t son enteros}.
Demuestre que X es no vacío.
28. Demuestre que X tiene un elemento menor. Denote por g el elemento
menor.
a g.
30. Demuestre que g es un divisor común de a y b. Sugerencia: Suponga
que g no divide a a. Entonces a = qg + r, 0 < r < g. Obtenga
una contradicción demostrando que r ∈ X.
31. Demuestre que g es el máximo común divisor de a y b.
En los ejercicios 32 al 38, demuestre que el mcd(n, φ) = 1 y encuentre
el inverso s de n módulo φ que satisface 0 < s < φ.
32. n = 2, φ = 3
33. n = 1, φ = 47
34. n = 7, φ = 20
35. n = 11, φ = 47
36. n = 50, φ = 231
37. n = 100, φ = 231
38. n = 100, φ = 243
39. Demuestre que 6 no tiene inverso módulo 15. ¿Contradice esto el
resultado que precede al ejemplo 5.3.9? Explique su respuesta.
40. Demuestre que n > 0 tiene un inverso módulo φ > 1 si y sólo si
mcd(n, φ) = 1.
