Máximo común divisor

Si d|a y d|b entonces d|(a-b). Que se lee, si d divide a a y d divide a b entonces d divide a (a-b).  En efecto (a-b)/d = a/d - b/d que es entero porque lo son los dos por suposición.

Llamaré d a Dn para mayor claridad

D es el máximo común divisor de

An = 100+n^2

An+1 =100+(n+1)^2 = 100 + n^2 + 2n +1

Luego si divide a los dos también divide a la diferencia

(An+1) - (An) = 2n + 1

Luego d divide a An=100+n^2 y a 2n+1.

Ahora ponemos An de esta forma

An = 100 + 200 n - 200n + n^2

Como d|(2n+1) ==>

d|100+200n  y para que An sea entero  ==>

d|(-200n+n^2)  ==>

d|n(n-200)  ==>

d|n o d|(n-200)

Si d|n entonces tomamos (2n+1))/d que es un entero por lo visto arriba

(2n+1)/d = 2n/d + 1/d = 2m + 1/d con m € Z ==> d=1

Si d|(n-200)==>

d|2n-400

como divide a 2n-400 y a 2n+1 también divide a la diferencia

2n+1 - (2n-400) = 401

Como 401 es primo significa que d =1 o d = 401

Supongamos que d = 401 ==>

2n+1 = 401m ==>

n = (401m-1)/2

An = 100+n^2 = 100+[(401m-1)^2] / 4 = [400 +(401m)^2 - 802m + 1] / 4 =

[401 + (401m)^2 - 802m] / 4 = 401(1 + 401m^2 - 2m)/4

Si m es impar lo del paréntesis es impar (los tres sumandos son impares) e indivisible por 4 con lo que An no es divisible por 401

Si m es par sucede lo mismo (un impar y dos pares dan impar) y An no es divisible por 401. Luego absurdo porque 401 era el máximo común divisor de An y 2n+1

Luego d no puede ser 401 y solo le queda como remedio ser 1.

Conclusión: el máximo común divisor de An y An+1 es 1.

Y eso es todo.

Hola:

Muchas gracias por responder, el desarrollo está muy bueno, pero tengo algunas dudas:

1) ¿de donde sale el m?

2) ¿cuando te refieres que m pertenece a los enteros quieres decir a los enteros positivos = naturales)

3) Al finalizar el desarrollo hay un error en la interpretación de lo que esta dentro del paréntesis, debido  a que lo que esta dentro del paréntesis es par si m es impar.

Esperando tu respuesta se despide atentamente Franunez

Al principio explicaba por que d dividía a (2n+1)

Cuando suponemos que d es 401 entonces 401 divide a 2n+1 luego tendremos

2n+1=401m con m entero

Y es entero positivo porque también lo es n por hipótesis y la cantidad de la izquierda resulta ser positiva entonces.

Es verdad, el paréntesis es par si m es impar.

Tomemos ese número m impar

m = 2r+1 con r € NU{0}

2n+1=401(2r+1)

n = (802r + 401 - 1)/2 = 401r + 200

An = 100 + (401r+200)^2 = 100+(401^2)r^2+401·400r + 40000 =

Calculamos aparte 40000 + 100 = 40100 = 401·100

An=401(401r^2 + 400r + 100)

Recuerdo que estamos calculando el mcd(An, 2n+1) que es el mismo que mcd(An, An+1)

Y ese mcd es 401 porque es factor común de ambos y no puede ser del tipo 401 por algo porque antes habiamos demostrado que d dividía a 401.

Lo he comprobado con el ordenador mediante este programa en Pascal:

program mcd100mascuadradosseguidos;
function mcd(a,b:integer):integer;
begin 
  if a<b then  
    if (b mod a) = 0 then 
      mcd := a 
    else 
      mcd := mcd(b mod a, a) 
  else  
    if (a mod b) = 0 then  
      mcd := b 
    else  
      mcd := mcd(a mod b, b)
end;
var i,m:integer;
begin 
  for i:=1 to 46000 do 
    begin 
      m := mcd(100+i*i, 100+(i+1)*(i+1));  
      if (m <> 1) then  
        begin  
          writeln(i,' ',m);  
          if (m <> 401) then 
            begin  
              writeln('CASO ESPECIAL'); readln;  
            end; 
        end; 
    end; 
  readln;
end.

 Y el resultado para esos 46000 primeros mcd ( no me deja probar con más más por que los cuadrados desbordaban el rango positivo de las variable integer de 16bits) es el previsto en la teoria que dice:

El mcd es 401 cuando n = 401r + 200 con r € NU{0}  o sea: 200, 601, 1002, 1403, 1804, etc. y es 1 en los demás casos

Y eso es todo, si tienes algunba otra duda o hay algo mal me lo comunicas.

OK, ¿entonces puedo concluir debido a que lo que esta dentro del paréntesis es par que 401 es el MCD y que también 1 es MCD?. Espero su respuesta. Muchas gracias :)