0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – JMoravitz Jan 7 '18 at 1:08
  • $\begingroup$ 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... $\endgroup$ – JMoravitz Jan 7 '18 at 1:11
1
$\begingroup$

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$.

$\endgroup$
1
$\begingroup$

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.