Hola, gente.
En un problema, se pedía hallar el máximo común divisor entre \( n^2+1 \) y \( n+1 \); es decir, \( (n^2+1:n+1) \), y escribirlo como combinación lineal entera.
Para resolverlo, utilicé el algoritmo de Euclides, de la siguiente manera:
Primer paso: \( a_0=n^2+1 \) \( b_0=n+1 \)
Segundo paso: \( a_1=n+1 \) \( b_1=r_{n+1}(n^2+1)=2 \) \( 2=(n^2+1)-(n+1)(n-1) \)
En el siguiente paso es donde me trabo, porque:
\( a_2=2 \) \( b_2=r_2(n+1) \)
Pero ahora tenemos dos posibilidades:
* \( n+1\mbox{ es par}\Rightarrow b_2=0 \), con lo que \( (n^2+1:n+1)=2 \), y estaría resuelto el problema.
* \( n+1\mbox{ es impar}\Rightarrow b_2=1 \), pero esta posibilidad no me parece clara porque no puedo encontrar manera de expresar \( 1 \) como combinación lineal de \( n^2+1 \) y \( n+1 \).
Espero que alguien me haya entendido y tenga alguna idea de cómo seguir.