3
$\begingroup$

We have recently started working with modular arithmetic in my discrete mathematics course, and I found two problems in my textbook that I am having trouble with. What are these kinds of proofs called, and what is the usual approach that is undertaken? Lastly, how would you suggest tackling these proofs in particular? Thank you so much in advance!

1.(a mod m) + (b mod m) ≡ (a + b mod m)

2.(a mod m)(b mod m) ≡ (ab mod m)

$\endgroup$
1
$\begingroup$

The idea here is to write $a\mod m$ as $a+k_1m$, where $k_1$ is some constant. Then we can construct a proof quite easily.

For 1, we have $(a+k_1m) + (b + k_2m) = a+b+(k_1+k_2)m \equiv a+b\mod m$

And for 2, we have $(a+k_1m)(b + k_2m) = ab+(bk_1+ak_2+k_1k_2m)m \equiv ab \mod m$

$\endgroup$
  • $\begingroup$ Can you explain this last step: = a+b+(k1+k2)m ≡ a+b mod m How do you arrive that this is congruent to a+b mod m ? $\endgroup$ – BillyBob1 Apr 30 '17 at 2:16
  • $\begingroup$ Here's a better way of explaining it. By definition $(k_1+k_2)m \equiv 0 \mod m$ $\endgroup$ – Isaac Browne Apr 30 '17 at 2:20
  • $\begingroup$ Oh, I get it now, thanks for your help. $\endgroup$ – BillyBob1 Apr 30 '17 at 2:21
0
$\begingroup$

You’re using the binary “mod” operator, which may be defined this way: $a\bmod m$ is the number $\bar a$ satisfying the conditions that $0\le\bar a<m$ and $a-\bar a$ is a multiple of $m$. In other words, $a\bmod m$ is the remainder when $a$ is divided by $m$ using Euclidean division.

As you’ve undoubtedly noticed, it may be that $(a\bmod m)+(b\bmod m)$ may be unequal to $(a+b)\bmod m$, as in the case $a=4$, $b=5$, and $m=7$. But notice that their difference is still a multiple of $7$.

Mathematicians say, when $A$ and $B$ have a difference that’s divisible by $m$, that $A\equiv B\pmod m$. I think that this notation has slipped into the formulation of your problem, which seems to be asking you to show that even when $(a\bmod m)+(b\bmod m)\ne(a+b)\bmod m$, the two numbers still have a difference divisible by $m$.

In the notation I introduced for $\bar a$, you’re being asked to show that $\bar a+\bar b$ and $\overline{a+b}$ are numbers whose difference is divisible by $m$. But that’s easy enough: $a-\bar a$, $b-\bar b$ and $a+b-\overline{a+b}$ all are multiples of $m$. That is, $a-\bar a=rm$, $b-\bar b=sm$, $a+b-\overline{a+b}=tm$. Pile them all together in the right combination, and you get $\bar a+\bar b-(\overline{a+b})=(t-r-s)m$. I’ll let you do the other one in (almost) the same way.

$\endgroup$
0
$\begingroup$

The key idea is to start by assuming that $a$ and $b$ can be expressed in the form $a=mq_1+r_1$ and $b=m q_2 + r_2$, where the $q_i$s are the quotients and the remainders are $r_i \in \{0,1,\ldots,m-1\}$. From there it is just basic manipulation of the expressions.

Recall that given an integer $m \ge 1$ and an integer $n$, we can express $n$ uniquely as $n=mq+r$, where $r$ is the remainder upon dividing $n$ by $m$ and $r \in \{0,1,\ldots,m-1\}$. Observe that if $n$ is negative, then we can keep adding $m$ to to this negative integer until we get a non-negative integer, which we denote by $r$.

For example, $18$ mod $5$ is $3$ because if we keep subtracting $5$ from the given integer $18$ until we get a number in $\{0,1,\ldots,4\}$, the number we get is $3$. Similarly, $-18$ mod $5$ is $2$ because if we keep adding $5$ to $-18$ until we hit a number in $\{0,1,\ldots,4\}$, then we hit $2$.

$\endgroup$

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.