¿Por qué es $\gcd(a,b)=\gcd(b,r)$ al $a = qb + r$?

Question

Dado: $a = qb + r$

A continuación, se sostiene que $\gcd(a,b)=\gcd(b,r)$. Eso no suena lógico para mí. ¿Por qué es esto así?

---

Addendum al LePressentiment en 11/29/2013: (en el interés de http://meta.math.stackexchange.com/a/4110/53259 y evitar un duplicado)

¿Cuál es la intuición detrás de este resultado? Sólo reconozco la prueba y ejemplos único, debido a las propiedades algebraicas y definiciones formales; me gustaría aprehender el resultado de forma natural.

Answer 1

SUGERENCIA $\rm\ \ $ Si $\rm\ d\ |\ b\ $ $\rm\ d\ |\ q\ b + r\ \iff\ d\ |\ r\:.\ $ por lo Tanto $\rm\ \{b\:,\:q\ b+r\}\ $ $\rm\ \{b\:,\: r\}\ $ tienen el mismo conjunto de divisores comunes $\rm\:d\:,\:$ por lo tanto tienen el mismo mayor común divisor.

Modly: $\ $ si $\rm\ b\equiv 0\ $ $\rm\ q\ b+r\equiv 0\: \iff\: r\equiv 0\ \pmod{d}$

NOTA $\ $ El resultado tiene cierto porque las $\rm\:\mathbb Z\:$ constituye un sub-anillo de su fracción de campo $\rm\:\mathbb Q\:.\:$ Más en general, dado cualquier sub-anillo $\rm\:Z\:$ de un campo de $\rm\:F\:$ definimos la divisibilidad relativa a$\rm\ Z\ $$\rm\ x\ |\ y\ \iff\ y/x\in Z\:.\:$, Entonces la anterior prueba todavía funciona, ya que si $\rm\ q,\ b/d\ \in Z\ $ $\rm\ q\:(b/d) + r/d\in Z\ \iff\ r/d\in Z\:.\:$ En otras palabras, la costumbre de divisibilidad leyes a seguir, desde el hecho de que los anillos están cerrado bajo las operaciones de resta y multiplicación; de ser tan cerrado, $\rm\:Z\:$ sirve como un anillo de "enteros" para pruebas de divisibilidad.

Por ejemplo, para centrarse en el prime $2$ podemos ignorar todos los impares primos y definir una relación de divisibilidad por lo que el $\rm\ m\ |\ n\ $ si el poder de la $2$ $\rm\:m\:$ $\le$ que $\rm\:n\:$ o, equivalentemente, si $\rm\ n/m\ $ tiene impar denominador en términos mínimos. El conjunto de todas estas fracciones se forma un anillo $\rm\:Z\:$ $2$integral de las fracciones. Por otra parte, este anillo disfruta de paridad, de modo que los argumentos basados en pares/impares aritmética ir a través de. Ideas similares conducen a la poderosa local-global de las técnicas de reducción de la divisibilidad problemas de complicada "global" de los anillos de simple "local" anillos", donde la divisibilidad se decidió por la simple comparación de los poderes de un primo.

Answer 2

Si $d$ es un divisor de a $a$ e de $b$, luego $$ \begin{align} a & = dn, \\ b & = dm. \end{align} $$ Por lo $$a-b= dn-dm=d(n-m)= (d\cdot\text{something}).$$ Por lo $d$ es un divisor de a $a-b$.

Por lo tanto: Todos los divisores de a $a$ $b$ tienen en común son los divisores de $a-b$.

Si $d$ es un divisor de a $a$ e de $a-b$, luego $$ \begin{align} a & = dn, \\ a-b & = d\ell. \end{align} $$ Así $$ b=a-(a-b)=dn-d\ell=(d\cdot\text{algo}). $$ Por lo $d$ es un divisor de a $b$.

Por lo tanto: Todos los divisores de a $a$ $a-b$ tienen en común son los divisores de $b$.

Por lo tanto, el conjunto de todos los divisores comunes de a $a$ $b$ es el mismo que el conjunto de todos los divisores comunes de a$a$$a-b$.

Restando uno de los miembros de un par de los otros nunca altera el conjunto de todos los divisores comunes; por lo tanto, nunca se altera la $\gcd$.

Answer 3

Usted puede demostrar que para cualquier entero$d$, $d\; |\; a$ $d\; |\; b$ si y sólo si $d\; |\; b$$d\; |\; r$. En otras palabras, $a$ $b$ tienen exactamente la misma comunes divisores como $b$$r$. Por lo tanto $\gcd(a,b)$ es lo mismo que $\gcd(b,r)$.

Answer 4

Desde el conjunto de divisores comunes de a $a-b$ $b$ coincide con el conjunto de divisores comunes de a$a$$b$$\operatorname{gcd}(a,b)=\operatorname{gcd}(a-b,b)$. Si $a=qb+r$ donde$b>0$$0\leq r<b$, se puede aplicar esta igualdad de $q$ veces y obtener un $\operatorname{gcd}(a,b)=\operatorname{gcd}(r,b)$

Answer 5

Deje $A$ ser un anillo conmutativo. Para cualquier $a_1,\dots,a_n$ $A$ deje $(a_1,\dots,a_n)$ el ideal generado por el $a_i$.

Entonces, para cualquier $q,b,r$$A$, tenemos $$ (qb+r,b)=(b,r). $$ De hecho, $qb+r$$(b,r)$, e $r$$(qb+r,b)$.

EDIT. Estimado Kevin: Tu pregunta, creo que sería mejor entendida si se ponen en un contexto más amplio, que involucra a los anillos e ideales. La más básica de hecho, detrás de la cuestión es, creo, el hecho de que, en cualquier anillo conmutativo, los elementos $qb+r$ $b$ generar el mismo ideal que los elementos $b$$r$. Si hiciera más hipótesis, este hecho puede ser interpretado en términos de divisibilidad. (Ver proyecto de Ley del comentario.) El más simple es asumir que su anillo es una de las principales ideales de dominio.

Yo podría tratar de explicar esto en mayores detalles, pero muchos matemáticos mucho mejor de lo que ya he hecho. Así que, mi consejo sería tomar un vistazo a al menos uno de los muchos Álgebra de los libros de texto escritos por grandes matemáticos. Aquí están algunos de estos libros:

• Michael Artin, Álgebra.

• Nathan Jacobson, Álgebra Básica.

• Serge Lang, Álgebra.

• Saunders Mac Lane, Garret Birkhoff, Álgebra.

En resumen, mi consejo es el clásico: Leer el masters!