Please Login to access more options.

Problem 16(Remainders Equal Iff Difference Is A Multiple)

Let $a,b,n\in\mathbb{Z}$ with $n>0$. Prove that $a\pmod n = b \pmod n$ if and only if $a-b$ is a multiple of $n$.

Solution

Suppose $(a \mod n) = (b \mod n)$ for some integers $a$, $b$, and $n$. We must show that $a-b = qn$ for some integer $q$. Use the division algorithm to write $a$ as $a-qn + a_r$ for some integers $a_q$ and $a_r$. Use the division algorithm again to write $b$ as $b_qn+b_r$ for some integers $b_q$ and $b_r$. Then $ a_r - b_r = 0 $ by the definition of modulus. Subtracting $a$ from $b$ yields $$\begin{align} a-b &=a_qn - b_qn +a_r - b_r\\ &=a_qn - b_qn&(\text{recall }a_r -b_r = 0)\\ &=n(a_q - b_q)&(\text{factor}), \end{align}$$ which is clearly a multiple of $n$. Thus, if $(a \mod n) = (b \mod n)$ then $a-b$ is a multiple of $n$.

Now, suppose $a-b = qn$ for some integers $a$, $b$, $q$, and $n$ with $n > 0$. We must show that $(a \mod n) = (b \mod n)$. Again using the division algorithm, we write $a$ and $b$ as $a = a_qn + a_r$ and $b = b_qn+b_r$. Then $a_qn - b_qn + a_r - b_r = qn$. It is clear that for this to be true, $a_r - b_r$ must also be a multiple of $n$. However, we know $0 \leq a_r, b_r < n$ because they are remainders from the division algorithm. This means that the difference must be in the interval $ [-(n-1), (n-1)] $. Since we know that it must be a multiple of $n$, we see that $a_r - b_r = 0$. Then $a_r = b_r$. By the definition of the modulus, we have $(a \mod n) = (b \mod n)$. Thus, if $a - b $ is a multiple of $n$, then $(a \mod n) = (b \mod n)$. Since we have also shown that if $(a \mod n) = (b \mod n)$ then $a-b$ is a multiple of $n$, we know that $(a \mod n) = (b \mod n)$ if and only if $a-b$ is a multiple of $n$.

Tags

Change these as needed.

  • Week2 - Which week are you writing this problem for?
  • Christian - Sign your name by just changing "YourName" to your wiki name.
  • Complete
  • When you are ready to submit this written work for grading, add the phrase [[!Submit]] to your page. This will tell me that you have completed the page (it's past rough draft form, and you believe it is in final draft form). Don't type [[!Submit]] on a rough draft.
  • If I put [[!NeedsWork]] on your page, then your job is to review what I've written, address any comments made, and then delete all the comments I made. When you have finished reviewing your work, leave [[!NeedsWork]] on your page and type [[!Submit]]. (Both tags will show up). This tells me you have addressed the comments.
  • I'll mark your work with [[!Complete]] after you have made appropriate revisions.