I am trying to learn mathematics from the beginning, i.e. trying to form a solid foundation and understanding of basic concepts that I should have learned in high school.

I am working through Basic Mathematics by Serge Lang and I love the book so far. It is terse and dry in places but I like that, it forces me to really think through things for myself and research other sources when I'm stuck. Well, I think I'm somewhat stuck right now.

I don't know if I understood the exercise well enough and if my proofs are correct.

If anyone has the book, it is exercise 25, p.26, Algebra, Even and odd integers; divisibility. For those who don't own the book:

Let $d$ be a positive integer. Let $a, b$ be integers. Define $$ a \equiv b \pmod{d} $$ to mean that $a - b$ is divisible by $d$. Prove that if $a \equiv b \pmod{d}$ and $x \equiv y \pmod{d}$, then $$a + x \equiv b + y \pmod{d}$$ and $$ax \equiv by \pmod{d}$$

This was the first time that I met $\equiv$ symbol and $\pmod{d}$. In the book it is only briefly mentioned in the previous exercise (which is the same, just $d = 5$) that we read this "$a$ is congruent to $b$ modulo 5". I went on to research this a bit since I didn't know how to even start but have found most of the explanations too advanced for my level and I couldn't take much away from it. After some time I gave up and checked the solution at the back of the book but I didn't understand it quite well. I took some ideas from it and came up with the following proof, which seems right to me but I would like someone to confirm it since it is somewhat different from the one in the book.

By definition we have $$a - b = dk \implies a = b + dk$$ $$x - y = dl \implies x = y + dl$$ for some integers $k, l$.

Proof of the first statement:

$$\begin{align} a + x & = b + dk + y + dl \\ & = b + y + d(k + l) \\ \end{align} $$ from which we get $$(a + x) - (b + y) = d(k + l).$$ Which is the same as saying $$a + x \equiv b + y \pmod{d}$$

Proof of the second statement:

$$\begin{align} ax & = (b + dk)(y + dl) \\ & = by + bdl + dky + d^2kl \\ & = by + d(bl + ky + dkl) \\ \end{align} $$ $$ax - by = d(bl + ky + dkl).$$ Which we can write $$ax \equiv by \pmod{d}$$

I think I understood what this means, in a way congruence is similar to equality. So it is similar to the situation: If $A = B$ and $C = D$ then $A + C = B + D$, and similarly for multiplication.

  • 4
    $\begingroup$ Your work looks fine to me. Good job! $\endgroup$ – paw88789 Feb 3 '15 at 0:10
  • 1
    $\begingroup$ What is your question? $\endgroup$ – user133281 Feb 3 '15 at 0:12

Congratulations, your proof is well.



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.