Remainders of two integers when divided by another integer n

Question

I am curious if the remainder of u+v is the same as the sum of the two integers separately if they are the same how would one go about proving this

Answer 1

HINT

In general, it is not true as stated -- for example, $u=v=1$ and $n=2$, then $u \pmod{2} = v \pmod{2} = 1$ but $(u+v) \mod{2} = 0 \ne 2$. But notice that something else is true: $$ (u+v) \pmod{n} \equiv [u \pmod{n} + v \pmod{n}] \pmod{n} $$ as in our case $2 \pmod{2} \equiv 0$.

The proof would be in the following style. Let $u = an+b,v=cn+d$ with $0 \le d,b < n$. Can you now do arithmetic?

Answer 2

Close. It's possible for the remainders when added together could be larger than $n$. (Ex: if we use the notation $a\% n$ to mean the remainder when $a$ is divided by $n$ then, $13\%7 = 6$ and $12\%7 = 5$ and $6+5 =11$ while $(13+12)\%7= 25\%7 = 4$.)

However the remainder of the sum of the remainders is the same as the remainder of the sum. (Ex: $13\%7 = 6$ and $12\%7 =5$ and $6+5=11$ and $11\%7 = 4$. Meanwhile $(13+12) =25$ and $25\%7 = 4$)

Or maybe a clearer way to word it is:

$u+v$ and the sum of the remainder of $u$ and the remainder of $v$, both have the same remainder.

EDIT: New proof:

If $u\%n = h$ then there is an integer $a$ so that $u=an + h$ and $0 \le h < n$. And if $v\&n = j$ then there is a $b$ so that $v = bn + j$ and $0 \le j < n$. So $h + j < 2n$.

Case 1: $h+j < n$. Then $(h+j)$ is its own remainder.

Then $u+v = (an + h) + (bn + j) = (a+b)n + (h+j)$ and the remainder of $u+v$ is $h + j$.

Case 2: $n\le h + j < 2n$. Then there is a $k$ so that $h+j = n + k$ and $k$ is the remainder.

Then $u+v = (an + h) + (bn + j) = (a+b)n + (h+j) = (a+b)n + n + k = (a+b+1)n + k$. And the remainder for $u+v$ is $k$, the same remainder for $h+j$.

===old proof much harder ====

Proof: Suppose $u \% n = k$. Then means there is an integer $a$ so that $u = an + k$. And $v\%n = j$ means there is an integer $b$ so that $v = bn + j$. And $(u + v)\% n = h$ means there is an integer $c$ so that $u+v = cn + h$.

We want to prove that $(j+k)\% n = h$.

We do that by:

$u= an+k$ and $v= bn + j$ so $u+v = (an+bn) + (k+j) = (a+b)n + (k+j)$. But $u+v = cn + h$. So hat means $cn + h = (a+b)n + (k+j)$.

Which means $(k + j) = (cn+ h) - (a+b)n = (c-a+b)n + h$. So the remainder of $k+j$ is $h$ and the remainder of $u+v$ is $h$.

We have proven it.