Autor Tema: Máximo común divisor

0 Usuarios y 1 Visitante están viendo este tema.

12 Abril, 2008, 01:34 am
Leído 1802 veces

Springer

  • $$\Large \color{#5e8d56}\pi\,\pi\,\pi$$
  • Mensajes: 127
  • Karma: +0/-0
  • Sexo: Masculino
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.

12 Abril, 2008, 10:30 pm
Respuesta #1

almendra

  • $$\Large \color{#c88359}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 614
  • Karma: +0/-0
  • Sexo: Femenino
Hola.

Hasta ahí vas bien.

Cuando \( n+1 \) es impar, efectivamente el mcd es 1 y para expresarlo como combinación lineal es así:

Primer paso: dividís \( n^2+1 \) por n+1: te da cociente n-1 y resto \( 2 \).   Esto te permite escribir \( 2=(n^2+1)-(n+1)(n-1) \)  (*).
 
Segundo paso: dividís \( n+1 \) por 2: esto da cociente \( \displaystyle\frac{n}{2} \) y resto 1.  Entonces escribís \( 1=  (n+1) - 2 \displaystyle\frac{n}{2}  \)    (**). Fijate que acá, como \( n+1 \) es impar, entonces \( n \) es par, o sea que \( \displaystyle\frac{n}{2} \) es entero.

Ahora, lo que te queda es reemplazar el 2 que aparece en la expresión   (**) por la expresión (*) y operar, agrupando por un lado los términos que tienen \( n+1 \)  y  por otro los que tienen \( n^2+1 \) y así obtendrás la combinación lineal buscada.


13 Abril, 2008, 03:03 am
Respuesta #2

Springer

  • $$\Large \color{#5e8d56}\pi\,\pi\,\pi$$
  • Mensajes: 127
  • Karma: +0/-0
  • Sexo: Masculino
Gracias.

Había probado de esa manera, pero me resultaba dudoso por tener una fracción, pero tu aclaración me vino bárbaro.

19 Agosto, 2008, 08:03 pm
Respuesta #3

bepro

  • $$\Large \color{#5e8d56}\pi\,\pi\,\pi$$
  • Mensajes: 331
  • Karma: +0/-0
  • Sexo: Masculino
    • GENERALIZACION DE LA REGLA DE RUFFINI
Un método más fácil es este:\( n^2+1=\left(n+1-1\right)^2+1=\left(n+1\right)^2-2\left(n+1\right)+2 \)por tanto para que exista m.c.d. n+1 debe de dividir a 2, es decir que n=1.
Saludos