1
$\begingroup$

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.

  • 0
    @Marc I mean $(N modulo s).2012-03-11

1 Answers 1

1

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.