Teorema del resto del cociente

El Teorema del Resto del Cociente establece que para cualquier par de enteros a y b (b es positivo), existen dos enteros únicos q y r tales que:

a = bxq + r
donde 0 <= r < b

Ejemplo 1:
Si a = 22, b = 4
entonces q = 5, r = 2
22 = 4 x 5 + 2

Ejemplo 2:
Si a = -19, b = 5
entonces q = -4, r = 1
-19 = 5 x -4 + 1

Uso del teorema del resto del
cociente: el teorema del resto del cociente es el teorema fundamental de la aritmética modular. Se utiliza para probar la suma modular , la multiplicación modular y muchos más principios de la aritmética modular.

Prueba:

Para probar el teorema del Resto del Cociente, tenemos que probar dos cosas:
Para cualquier número entero a y número entero positivo b:
1. q y r existen
2. q y r son únicos

Existencia de q y r:
Considera la progresión…, a – 3b, a – 2b, a – b, a, a + b, a + 2b, a + 3b…
Esto se extiende en ambas direcciones.
Por el principio de buen orden , debe existir un elemento no negativo más pequeño x.
Por lo tanto, x = a – qb y x deben estar en el intervalo [0, b) porque, de lo contrario, rb sería más pequeño que r y un elemento no negativo en la progresión.

Unicidad de q y r:
Supongamos que tenemos otro par q0 y r0 tal que a =bx q0 + r0, con 0 <= r0 < b.
bxq + r = bx q0 + r0
Vemos que r – r0 = b(q0 – q), entonces q0 – q = b / (r – r0)
Como 0 <= r < b y 0 <= r0 < b, tenemos que -b < r-r0 < b
Por lo tanto, r- r0 = 0 que implica r = r0
Entonces r – r0 = 0 = b(q0 – q)
lo que implica que q = q0.
Esto muestra singularidad.