> It's not that each congruence gives you new information

So it's not that each congruence gives you N bits of information, and you want kN bits in total. It's more like each congruence has a 1/k chance of giving you the full kN bits.

But in some information theory sense those are the same! Or concretely, if you were testing a large quantity of numbers in parallel, you would get information from each congruence.