How are numbers distributed under a different modulus

Question

Suppose we take a sample of numbers with unique congruence class modulo p:

x_0 ≡ 0 (mod p)
x_1 ≡ 1 (mod p)
x_2 ≡ 2 (mod p)
...
x_(p-2) ≡ p-2 (mod p)
x_(p-1) ≡ p-1 (mod p)

and we then examine their class under modulo q. How will these classes be distributed? For example, will some values appear more often than others? Or might they be uniform in number or all unique? I imagine this result would depend on if p<q or p>q, and perhaps other things.

Specific, numerical example

15 = 5(3) ≡ 0 (mod 5)
26 = 5(5)+1 ≡ 1 (mod 5)
37 = 5(7)+2 ≡ 2 (mod 5)
58 = 5(11)+3 ≡ 3 (mod 5)
69 = 5(13)+4 ≡ 4 (mod 5)

and

15 ≡ 1 (mod 2)
26 ≡ 0 (mod 2)
37 ≡ 1 (mod 2)
58 ≡ 0 (mod 2)
69 ≡ 1 (mod 2)

and

15 ≡ 3 (mod 6)
26 ≡ 2 (mod 6)
37 ≡ 1 (mod 6)
58 ≡ 4 (mod 6)
69 ≡ 3 (mod 6)

Answer 1

If you take any $q$ successive numbers, there will be one in each congruence class $\bmod q$. You start with the lowest one in its class, the next is in the next class up, and so on, wrapping around at $0$. When you get to $q$ you have put one in each class and are ready to start again. If you take $p$ successive numbers where $q\not | p$ you will have two different counts among the congruence classes. Let $r$ be the remainder on dividing $p$ by $q$. There will be $q-r$ classes with $\lfloor \frac pq \rfloor$ because you go around fully that many times. There will be $r$ classes with one more because you have $r$ numbers left after the full cycles.

Answer 2

Recall the Chinese Remainder Theorem; in one form, it says that if $p$ and $q$ are relatively prime integers, then there is a bijective correspondence between the

• residue classes modulo $pq$
• pairs consisting of a residue class modulo $p$ and a residue class modulo $q$

Furthermore, given any integer $x$, its residue classes modulo $pq$, $p$ and $q$ are related by this correspondence.

In particular, integers fall into every combination of residues modulo $p$ and $q$, and they do so exactly once per period of length $pq$. So knowing the residue class of an integer modulo $p$ tells you absolutely nothing about its residue class modulo $q$.

And while the notion of a uniform distribution doesn't actually make sense for the integers, this periodic behavior still allows us to capture the idea that such a thing would have independent distributions modulo $p$ and $q$.

In the example of taking $p=21$ and $q=11$, we can give this bijection by explicit formula (discussions of the CRT should show how to obtain this):

• $22 x - 21 y \equiv x \bmod 21$
• $22 x - 21 y \equiv y \bmod 11$

Similarly, any other integer with the same residue as $22x - 21y \bmod 231$ will also satisfy these congruences.

So, given any choice of twenty-one residue class modulo 11, you could find a sequence of $x$'s that have the chosen residues $\bmod 11$ along with the required residues $\bmod 21$. For example, if you want all $1$'s, then we can take

$$ x_n = 1 + 22(n-1) $$

to get

• $x_n \equiv n \bmod 21$
• $x_n \equiv 1 \bmod 11$