The Residues modulo m of Products of Random Integers

Source 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 m . Our main result is an upper bound for the distance Δ m = sup x ∈[0,1] [mid ] P ( U/m [les ] x )− x [mid ]. 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 Δ m is given explicitly.