Si $a \mid m$ y $(a + 1) \mid m$ , demuestre que $a(a + 1) | m$ .

Question

¿Puede alguien ayudarme? No puedo encontrar las reglas de divisibilidad adecuadas para mostrar esto:

Si $a \mid m$ y $(a + 1) \mid m$ entonces $a(a + 1) \mid m$ .

Answer 1

Las otras respuestas lo sitúan en un contexto general, pero en este ejemplo se puede puede ser absolutamente explícito. Si $a\mid m$ y $(a+1)\mid m$ entonces hay enteros $r$ y $s$ tal que $$m=ar=(a+1)s.$$ Entonces $$a(a+1)(r-s)=(a+1)[ar]-a[(a+1)s]=(a+1)m-am=m.$$ Como $r-s$ es un número entero, entonces $a(a+1)\mid m$ .

Answer 2

Si $\rm\,\ a\mid m,\ a\!+\!1\mid m\ \,$ entonces se deduce que $\rm\ \, \color{#90f}{a(a\!+\!1)\mid m}$

${\bf Proof}\rm\quad\displaystyle \frac{m}{a},\; \frac{m}{a+1}\in\mathbb{Z} \ \,\Rightarrow\,\ \frac{m}{a} - \frac{m}{a\!+\!1} \; = \;\color{#90f}{\frac{m}{a(a\!+\!1)} \in \mathbb Z}.\quad$ QED

${\bf Remark}\rm\ \, \text{More generally, if }\, \color{#c00}{n = bc \:\!-\:\! ad} \;$ es una combinación lineal de $\rm\, a, b\, $ entonces

$\rm\text{we have}\quad\,\ \displaystyle \frac{m}{a},\; \frac{m}{b}\in\mathbb{Z} \;\;\Rightarrow\;\; \frac{m}{a}\frac{\color{#c00}{bc}}{b} - \frac{\color{#c00}{ad}}{a}\frac{m}{b} = \frac{m\:\!\color{#c00}n}{a\:\!b} \in \mathbb Z$

Por Bezout, $\rm\, \color{#c00}{n = \gcd(a,b)}\, $ es el menos combinación lineal positiva, por lo que lo anterior da como resultado

$\rm\qquad\qquad a,b\mid m \;\Rightarrow\; ab\mid m\;gcd(a,b) \;\Rightarrow\; \mathfrak{m}_{a,b}\!\mid m\ \ $ para $\ \ \rm \mathfrak{m}_{a,b} := \dfrac{ab}{\gcd(a,b)}$

es decir $ $ todo múltiplo común $\rm\, m\,$ de $\,\rm a,b\,$ es un múltiplo de $\;\rm \mathfrak{m}_{a,b},\,$ así que $\rm\, \color{#0a0}{\mathfrak{m}_{a,b}\le m}.\,$ Pero $\rm\,\mathfrak{m}_{a,b}\,$ también es un común múltiple, es decir $\rm\ a,b\mid \mathfrak{m}_{a,b}\,$ a saber $\displaystyle \,\rm \frac{\mathfrak{m}_{a,b}}{a} = \;\frac{a}{a}\frac{b}{gcd(a,b)}\in\mathbb Z\,$ $\,\Rightarrow\,$ $\rm\, a\mid \frak{m}_{a,b},\,$ y $\,\rm b\mid \mathfrak{m}_{a,b}\,$ por simetría. Así, $\,\rm \mathfrak{m}_{a,b} = lcm(a,b)\,$ es el $\rm\color{#0a0}{least}$ múltiplo común de $\rm\,a,b.\,$ De hecho, hemos demostrado la afirmación más fuerte de que es un múltiplo común que es divisibilidad-mínima es decir, que divide todos los múltiplos comunes. Esta es la definición general de LCM en un dominio arbitrario (anillo sin divisores de cero), es decir, tenemos lo siguiente universal definiciones duales de LCM y GCD, que esencialmente dice que LCM y GCD son $\,\sup\,$ & $\,\inf\,$ en el poset inducido por el orden de divisibilidad $\,a\preceq b\!\iff\! a\mid b$ .

Definición de LCM $\ \ $ Si $\quad\rm a,b\mid c\,\iff\; d\mid c \ \ \,$ entonces $\rm\ d\approx lcm(a,b)$
comparar: $\, $ Def de $\rm\,\cap\ \ \,$ Si $\rm\ \ \ a,b\supset c\iff d\supset c\,\ $ entonces $\,\ \rm d = a\cap b$

Definición de GCD $\ \ $ Si $\quad\rm c\mid a,b \;\iff\; c\mid d \,\ $ entonces $\,\ \rm d \approx \gcd(a,b)$
comparar: $\, $ Def de $\rm\,\cup\ \ \,$ Si $\rm\ \ \ c\supset a,b\iff c\supset d\,\ $ entonces $\,\ \rm d = a\cup b$

Nota $\;\rm a,b\mid [a,b] \;$ sigue poniendo $\;\rm c = [a,b] \;$ en la definición. $ $ Dually $\;\rm (a,b)\mid a,b$ .

Por encima de $\rm\,d\approx e\,$ significa $\rm\,d,e\,$ son asociados, es decir $\rm\,d\mid e\mid d\,$ (de forma equivalente $\rm\,d = u\!\: e\,$ para $\,\rm u\,$ una unidad = invertible). En los dominios generales los gcds se definen sólo hasta los asociados (múltiplos de la unidad), pero a menudo podemos normalizar para deshacerse de dichos factores unitarios, por ejemplo, normalizando el gcd para que sea $\ge 0$ en $\Bbb Z,\,$ y hacerla mónica para polinomios sobre un campo, por ejemplo, ver ici y ici .

Estas definiciones universales permiten realizar pruebas unificadas de las dos direcciones de las flechas, por ejemplo

Teorema $\rm\;\; (a,b) = ab/[a,b] \;\;$ si $\;\rm\ [a,b] \;$ existe.

Prueba : $\rm\quad d\mid a,b \iff a,b\mid ab/d \iff [a,b]\mid ab/d \iff\ d\mid ab/[a,b] \quad$ QED

La concisión de la prueba surge al explotar al máximo la $\:\!(\!\!\iff\!\!)\:\!$ definición de LCM, GCD. La prueba anterior lleva implícita una dualidad cofactorial innata. Llevada al primer plano, aclara la dualidad LCM, GCD (análoga a las leyes de DeMorgan), por ejemplo, véase ici y aquí.

Por el teorema, los GCDs existen si los LCMs existen. Pero los múltiplos comunes comprenden claramente un ideal, ya que son cerrados bajo la sustracción y la multiplicación por cualquier elemento del anillo. Por lo tanto, en un PID el generador de un ideal de múltiplos comunes es claramente un LCM. En los dominios euclidianos esto se puede demostrar directamente por un simple descenso, por ejemplo en $\:\mathbb Z \;$ tenemos la siguiente prueba de nivel de bachillerato de la existencia de LCMs (y, por lo tanto, de GCDs), después de observar el conjunto $\rm M$ de los múltiplos comunes de $\rm a,b$ es cerrado bajo la sustracción y contiene $\:\rm ab \ne 0\:$ :

Lema $\ $ Si $\;\rm M\subset\mathbb Z \;$ es cerrado bajo la sustracción y $\rm M$ contiene un elemento no nulo $\rm\,k,\,$ entonces $\rm M \:$ tiene un elemento positivo y el menor elemento positivo de $\;\rm M$ divide cada elemento.

Prueba $\, $ Nota $\rm\, k-k = 0\in M\,\Rightarrow\, 0-k = -k\in M, \;$ por lo tanto $\rm M$ contiene un elemento positivo. Sea $\rm\, m\,$ sea el elemento menos positivo de $\rm\, M.\,$ Desde $\,\rm m\mid n \iff m\mid -n, \;$ si algunos $\rm\, n\in M\,$ no es divisible por $\,\rm m\,$ entonces podemos suponer que $\,\rm n > 0,\,$ y el menos tal. Entonces $\rm\,M\,$ contiene $\rm\, n-m > 0\,$ tampoco es divisible por $\rm m,\,$ y más pequeño que $\rm n$ , la contrapartida de $\,\rm n.\ \ $ QED

Answer 3

No es de extrañar que te resulte difícil, porque va más allá de las reglas básicas de divisibilidad - más bien requiere algo que es esencialmente equivalente a la unicidad de la factorización de primos. [ Editar : En realidad este comentario es incorrecto -- como muestra la respuesta de Robin Chapman, es es es posible demostrarlo utilizando sólo las reglas de divisibilidad. En particular, es cierto en cualquier dominio integral].

Supongo que $a$ y $m$ son enteros positivos. La primera observación es que $a$ y $a+1$ son relativamente primos: es decir, no hay ningún número entero $d > 1$ --o, equivalentemente, ningún número primo-- que divida a ambos $a$ y $a+1$ , ya que entonces $d$ tendría que dividir $(a+1) - a = 1$ Así que $d = 1$ .

Ahora el paso clave: ya que $a$ divide $m$ podemos escribir $m = aM$ para algún número entero positivo $M$ . Así que $a+1$ divide $aM$ y es relativamente primo de $a$ . Reclamo que esto implica $a+1$ divide $M$ . Asumiendo esto, tenemos $M = (a+1)N$ , digamos, así que en conjunto

$m = aM = a(a+1)N$ Así que $a(a+1)$ divide $m$ .

La reclamación es un caso especial de:

Lemma de Euclides (generalizado): Sea $a,b,c$ sean enteros positivos. Supongamos que $a$ divide $bc$ y $a$ es relativamente primo de $b$ . Entonces $a$ divide $c$ .

Una prueba formal de esto requiere algo de trabajo. Véase, por ejemplo

http://en.wikipedia.org/wiki/Euclid's_lemma

En particular, demostrar esto es esencialmente tan difícil como demostrar la teorema fundamental de la aritmética .

Answer 4

Una ruta alternativa: Demostramos que, si $ax+by=1$ y $m$ es divisible por $a$ y $b$ entonces $m$ es divisible por $ab$ . (A continuación, aplique esto con $b=a+1$ , $x=-1$ y $y=1$ .)

Prueba: Dejemos que $m=ak=bl$ . Entonces $ab(xl+ky)=(ax+by)m=m$ . QED

La cuestión aquí es que la hipótesis $\exists_{x,y}: ax+by=1$ suele ser más fácil de usar que $GCD(a,b)=1$ . La equivalencia entre estos dos es básicamente equivalente a la factorización única, y a menudo se puede esquivar la factorización única averiguando cuál de estos dos se necesita realmente.