# Modulo, help solving

Given $a,b \in \mathbb{N}$, $a$ and $b$ are positive integers and $a | b$, $a$ divides $b$, $b \mod a = 0$ we have:

$$(x \mod b) \mod a = x \mod a \quad\quad\forall x \in \mathbb{Z}$$

Prove:

$$x \equiv y \quad(\mod b) \quad\text{ implies}\quad x \equiv \quad(\mod a) \\ \forall x, y \in \mathbb{Z}$$

I am not looking for a straight answer, but how to go about solving this.

I have manipulated these equations in many ways trying to get an answer, but I just cannot seem to wrap my head around it.

Here are some things I have tried:

\begin{aligned} x \equiv y \quad(\mod b) &\quad\quad x \equiv y \quad(\mod a) \\ x \mod b = x \mod y &\quad\quad x \mod a = y \mod a \end{aligned} \\ \\ (x \mod b) \mod a = y \mod a \\ (y \mod b) \mod a = y \mod a

This basically manipulates what I want to prove, but all it does is swap $x$ for $y$, which does not seem right.

$$x \equiv y \quad(\mod b) \\ x = y + kb \\ x \equiv y \quad(\mod a) \\ x = y + ka \\ y + kb = y +ka$$

This of course does not work as $a \not= b$ and is just forced.

I am not sure how to reconcile this.

• When you say $x\equiv y\pmod{b}$ this does indeed mean that there is some integer $k_1$ such that $x=y+k_1b$. Similarly, when you say $x\equiv y\pmod{a}$ this means that there is some integer $k_2$ such that $x=y+k_2a$. These don't need to be the same! There is no reason to expect $k_1$ to equal $k_2$. As such, you should avoid using the same name for each as you did above. You called them both "$k$" and confused yourself. – JMoravitz Jan 7 '18 at 1:08
• That being said, we want to show that $x\equiv y\pmod{b}$ implies $x\equiv y\pmod{a}$... we do not assume that both are true, we only assume the first is true and show that the second must follow. So, we have $x=y+kb$ and since $a\mid b$ there must be some $l$ such that... (use what it means for $a$ to divide $b$)... and by rearranging we get... which implies... – JMoravitz Jan 7 '18 at 1:11

Prelim: If $m|n$ and $n|k$ then $m|k$.

Pf: $m|n \implies \frac nm \in \mathbb Z$. And $n|k \implies \frac kn \in \mathbb Z$. So $\frac km =\frac nm * \frac kn\in \mathbb Z$. So $m|k$.

....

So $x \equiv y \mod b \iff b|(x - y)$.

And we have $a|b$.

So $a|(x-y)$.

But $a|(x-y) \iff x \equiv y \mod b$.

That's it.

........

Note: if you use any definiton of $m|n$ ($n = km$ for some integer $m$ or $n \equiv 0 \mod m$)

And if you use any definition of $x \equiv y \mod b$ ($x = y + kb$ for some integer $m$; of $\frac xb$ and $\frac yb$ have the same remainder; or $b|x-y$) the prove would still be the same)

Example:

Prelim: $m|n$ means $n = jm$ for some integer $j$ and $n|k$ means $k = ln$ for some integer $l$. So $k = (lj)m$ so $m|k$.

$x \equiv y \mod b$ means $x = y + jb$ for some integer $j$. But we have $a|b$ so $b = la$ for some integer $l$. So $x = y + (jl)a$ so $x \equiv y \mod a$.

You're making more complex than they are: $x\equiv y\mod b$ means $x-y$ is divisible b, i.e. there exists $k\in \mathbf Z$ such that $x-y=kb$.

Now, if $a\mid b$, we can write $b=ca$ for some integer $c$, so $$x-y=kb=k(ca)=(kc)a,$$ which means $x\equiv y\mod a$.