Mostrar que $\gcd(7^{79}+5,7^{78}+3) = 4$

Question

Cómo puedo probar que $\gcd(7^{79}+5,7^{78}+3) = 4$ ? Esta fue una pregunta de un pasado en el examen, por lo que el ingenuo algoritmo de euclides no parece ser suficiente.

No estoy muy seguro de por dónde empezar con este.

Nota: Esta es la preparación del examen, no a la tarea.

Answer 1

Un primer paso, $7^{79}+5 - 7*(7^{78}+3) = -16$, que se obtiene de un largo camino. Sólo es necesario el estudio de los factores de 2 en los números.

Answer 2

Modulo el mcd: $\rm\ 7^{78}\ \equiv -3\ \Rightarrow\ 0\ \equiv\ 7^{79}+5\ \equiv\ 7(-3)+5\ \equiv -16\:,\ $ es decir, el mcd dvides $16\:$.

Ahora $\rm\ mod\ 8:\ 7^{78}+3\ \equiv\ (-1)^{78}+3\ \equiv\ 4\ \equiv\ (-1)^{79}+5\ \equiv\ 7^{79}+5\:,\ $ es decir $\ $ mcd $\rm\equiv 4\ (mod\ 8)$

Por lo tanto:$\ $ mcd $\rm = 4 + 8\ k\ $ divide $16\:$ implica $\rm\ k = 0\:,\ $ $\ $ mcd $ = 4\:$.

Observe cómo los cálculos se vuelven más intuitiva, trabajando en varias sortijas $\rm\ \mathbb Z/m\:.$ Haciendo nos permite reutilizar nuestro bien afilada intuición de la aritmética de las operaciones (anillo de leyes), frente a la mucho más engorroso $\ $ $\ $ mucho menos intuitiva de divisibilidad relación, es decir, de cálculo ecuacional álgebras es más simple que en el cálculo relacional de álgebras, así que cada vez que un problema se puede convertir de relacional para ecuacional se produce habitualmente una simplificación.

Answer 3

Desde $\gcd(a,b)=\gcd(a-b,b)$, $$\begin{align} \gcd(7^{79}+5,7^{78}+3) &=\gcd(7\cdot 7^{78}+5-7^{78}-3,7^{78}+3) \\ &=\gcd(6\cdot 7^{78}+2,7^{78}+3) \\ &=\gcd(6\cdot 7^{78}+2-7^{78}-3,7^{78}+3) \\ &=\gcd(5\cdot 7^{78}-1,7^{78}+3) \\ &\vdots \\ &=\gcd(7^{78}-13,7^{78}+3) \\ &=\gcd(7^{78}-13,7^{78}+3-7^{78}+13) \\ &=\gcd(7^{78}-13,16) \\ \end{align}$$

A partir de ahí, me gustaría determinar el resto al $7^{78}$ se divide entre el 16 y el uso que ver cómo $7^{78}-13$ compara a 16.