Chinese remainder theorem corollary.

Question

I was puzzled regarding corollary 31.29 of the Chinese remainder theorem as presented in the chapter on number theoretic algorithms by Cormen et al. I found another person who asked the same question here. When I look at the answer though, it doesn't make sense to me. It is said that "if a=b(mod n) then a=b(mod n_i) for any n_i|n. But, if n>n_i, then a from the first equation can take n values while the a in the second equation can take only n_i values. So, how can this hold in general? Here is what I think is a counter example -

100%%55 = 45

100%%11= 1

Here, b=100, n=55 and n_i=11 (right?). So how come the two equations don't produce the same result as the statement says they should?

Answer 1

There is no probem here, as $$ 45 = 1\mod 11 $$ or in other words: $$ 1 + 11\Bbb Z = 45 + 11\Bbb Z $$

---

The proof is actually easy: if $a=b\mod n$ then $n|(a-b)$, and if $n_i|n$ then, as the relation "divides" is transitive, $n_i|(a-b)$ as well. So $a=b\mod n_i$.