Máximo común divisor

Estimado: Junto con saludarle cordialmente le escribo con el fin de solicitar su ayuda con respecto al siguiente problema, cualquier respuesta será un gran aporte.

Sea An=100+n^2 y Dn= máximo común divisor (An, An+1). Calcular Dn para cada n perteneciente a los naturales.

Observación: con respecto a la escritura considerar lo siguiente:

An= a sub n

Dn= d sub n

An+1= a sub (n+1)

es decir todas las n son sub-indice.

Respuesta
1

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 :)

Si, cuando lo de dentro del paréntesis es par, el mcd es 401. Y cuando no el mcd es 1. Pero no lo es por ser par lo del paréntesis, en realidad debería ser múltiplo de 4 para no caer en el absurdo. Sin embargo la forma que tiene la expresión del paréntesis hace que ser par equivalga a ser múltiplo de 4, vamos a demostrarlo.

Ya habíamos visto que para que el paréntesis sea par m debía ser impar, luego:

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

1 + 401m^2 - 2m = 1 +401(4r^2 + 4r + 1) - 4r - 2 = 4·401r^2 + 4·401r + 400

que es múltiplo de 4 porque lo son sus tres sumandos.

Y al ser múltiplo de 4 era cuando se deducía que An =  401(1 + 401m^2 - 2m)/4 era múltiplo de 401 al igual que lo era 2n+1

Y por lo tanto cuando 2n+1 sea múltiplo de 401, el mcd es 401.

Y 2n+1 es múltiplo de 401 cuando n tiene la forma

n = 200+ 401s con s€NU{0]

Para esos números el mcd es 401 para el resto es 1.

Espero que lo vayas entendiendo, no es muy sencillo pero tampoco tan complicado.

Añade tu respuesta

Haz clic para o

Más respuestas relacionadas