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?
3
-
$\begingroup$ Distributed uniformly within what set? (and what does "fix" mean?) $\endgroup$– Gerry MyersonCommented Oct 24, 2018 at 21:46
-
$\begingroup$ 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. $\endgroup$– AlexCommented Oct 25, 2018 at 20:38
-
$\begingroup$ 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. $\endgroup$– Gerry MyersonCommented Oct 25, 2018 at 22:02
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
1
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$.
answered Oct 24, 2018 at 19:05
-
$\begingroup$ 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^n1*p2^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. $\endgroup$– AlexCommented Oct 25, 2018 at 21:11