Please Login to access more options.

Problem 25 (Modular Arithmetic Properties)

Let $n$ be a positive integer. Let $a,b\in \mathbb{Z}$.

  1. Show that $((a \mod n)+(b\mod n))\mod n = (a+b)\mod n$. In other words, show that the sum of the remainders has the same remainder as the original sum.
  2. Show that $((a \mod n)(b\mod n))\mod n = (ab)\mod n$. In other words, show that the product of the remainders has the same remainder as the original product.

Remember, you'll want to use the division algorithm to obtain quotient and remainders when dividing $a$, $b$, $ab$, and $a+b$ by $n$. You'll need to use the problem, Remainders Equal Iff Difference Is A Multiple, to complete your work.

Solution

Part 1:
From the division algorithm, we know that there exists unique integers $q_a,r_a,q_b,r_b$ such that $a=q_an+r_a$ and $b=q_b+r_b$, where $0\leq r_a,r_b < n$. Let $A=(a\mod n)+(b\mod n)$ and let $B=a+b$. From problem 16, we know that $A\mod n=B\mod n$ if and only if $A-B$ is a multiple of $n$. We now compute

$$\begin{align} A-B&=(a\mod n)+(b\mod n)-(a+b)\\ &=(r_a)+(r_b)-(q_an+r_a+q_bn+r_b)\\ &=-q_an-q_bn\\ &=(-q_a-q_b)n \end{align}$$

Since $A-B$ is a multiple of $n$, we conclude that $A\mod n=B\mod n$, or $((a\mod n)+(b\mod n))\mod n=(a+b)\mod n$.
Part 2:
From the division algorithm, we know that there exists unique integers $q_a,r_a,q_b,r_b$ such that $a=q_an+r_a$ and $b=q_b+r_b$, where $0\leq r_a,r_b < n$. Let $A=(a\mod n)(b\mod n)$ and let $B=ab$. From problem 16, we know that $A\mod n=B\mod n$ if and only if $A-B$ is a multiple of $n$. We now compute $$\begin{align} A-B&=(a\mod n)(b\mod n)-(ab)\\ &=(r_a)(r_b)-(q_an+r_a)(q_bn+r_b)\\ &=r_ar_b-q_aq_bn^2-q_ar_bn-q_br_an-r_ar_b\\ &=-q_aq_bn^2-q_ar_bn-q_br_an\\ &=(-q_aq_bn-q_ar_b-q_br_a)n \end{align}$$ Since $A-B$ is a multiple of $n$, we conclude that $A\mod n=B\mod n$, or $((a\mod n)(b\mod n))\mod n=(ab)\mod n$.

Tags
  • 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.