1

Question: Give an example to show that Law D is not always true if $r$ is not relatively prime to $s$.

Law D: If $r \perp s$, then $a \equiv b$ (modulo $rs$) if and only if $a \equiv b$ (module $r$) and $a \equiv b$ (modulo $s$).

Where $r, s, a, b$ are integers.

Suppose you have chosen numbers for $r$ and $s$, now let's say $a = krs + c$, for some integer $k$ and $c$.

Now we know $a \equiv c$ (modulo $rs$).

As $krs$ is multiple of $r$ and $s$ both, which implies

$a \equiv c$ (modulo $r$) and $a \equiv c$ (modulo $s$)

What I am doing wrong ?

Community
  • 1
Abhisek
  • 465
  • I was talking about your spelling: T-A-O-C-P. Never heard it called "T-O-A-C-P" before. –  Jan 02 '18 at 23:56

1 Answers1

1

One direction holds with no assumption on $r$ and $s$:

If $a\equiv b\pmod{rs}$ then $a\equiv b\pmod{r}$ and $a\equiv b\pmod{s}$

So if property D fails for $r$ and $s$ non coprime, you should be able to find particular values of $r$, $s$, $a$ and $b$ so that

  1. $a\equiv b\pmod{r}$
  2. $a\equiv b\pmod{s}$
  3. $a\not\equiv b\pmod{rs}$

Can you find suitable $a$ and $b$ for $r=s=2$?

egreg
  • 238,574
  • Suppose $a = 2$ and $b = 2$ then $2 \equiv 0$ (mod $r$), $2 \equiv 0$ (mod $s$) and $2 \equiv 2$ (mod $rs$), but as it is $\equiv$, we can choose $b$ for the $2 \equiv 0$ (mod $r$) and $2 \equiv 0$ (mod $s$) as $2$. Can't we ? – Abhisek Jan 01 '18 at 17:43
  • @Abhisek You're on the right track, but $a=2$ is good, whereas $b=2$ isn't: why not $b=0$, which is what you're actually using? – egreg Jan 01 '18 at 17:54
  • The $\equiv$ relation confused me($b = 2 \equiv 0 = b`$). We need to make sure the relation should satisfy for every $b$) not just one. Got it thanks – Abhisek Jan 01 '18 at 17:59