Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let me ask the following.

let S(n) be the set of positive integers less than n;
let N be a larger integer than n,for example N=100*n;
let M(n,N) be the set of ( N modulo s ) for any s in S(n);

Can I expect that M(n,N) tends to be more random for larger N?

Thank you in advance.

share|cite|improve this question
How do you define "more random"? – utdiscant Mar 11 '12 at 10:14
It also depends on what you mean by "tends" – Henry Mar 11 '12 at 10:20
Do you mean $n$ modulo $s$? – Marc van Leeuwen Mar 11 '12 at 11:15
@Marc I mean $(N modulo s). – seven_swodniw Mar 11 '12 at 11:30
up vote 1 down vote accepted

The values $(N\bmod s)_{s=0,\ldots,n-1}$ won't be random at all unless $N$ is taken to be random (in some range), so I'll suppose you meant to say that. Even so, these values will never be independent since whenever $d$ divides $s$ the value $N\bmod s$ fully determines $N\bmod d$, and more generally there is dependency for every pair of moduli that are not relatively prime. The total number of $n$-tuples of values that are possible by varying $N$ is not $n!$, which is the number of lists of values that are individually possible at their position, but it is the least common multiple $L=\mathrm{lcm}(1,2,\ldots,n)$.

The value of $N$ is relevant only modulo $L$, and using the Chinese remainder theorem one can easily show that as $N$ runs through all classes modulo $L$, the list $(N\bmod s)_{s=0,\ldots,n-1}$ runs through all possible $n$-tuples (those that satisfy all the obligatory relations for such lists). So if you let $N$ be a uniformly distributed random number in the range $0,\ldots,L-1$, then these lists are as random as they ever get, but that however is not very random.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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