The residues modulo m of products of random integers

Abstract

For two stochastically dependent random variables X and Y taking values in {0,..., m - 1}, we study the distribution of the random residue U = XY mod in. Our main result is an upper bound for the distance Delta(m) = sup(xis an element of[0,1]) P(U/m less than or equal to x) - x. For independent and uniformly distributed X and Y, the exact distribution of U is derived and shown to be stochastically smaller than the uniform distribution on {0,..., m - 1}. Moreover, in this case Delta(m) is given explicitly.