La intuición de por qué $\gcd(a,b) = \gcd(b, a \pmod b)$?

Question

¿Alguien tiene una intuición o argumento o croquis prueba de por qué $\gcd(a,b) = \gcd(b, a \pmod b)$?

Tengo una prueba y yo lo entiendo, así que una intuición sería más útil.

---

La prueba de que ya tengo:

Muestro $\gcd(a,b) \mid \gcd(b, a \pmod b)$$\gcd(b, a \pmod b) \mid \gcd(a, b)$, lo que implica $\gcd(a,b) = \gcd(b, a \pmod b)$ y esas cosas es no negativo.

WLOG $a \geq b$

$\gcd(a,b) \mid a$

$\gcd(a,b) \mid b$

por lo que se divide cualquier combinación lineal de a y b

Desde $a \pmod b = a - qb$, entonces:

$\gcd(b, a - qb) = bx + (a-qb)y$

$\gcd(b, a - qb) = bx + ay - qby $

$\gcd(b, a \pmod b) = b(x-qy) + ay$

que es un LC de $a$$b$.

Por lo $\gcd(a,b) \mid \gcd(b, a \pmod b)$.

Otra dirección es casi idéntica.

Answer 1

Sugerencia: Muestre que más generalmente se $\gcd(a,b)=\gcd(b,a-bk)$ para cualquier entero $k$.

A continuación, tenga en cuenta que $a\pmod b = a-bk$ algunos $k$.

Answer 2

Sugerencia $ $ Deje $\, a\ {\rm mod}\ b = a-kb.\, $ Si $\, d\mid b\ $ $\ d\mid \color{#0a0}{a-kb}\iff d\mid \color{#c00}a.\ $ $\ \color{#0a0}{a-kb},b\ $ $\ \color{#c00}a,b\ $ tienen el mismo conjunto $S$ de los comunes divisores $\,d,\,$, por lo que tienen el mismo mayor común divisor $\,(= \max S).$

Answer 3

El quid de todas las pruebas es que el $gcd(b,a) = gcd(b,a-b)$.

Esto debería ser fácil de ver intuitivamente; si añade o resta de dos múltiplos de $g$ usted obtiene un múltiplo de $g$, por lo que todos los factores son retenidos en ambos sentidos.

Una vez que usted sabe que usted puede restar un número de otro tantas veces como quieras, sin necesidad de cambiar el mcd.

Si continúa restando $b$ a partir del segundo número, que finalmente se llegue a un número entre 0 y $b-1$; específicamente $a\bmod b$.

Answer 4

Para mí todo se reduce a esta ecuación $$ a=qb+r $$ Por si $d$ divide $b$ y ninguno de los dos $a$ o $r$ tiene que dividir el último de $a$ $r$ demasiado para que esta ecuación para celebrar.

Answer 5

Supongamos que cada uno de $a$ $b$ es un número entero de millas. Entonces así es $a\bmod b$.

Si una milla es una "medida común" (como Euclides de traductores dicen) de ambas distancias, luego de una milla es una medida común de lo que queda al $b$ ha sido tomado de $a$ tantas veces como sea posible.