Si n es un número impar, ¿cómo pruebo que mcd (n, (n-1) / 2) = 1?

Answer 1

Si dos números tienen un MCD de 1, significa que no tienen factores en común, excepto 1. Intentemos ver esto en términos de factores.

Comencemos comparando [matemáticas] n-1 [/ matemáticas] y [matemáticas] n. [/ Matemáticas] Podrías ver fácilmente que su MCD es 1. ¿Por qué? Dos números consecutivos siempre no tienen factores comunes (excepto 1). Pruébelo con cualquier número [matemática] k [/ matemática], y verá que si [matemática] k [/ matemática] divide [matemática] n-1 [/ matemática], dejará un resto [matemática] 1 [/ math] para n, y si divide [math] n [/ math], dejará el resto [math] k-1 [/ math] para [math] n-1 [/ math].

Bien, ahora sabemos que [matemáticas] n-1 [/ matemáticas] y [matemáticas] n [/ matemáticas] no tienen factores comunes, ¿qué podemos decir sobre [matemáticas] \ frac {n-1} {2} [/ matemáticas]? Bueno, hemos tomado [matemáticas] n-1 [/ matemáticas] y acabamos de eliminar uno de sus factores (2). Obviamente no podemos tener más factores, ¡siempre tendremos menos factores! Por lo tanto, dado que [matemática] n-1 [/ matemática] y [matemática] n [/ matemática] no tenían factores comunes, [matemática] \ frac {n-1} {2} [/ matemática] y [matemática] n [ / math] tampoco tendrá factores.

Y como no tienen factores en común (excepto 1), el MCD ([matemáticas] n, \ frac {n-1} {2} [/ matemáticas]) = 1

Answer 2

n es impar, entonces n = 2k + 1 para algunos k. (n-1) / 2 es entonces igual a k. Entonces, tienes que demostrar que k y 2k + 1 no tienen divisores comunes. Pero esto es obvio (fx ya es el primer paso del algoritmo euclidiano para (2k + 1, k): 2k + 1 = 2 * k + 1, dejando 1 como mcd).

Answer 3

Observe que n-2 * (n-1) / 2 = n-n + 1 = 1, por lo que existen enteros (a saber, 1 y -2) de modo que la combinación lineal de n y (n-1) / 2 es igual a 1. Esto puede suceder si y solo si los dos números son coprimos, es decir, tienen mcd 1, ya que el mcd es siempre el elemento positivo más pequeño del conjunto de expansión de los enteros involucrados.

Si podemos encontrar enteros u y v tales que ua + vb = 1, entonces a y b son números coprimos, para cualquier número entero a y b.