# Remainders of two integers when divided by another integer n

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

• Not exactly; remainder when $17$ is divided by $10$ is $7$ and when $14$ is divided by $10$ is $4$, but when $31=17+14$ is divided by $10$ is $1 \ne 7+4$, though $1 \equiv 7+4 \pmod {10}$ – J. W. Tanner Feb 22 at 1:16
• No, it is not true but. The remainder of $u+v$ is the same as the REMAINDER of the sum of the remainders. – fleablood Feb 22 at 1:57

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?

• I'm not sure an OP who would ask this question would be familiar with modular arithmetic. – fleablood Feb 22 at 1:36
• @fleablood didn't think, maybe OP just starting -- will leave the answer here just in case – gt6989b Feb 22 at 1:45
• It's a good answer. And something for the OP to figure out which s/he can once realizes that $u \pmod 2$ means "remainder" and $a \equiv b \pmod n$ means "$a$ and $b$ have the same remainder". – fleablood Feb 22 at 1:56
• I am familiar with it, thank you. – redneckmathematician Feb 22 at 13:54

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.