Prueba de $[(a \; \text{mod} \; n)+(b \; \text{mod} \; n)] \equiv (a+b)\; \text{mod}\; n$

Question

Actualmente estoy estudiando por mi cuenta un curso de criptografía, y comprendo la importancia de entender a fondo la aritmética modular. He demostrado muchas operaciones en aritmética modular, pero uno que estoy atascado en es por qué:

$[(a \; \text{mod} \; n)+(b \; \text{mod} \; n)]=(a+b)\; \text{mod}\; n$ y la prueba completa de ello.

He tenido algunas ideas al respecto, pero no lo he probado del todo.Puede que sea obvio, pero yo sólo soy $15$ .

Gracias por cualquier ayuda.

Answer 1

Sea $$a=q_an+r_a$$ $$b=q_bn+r_b$$ para cocientes $q_a,q_b$ y restos $0\le r_a,r_b<n$ de $a,b$ modulo $n$ . Entonces $$\begin{align} a+b&=(q_a+q_b)n+(r_a+r_b)\\ &=\left(q_a+q_b+\delta\right)n +\left(r_a+r_b-\delta n\right) \end{align}$$ para $$\delta=\left\lfloor\frac{r_a+r_b}{n}\right\rfloor$$ donde $\lfloor x\rfloor$ es el mayor número entero (menor o igual que $x$ ) o función de suelo y $$\left(r_a+r_b-\delta n\right)=(a+b)\text{ mod }n.$$ Ahora bien, la igualdad sólo se cumple si $\delta=0$ : no es cierto en general que $r_a+r_b=r_a+r_b-\delta n$ . Por ejemplo, pruebe $a=b=1,n=2$ . Lo que sí se cumple es la congruencia módulo $n$ : $$(a \; \text{mod} \; n)+(b \; \text{mod} \; n) \equiv (a+b)\; \pmod n$$ que acabamos de demostrar. En matemáticas, decimos $$a\equiv b\pmod n \qquad\iff\qquad n | b-a$$ es decir, si su diferencia es divisible por $n$ pero en algunos contextos informáticos, $$r_a=a\text{ mod }n$$ significa que $r_a$ es el resto de dividir $a$ por $n$ utilizando el algoritmo de división , con $0\le r_a<n$ o a veces $-\lfloor\frac n2\rfloor\le r_a<\lfloor\frac n2\rfloor$ o incluso $-n<r_a<n$ lo que puede ser fuente de confusión.

Answer 2

Pista:

No hace falta demostrarlo: es una definición que es sin ambigüedad una vez que has probado esto:

Si $a\equiv a'\mod n$ y $b\equiv b'\mod n$ entonces $a+b\equiv a'+b'\mod n$

que resulta de observar que $a+b\bmod n=(a\bmod n+b\bmod n)\bmod n$ .