2
$\begingroup$

For all $n \in \mathbb{N}$, $n > 1$ and $x,y \in \mathbb{Z}$ prove that

\begin{equation} (x+y) \text{ mod } n = ((x \text{ mod } n)+(y \text{ mod } n))\text{ mod } n. \end{equation}

Would this be a proof if I say:

Let $x = x' \text{ mod } n$ and let $y=y' \text{ mod } n$. Then

\begin{equation} x+y = x'+y' \text{ mod } n. \end{equation}

Now, if we look at the current thing we want prove, this will follow:

\begin{equation} x+y \text { mod } n = (x \text{ mod } n + y \text{ mod } n) \text{ mod } n. \end{equation}


I'm not sure if this is allowed or will count as a "proof" at all. Maybe you can show me some other ways of doing this, more precise ones?

$\endgroup$
  • $\begingroup$ No, it is not a valid proof. Are you familiar with congruence arithmetic? $\endgroup$ – Bill Dubuque Nov 2 '16 at 20:08
  • $\begingroup$ no i'm not this is the first time :p $\endgroup$ – berndgr Nov 2 '16 at 20:15
3
$\begingroup$

Using $\,\ a\equiv b\pmod n\color{#c00}\iff (a\ {\rm mod}\ n) = (b\ {\rm mod}\ n)\,\ $ we have

${\rm mod}\ n\!:\ \ x\color{#c00}\equiv (x\ {\rm mod}\ n)$
$\qquad\qquad y\color{#c00}\equiv (y\ {\rm mod}\ n)$
$\ \Rightarrow\,\ x+y\equiv (x\ {\rm mod}\ n) + (y\ {\rm mod}\ n)\ \ $ by the $ $ Congruence Sum Rule

$\ \Rightarrow\, (x+y)\ {\rm mod}\ n\, =\, ((x\ {\rm mod}\ n) + (y\ {\rm mod}\ n))\ {\rm mod}\ n\,\ $ by $\,(\color{#c00}{\Rightarrow})\,$ above

Remark $ $ Generally, as above, to prove an identity about mod as an operator it is usually easiest to first convert it into the more flexible congruence relation form, prove it using congruences, then convert back to operator form at the end (using the equivalence in the first line above).

$\endgroup$
  • $\begingroup$ alright i should really read a book or something before trying a task because i have troubles understanding your solution and the task too. but thx for it and for the link as well! $\endgroup$ – berndgr Nov 2 '16 at 20:22
  • $\begingroup$ @berndgr The only thing you need to know from the link is the proof of the Sum Rule. By definition $\ a\equiv b\pmod n\iff n\mid a-b.\ $ Let me know if you need help learning that. Once you master congruences problems like this will become straightforward. $\endgroup$ – Bill Dubuque Nov 2 '16 at 20:24
1
$\begingroup$

I will assume that $x\pmod n$ stands for element of $\{0,1\ldots,n-1\}$ which I will denote with $x'$ such that $x = kn + x'$. But, it doesn't actually matter at all.

First, let me clarify definitions: $x\equiv x'\pmod n$ if and only if $n\mid x - x'$. Note that since we have Euclidean division (division with remainder) in $\Bbb Z$, for every $x\in\Bbb Z$, there is a unique number $x'\in\{0,\ldots,n-1\}$ such that $x = kn + x'$ for some $k\in\Bbb Z$ (which you denote by $x\pmod n$). But, $x-x' = kn$ which implies that $x\equiv x'\pmod n$. Conversely, if $x\equiv x'\pmod n$ and $x'\in\{0,1,\ldots,n-1\}$, then $x' = x\pmod n$. So, to prove your statement, I will use this more general notion of congruence.

I claim that whenever $x\equiv x'\pmod n$ and $y\equiv y'\pmod n$, then $x+y\equiv x' + y'\pmod n$ (i.e., addition is well defined in modular arithmetic). This will give your result as a special case.

So, $x-x' = kn$, $y - y' = ln$, with $k,l\in\Bbb Z$. Add this two to get $(x+y)-(x'+y') = (k+l)n$ which implies that $x + y\equiv x'+y'\pmod n$.

$\endgroup$
  • $\begingroup$ thank you i will translate to my language and try to understand :) $\endgroup$ – berndgr Nov 2 '16 at 20:30
  • $\begingroup$ @berndgr, you can always ask for clarification of particular points I make. All we do is proclaim numbers with the same remainder equal. But we need to check that we can still do addition, i.e., if we switch any number with another with same remainder, it won't change result of the addition. Loosely speaking, remainder of a sum is a sum of remainders. $\endgroup$ – Ennar Nov 2 '16 at 20:35

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.