0

Let N is a large odd number. What is known regarding distribution of remainders after division of N by 3,5,...,fix(sqrt(N))? Are they distributed mode or less uniformly?

Alex
  • 61
  • Distributed uniformly within what set? (and what does "fix" mean?) – Gerry Myerson Oct 24 '18 at 21:46
  • Dear Gerry: under "fix" I mean "integer part" (the Matlab notation). Also, I've meant within interval (0,sqrt(N)). Are there any result known in this regard? Thank you very much for your interest. – Alex Oct 25 '18 at 20:38
  • The remainders after division by the small primes will be nowhere near $\sqrt N$, so it's hard to see any chance for uniform distribution. – Gerry Myerson Oct 25 '18 at 22:02

1 Answers1

0

In order for the remainder to be $r$ (where $0 \le r < \sqrt{N}$), we need $N-r$ to have an odd divisor $m$ with $\max(r,1) < m \le \sqrt{N}$. It can't happen if $N-r$ is prime; on the other hand, if $N-r$ is a product of many small primes and $r$ is not too close to $\sqrt{N}$ there should be lots of such $m$.

Robert Israel
  • 53,594
  • Robert, thank you very much; this seems to be the answer. Thus, all remainders _r = N-p where _p is a prime are excluded. More generally: if _r: 0 <= r < sqrt(N) is a remainder, and _N-r = p1^n1p2^n2...pk^nk, where _pj are primes and 0<=nj, than after division of _N by all odd numbers between 3 and sqrt(N) the remainder _r will appear [(n1+1)(n2+1)*...(nk+1)-2] times. Is this right? Thus, the distribution of the remainders is in fact highly non-uniform. – Alex Oct 25 '18 at 21:11