Aclaración sobre la prueba para el algoritmo euclidiano.

Question

Lema: Vamos a $m$ $n$ ser enteros positivos con $m \leq n$. Si $r$ es el resto de dividir a $n$$m$,$(n,m) = (m,r)$.

La prueba está dada de la siguiente manera:

Tenemos por el algoritmo de la división que $n = sm + r$$0 \leq r < m$. Supongamos que $d = (n,m)$$e = (m, r)$. Desde $r = n - sm$ y $d \mid n,$ $d \mid m$ tenemos $d \mid n - sm = r$.

La parte que no entiendo es cómo $d \mid n - sm = r$ es equivalente a $r = n - sm.$

Parece como si lo está diciendo $n$ es lo mismo que $d \mid n$.

Answer 1

Como$d|n$ y$d|m$, tenemos$d|n-sm$. Pero entonces $n-sm=r$. "$d|r$" es solo una forma comprimida de escribir todo eso. Eso responde tu pregunta?

Answer 2

En general, si$d | n$ y$d | m$, entonces$d | (n - jm)$ para cualquier entero$j$. Para ver esto, deje que$n = ad$ y$m=bd$, luego$(n-jm) = (ad -jbd) = d(a-jb)$, que es claramente divisible por$d$.

En su ejemplo, conocemos$d | n$ y$d | m$ (esto es cierto porque$d=(m,n)$). Entonces$d | (n-sm)$ por la misma regla.

Answer 3

Como$d|r$ y$d|m$, tenemos$d|(m,r)=e.$ Por otra parte,$e|m$ y$e|r$, por lo tanto,$e|sm+r = n.$ Así$e|(n,m)=d.$ Entonces $d|e$ y$e|d$, lo que implica$d=e.$