2
$\begingroup$

Consider the following:

$\forall c\in\mathbb{Z}^{+}, a \equiv b \pmod n \Leftrightarrow a \equiv b,b+n,b+2n,..,b+(c-1)n \pmod {cn}$.

It seems false, so I suspect there is a typo in the statement, could anyone tell me where is it?

Thanks a lot.

  • 0
    @QiaochuYuan aha..it explains a lot.2011-09-28

1 Answers 1

2

It's correct: $\rm\: a\equiv b\pmod{n}\ $ iff $\rm\ \exists\ i:\ a = b + i\ n\:.\:$ By the Division Algorithm $\rm\: i = j + k\ c\:,\ \ 0\le j < c\:,\:$ so $\rm\: \exists\ i:\ a = b + i\ n\ $ iff $\rm\ \exists\ k,\:j,\ 0\le j < c:\ a = b + j\ n + k\ (c\:n)\:\equiv\: b + j\ n\pmod{c\:n}\:.$