0

Prove that if a and b are integers such that a|b and b > 0, then (x mod b) mod a = x mod a for any x.

Solution: As a|b, we have b = pa for some integer p. Let x mod b = r, then we have x = bq + r = apq + r for some integer q. Hence, we have x mod a = r mod a = (x mod b) mod a

I don't see how the author of this proof went from x = bq + r = apq + r to x mod a = r mod a. Can someone please explain this to me?

SpyMachine
  • 105

3 Answers3

1

$\overbrace{(x\ {\rm mod}\ b)}^{\large r}\ {\rm mod}\ a\, =\, \overbrace{(x\!-\!bq)}^{\large r}\ {\rm mod}\ a\, =\, (x\!-\!apq)\ {\rm mod}\ a\, =\, x\ {\rm mod}\ a$

Remark $\ $ Generally $\ x \equiv y\pmod{ap}\,\Rightarrow\,x\equiv y\pmod a\ $ by $\ a\mid ap\mid x-y$

Yours is the special case $\, y = (x\ {\rm mod}\ ap),\,$ using $\ x\equiv y\pmod a\,\Rightarrow\, (x\ {\rm mod}\ a) = (y\ {\rm mod}\ a).$

Generally, as here, it is much easer to work first with congruences then, if need be, reduce to remainders (= least reps $\ge 0)\,$ only at the end.

Bill Dubuque
  • 272,048
0

We have $x=apq+r$, and $r$ is the class of $x$ modulo $b$.

So, looking at this equality modulo $a$, we have $x \equiv r\; (\textrm{mod}\; a)$ since $apq \equiv 0\; (\textrm{mod}\; a)$. This proves the result, since $x \equiv r\; (\textrm{mod}\; b)$.

ah11950
  • 2,670
  • 12
  • 19
  • Same question as above, where does apq≡0(mod a) come from? – SpyMachine Mar 25 '14 at 01:19
  • $a \mid apq$, so the remainder upon dividing $apq$ by $a$ is zero. Thus, $apq \equiv 0; (\textrm{mod}; a)$. Remember how equivalence modulo an integer $m$ is defined: $\alpha \equiv \beta ; (\textrm{mod} ; n)$ iff $n\mid \alpha - \beta$. – ah11950 Mar 25 '14 at 01:21
0

At the beginning of the step you asked about, we have that $x = apq + r$. When we work modulo $a$, $a=0$, so $$\begin{align} x \pmod{a} &= \\ apq + r \pmod{a} &= \\apq\pmod{a} + r\pmod{a} &= \\0 + r \pmod{a} &= \\r\pmod{a}.\end{align}$$

William Ballinger
  • 3,682