0
$\begingroup$

I have met the following theorem from the book Introduction to Algorithms (3rd ed.) in the number theory section. The theorem states that

Prove that if $a>b>0$ and $c=a+b$, then $c \bmod a=b$.

Please help. In my mind, the main aspect is that because $a>b>0$, it means $c$ is also more then $0$ and each $a$ and $b$, and also $c/a=1$, so remainder is equal automatically to $b$, or $c=1 \cdot a+b$ (because a>b). Please tell me if I am correct.

  • 0
    Your argument seems valid to me.2011-10-26

2 Answers 2

4

The division theorem for integers tells us that given $n, d > 0$, there exists unique pair $(q,r)$ (both integers) such that $n = d q + r$ and $0 \le r \lt d$. We call $q$ the quotient, and $r$ the remainder. By the uniqueness, once you find any quotient-remainder pair that satisfies all the required conditions, you are done.

In the present case, take $n=c$, $d=a$, $q=1$ and $r=b$. Clearly $0 \leq r = b < a = d$, and $ n = c = a+b = a \cdot 1 + b = d \cdot q + r. $ So from the above paragraph, we are done: $q=1$ is the quotient, and $r=b$ is the remainder obtained by dividing $n$ by $d$.

  • 0
    @Srivatsan Narayanan: Oddly enough, a $c$ommon name in English-language introductions to Number Theory is the *Division Algorithm*.2011-10-26
1

This follows directly from the definition of congruence modulo an integer:

If $x,y,n\in \mathbb{Z}$, then $x\equiv y \mod(n)$ (which is semantically the same as $x \,\mod(n)\,=y$, although the former notation is more broadly used and, personally, I find the latter notation irritating) if $n \vert x-y$ (ie if there exists $k\in \mathbb{Z}$ with $nk=x-y$).

So, we know that $c=a+b$. Use the definition above to s how that $c \equiv b \mod(a)$. Note that it doesn't matter if $a>b$ or if either $a$ or $b$ are positive. It's still the case that $a+b \equiv b\mod(a)$.

  • 0
    Also, even if you work with congruence classes, one can introduce the equivalence relation mod$n$in two different (but equivalent ways): $a \equiv b \mod n$ means $n |b-a$ or $a \equiv b \mod n$ means$a$and$b$have the same reminder when divided by $n$. In math we ususally use the first definition, in computer science I think they use the second. I also saw the second used as a definition in some math classes. Of course WE know they are equivalent, but some of the students don't...2011-10-26