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?
On
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}$$
On
$\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.
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)$.