How should I be proving this?
If the remainder in the division of $a$ by $b$ is $r$ and $c|b$, then the remainder of division of $a$ by $c$ equals the remainder in the division of $r$ by $c$
Would I use the definition of $a \equiv b$ (mod $r$) also means that $r|(b-a)$? Or should I be using the definition of the division algorithm with $a = qb + r$ where $0≤ r < |b|$? I also don't understand what to do about $c|b$.
I tried using the definition of divisibility so that $c \, m = b$, and substituting $b$ for $cm$ so that $r|(cm-a)$ but have been stuck here. I also tried $a = q cm + r$, so $r = a+(-qm)c$, which would make $a$ the remainder of the division of $r$ by $c$.
I'm honestly just so confused. The next part of the question asks to use $(b,c)$ to compute the remainders in the division of a huge number, so I'm leaning towards using the definition of $a \equiv b$ (mod $r$).
Answer
You just do it.
$a = kb + r$ for some integer $k$ and $0 \le r < b$. That's what having a remainder of $r$ means.
And $b = c*n$ for some integer $n$. That's what $c|b$ means.
so $a = k(c*n) + r$
And if the remainder of $r$ when divided by $c$ is $r'$ then there is an integer $m$ so that $r = c*m + r'$ and $0\le r' < c$
So $a = k(c*n) + c*m + r'$ so $a = c(kn + m) + r'$ with $0\le r < c$.
So the remainder of $a$ when divided by $c$ is $r'$ which is the remainder of $r$ divided by $c$.
...
Using the notation for equivalence we have
$a \equiv r \mod b$ which means $b|a-r$
And $b \equiv 0 \mod c$ which means $c|b$.
So by transitivity $c|a-r$ so $a \equiv r \mod c$.
I guess you have to prove that $c|b$ and $b|d\implies c|d$ but that's comes directly from the definition of "divids". There is a $n$ and $k$ so that $b = c*n$ and $a-r = b*k$. So $a-r = c(kn)$. So $c|a-r$.
No comments:
Post a Comment