3
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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$? $\endgroup$ – pjs36 Feb 24 '16 at 3:09
  • $\begingroup$ @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)? $\endgroup$ – Dewick47 Feb 24 '16 at 3:13
  • $\begingroup$ 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! $\endgroup$ – pjs36 Feb 24 '16 at 3:19
  • $\begingroup$ @pjs36 Can you verify my new proof in the original post is now correct? $\endgroup$ – Dewick47 Feb 24 '16 at 3:32
  • $\begingroup$ 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. $\endgroup$ – pjs36 Feb 24 '16 at 4:14
0
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Dewick47 Feb 24 '16 at 3:32
  • $\begingroup$ 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$... $\endgroup$ – em29 Feb 27 '16 at 3:48

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.