3
$\begingroup$

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)
$\endgroup$
5
  • $\begingroup$ If you sample the $x_i$ values uniformly, then I imagine their remainders modulo $p$ is uniform, so that the following remainders modulo $q$ are also uniform. $\endgroup$ – Bill Wallis Jul 10 '18 at 19:08
  • $\begingroup$ That seems vaguely intuitive to me as well (and for my purposes, I'd like that to be true in general), but I'd like for someone to prove that if it is the case. Then again, it can't be completely true, right, since when q>p, we'll never get the larger modulo values, larger than p-1? $\endgroup$ – Steve Jul 10 '18 at 19:11
  • $\begingroup$ If $q<p$ and the samples are uniform $\bmod p$, they can be uniform $\bmod q$ only if $q|p$ (pigeonhole principle) $\endgroup$ – gammatester Jul 10 '18 at 19:12
  • $\begingroup$ An example of something I'd like to know if ever occurs, say we have sample (0,1,2,3,4,5,6.....20) in mod 21, is it possible to get a skewed distribution like (0,1,1,1,4,1,0,1,1,0,3) in mod 11 where there are "more 1s than expected"? $\endgroup$ – Steve Jul 10 '18 at 19:28
  • $\begingroup$ @Steve: If $p=2$, there's nothing stopping you from taking large values of $x$ like $x_0 = 384$ and $x_1 = -7447$. $\endgroup$ – user14972 Jul 10 '18 at 23:18
1
$\begingroup$

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$
$\endgroup$
2
  • $\begingroup$ This is fantastic and I think I roughly follow what you're saying and at least understand it's impact in a very generalized sense. In your explicit example, 1, 23, 45, 67, ..., 199, 221 are all 1 mod 11 while running across the 0,1,2,...,11 spectrum of values under mod 21. This is helpful because it allows me to refine my question back to my original post, however. What if we restrict ourselves to numbers which not only are sequential in mod 21, but rather are strictly sequential numbers (x, x+1, x+2, ...). Can we know anything about these numbers under mod q? $\endgroup$ – Steve Jul 11 '18 at 12:48
  • $\begingroup$ I'm realizing now, maybe my question is stupid and obvious afterall. Can you tell me if this follows? Let a, p, q be constant integers. Let x_n= ap+n for n={0,1,...p-1}. Then x_n (mod p) ≡ n. Observe that ap (mod q) ≡ B for some integer B. Thus, x_n (mod q) = ap+n (mod q) ≡n (mod q)+B, so the residues unders mod q are "uniformly distributed" save some wrapping around if q is smaller than p. Is this correct? $\endgroup$ – Steve Jul 11 '18 at 13:02
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.