1

Is it safe to assume that if $a\equiv b \pmod {35 =5\times7}$

then $a\equiv b\pmod 5$ is also true?

Arnaud Mortier
  • 27,276
user6394019
  • 650

3 Answers3

0

The statement "$a \equiv b \text{ mod m}$" is equivalent to "There exists integer k such that $a = b + km$". If there exists $k_1$ such that $a = b +35k_1$, then we can set $k_2=7k_1$, and then $a = b+ 5k_2$. So $a \equiv b \text{ mod 35}$ does in fact imply $a \equiv b \text{ mod 5}$. This also follows trivially from the Chinese Remainder Theorem: if $a$ and $b$ represent the same element in Z$_{35}$, then they also represent the same element in Z$_5$x Z$_7$.

Acccumulation
  • 12,210
  • Speaking about chinese remainder theorem. Can I use it only when there is a sole x in the equation? suppose 10x is equivalent to 34 mod 63 ... Does the use of CRT is permitted? – user6394019 Jun 28 '18 at 16:20
  • $10x \equiv 34 \mod 63$ means $10x\equiv 34 \mod 9$ or in other words $x \equiv 7 \mod 9$, and that $10x \equiv 34 \mod 7$ or in other words that $3x \equiv 6 \mod 7$. So $x \equiv 2 \mod 7$ and $x \equiv 7\mod 9$ so $x \equiv 16\mod 63$ – fleablood Jun 28 '18 at 19:25
0

If $m | c$ and $c | a -b$, then $m |a -b$. Use this and the fact that

$$ a \equiv b \pmod{d} \iff d | a - b $$

qualcuno
  • 17,121
0

$a \equiv b \mod mn \implies mn|a-b$ and as $m|mn$ and $mn|a-b$ then $m|a-b$ so $a\equiv b \mod m$.

(Lemma: Divisibility is transitive. Pf: $a|b$ means there exists an integer, $k$, so that $ak = b$. $b|c$ means there exists an integer, $j$ so that $bj =c$. So $a(jk)=c$. So $a|c$.)

It does not work the other way, of course. $a\equiv b \mod m \not \implies a\equiv b \mod m$ but we can state:

$a \equiv b \mod m \implies a \equiv b + km \mod mn$ for some $k;0 \le k < n$. (And by Chinese Remainder theorem we know said $k$ is unique.

fleablood
  • 124,253