# Prove: if $a ∈ [x]$ and $b ∈ [y]$, then $a + b = x + y$ (mod $n$).

I am stuck with connecting the integer congruence with the first part of this proof. I've got the outline.

Let $n ∈ Z$, and let $[x]$ denote the equivalence class of $x$ under integer congruence modulo $n$. Let $a, b, x, y$ be integers.

Proof.
Suppose $a ∈ [x]$ and $b ∈ [y]$.
Then $aRx$ and $bRy$.
So $n|(a-x)$ and $n|(b-y)$, by definition of integer congruence modulo $n$.
So there is an integer $g$ such that $a - x = ng$ and there is an integer $f$ such that $b - y = nf.$
So $(a + b) - (x + y) = a - x + b - y = ng + nf = n(g + f).$
Then there is an integer $k$ such that $(a + b) - (x + y) = nk$; namely, $k = g + f$.
Then $n|((a+b) - (x + y))$, by definition of integer congruence modulo $n$.
Therefore $a + b = x + y$ (mod $n$).

Am I on the right path? Can someone help me fill in the '...'? What exactly is contained in [x]? I know what it means to be an equivalence class, but how does it tie to the integer congruence modulo n?

• Rewrite $aRx$ and $bRy$ in terms of divisibility. If you know two things are multiples of $n$, can you generate any other multiplies of $n$? – pjs36 Feb 24 '16 at 3:09
• @pjs36 I think that's where I'm stuck. How can I rewrite aRx in terms of the integer congruence modulo n divisibility? Is it just aRx means that n|(a-x)? – Dewick47 Feb 24 '16 at 3:13
• Just to be clear, you are off to a good start, you need about 3 lines to get there. For divisibility, when you took your conclusion $a + b = x + y \pmod n$, which is just a restatement of $(a + b)R(x + y)$, you worked backwards I assume. What made you write $n \mid \big(a + b) - (x + y)\big) \pmod n$? EDIT in response to your edit: Yes, that's exactly it! – pjs36 Feb 24 '16 at 3:19
• @pjs36 Can you verify my new proof in the original post is now correct? – Dewick47 Feb 24 '16 at 3:32
• Yes, that works, nicely done! I personally would be happy to use the fact that adding multiplies of $n$ yields a multiple of $n$ without actually writing down extraneous variables (i.e., jumping right to $(a + b) - (x + y)$), but that's perfectly fine. – pjs36 Feb 24 '16 at 4:14

## 1 Answer

If your notation $a \in [x]$ here indicates $a \equiv x \pmod n$, then by definition of congruence $\pmod n$ this means that $\exists s \in \Bbb Z$ such that $a=sn+x$. Similarly, $b \in [y]$ means that $\exists t \in \Bbb Z$ such that $b=tn+y$. But then $a+b=(s+t)n+(x+y)$ so setting $v=s+t$, $a+b=vn+(x+y)$ which implies $a+b \equiv x+y \pmod n$.

• I changed my original proof in my post. I don't think it follows exactly what you said, but it's close. I just used the definition of divisibility more. Can you verify/explain if it's close or correct? – Dewick47 Feb 24 '16 at 3:32
• Yes, if you look closely your updated proof is basically the same as mine: you used $g$ where I used $s$ and you used $f$ where I used $t$. Saying that $a=sn+x$ is the same as saying that $a-x=sn$... – em29 Feb 27 '16 at 3:48