0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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}$ $\endgroup$ – J. W. Tanner Feb 22 at 1:16
  • $\begingroup$ No, it is not true but. The remainder of $u+v$ is the same as the REMAINDER of the sum of the remainders. $\endgroup$ – fleablood Feb 22 at 1:57
0
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ I'm not sure an OP who would ask this question would be familiar with modular arithmetic. $\endgroup$ – fleablood Feb 22 at 1:36
  • $\begingroup$ @fleablood didn't think, maybe OP just starting -- will leave the answer here just in case $\endgroup$ – gt6989b Feb 22 at 1:45
  • $\begingroup$ 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". $\endgroup$ – fleablood Feb 22 at 1:56
  • $\begingroup$ I am familiar with it, thank you. $\endgroup$ – redneckmathematician Feb 22 at 13:54
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.