¿Cuál es la prueba del lema de división del euclides que establece que, dados los enteros ayb, existen dos enteros q y r tales que a = bq + r, donde 0 = <a <b?

Aquí estoy tomando el lema de la División de Euclides como b = aq + r. Por lo tanto, no confunda.

Consideremos un conjunto S = {b-ak | b-ak es mayor o igual que cero, k € Z}. Así que de esto queda claro que b + | ab | Es el miembro de ‘S’. Por lo tanto, ‘S’ no es un conjunto vacío. Es por eso que al ordenar bien el principal, S tiene un elemento menor. Deja que ese elemento menor sea ‘r’. Y ahora, como ‘r’ es el miembro de S, entonces ‘r’ debe ser mayor o igual a cero y existe un entero ‘q’ tal que r = b-aq.

Ahora si ‘r’ es mayor o igual que | a | entonces

r- | a | es mayor o igual a cero y también

r- | a |

Ahora probamos la singularidad de ‘q’ y ‘r’. Supongamos que b = aq1 + r1 y también b = aq2 + r2 con r1 y r2, ambos mayores o iguales a cero y ambos menores que | a |. Ahora, si r1 no es igual a r2, vamos a r1

r2 – r1 = a (q1 – q2). Así obtenemos que ‘a’ se divide (r2 – r1). Pero esto contradice con el hecho de que

(r2 – r1) <| a |. Por lo tanto, r1 = r2 y así obtenemos q1 = q2.

Prueba:

Tenemos que discutir dos cosas.
Primero, necesitamos mostrar que q y r existen. Entonces, necesitamos mostrar que q y r son únicos.

Para mostrar que q y r existen, juguemos con un ejemplo específico primero para tener una idea de lo que podría estar involucrado, y luego tratar de argumentar el caso general.

Recuerde que si b es positivo, el resto de la división de b por a es el resultado de restar tantas a como sea posible mientras se mantiene el resultado como no negativo.
Si b es negativo, el resto se encuentra de una manera ligeramente diferente, agregando tantas a como sea necesario hasta que el resultado sea negativo.
Con esto en mente, supongamos que b = 27 y a = 5, y consideremos el conjunto de todos los enteros que resultan de sumar a 27, o restar de 27, algunos múltiplos de 5:

{…, −8, −3,2,7,12,17,22,27,32,37,…}

Ahora reduzcamos este set a solo los valores positivos presentes, para producir un set

S = {2,7,12,22,27,32,37,…}

Podemos ver que el elemento más pequeño de este conjunto (es decir, 2) es el resto que buscamos, pero en el caso más general, ¿cómo podemos garantizar que existe este elemento más pequeño? Recuerde que el principio de ordenamiento correcto nos dice que cualquier conjunto no vacío de enteros no negativos contiene un elemento mínimo. Quizás esto podría ser útil …

Ahora, con un indicio de qué herramienta podría ser útil, prestemos atención al caso general, para algunos a y b arbitrarios, con a> 0. De una manera similar a la empleada anteriormente, podemos construir un conjunto

S = {b − ka, donde k es un número entero y b − ka≥0}

Buscamos demostrar, usando el principio de ordenamiento correcto, que este conjunto tiene un elemento mínimo (que esperamos que desempeñe el papel de r). Por su construcción, S solo puede contener números enteros no negativos, por lo que queda para mostrar que no está vacío.

Si b≥0, esto es trivial, ya que b estará en el conjunto (considere k = 0).

Si b <0, considere k = b en su lugar. Nuestro objetivo es mostrar que b − ka≥0 para este valor de k y, por lo tanto, necesariamente debe estar en el conjunto S. Para este fin, note
b − ka = b − ba = b (1 − a)
y el factor (1 − a) debe ser cero o negativo como a> 0. En consecuencia b (1 − a) ≥0. Poniendo el lado izquierdo de esta última desigualdad nuevamente en su forma original, terminamos con b − ka≥0. Por lo tanto, concluimos que S debe contener el elemento b − ka cuando k = b.

Por lo tanto, independientemente del valor de b, S tendrá al menos un elemento y, por lo tanto, no estará vacío. Habiendo demostrado que el conjunto S es un conjunto no vacío de valores no negativos, se aplica el principio de buen ordenamiento y garantiza que S tiene un elemento mínimo.

Ahora la pregunta se refiere a si este elemento o no es realmente un valor razonable para r, y si puede producir algún valor razonable para q también …

Supongamos que este elemento menor está dado por
r = b − kra
Por supuesto, si este es un valor razonable para nuestros propósitos, deberemos estar seguros de que 0≤r

Ya sabemos que r no es negativo como lo era en S, por lo que todo lo que tenemos que hacer ahora es asegurarnos de que es menos que un. Pero considere la alternativa: si r≥a, entonces b − kra≥a, lo que implica (después de restar a a ambos lados) que
b− (kr + 1) a≥0
Esto contradice el hecho de que r era el elemento más pequeño del conjunto S. Por lo tanto, debe darse el caso de que r

Encontrar q ahora es fácil, como si b = qa + r, entonces
q = b − ra
Reemplazando r con b − kra, tenemos
q = b− (b − kra) a = kraa = kr
Por lo tanto, existen valores enteros q y r, con 0≤r

Queda por mostrar que estos valores para qyr son únicos.

Efectivamente, necesitamos mostrar que si b = q1a + r1 y b = q2a + r2, solo puede ser el caso de que q1 = q2 y r1 = r2.

Sin pérdida de generalidad, supongamos que r2≥r1. Sustituyendo por b, tenemos
q1a + r1 = q2a + r2
Pero entonces
q1a − q2ar2 − r1 == r2 − r1 y por lo tanto, a (q1 − q2)
En consecuencia, r2 − r1 es un múltiplo de a.

Sin embargo, como 0≤r1, r2 r1, debe darse el caso de que 0≤r2 − r1