# Remainders of primes

Maybe an idiot question but I can't find any info! We divide successive prime numbers by some fixed prime number $n$ (e.g. 7 or 17). We'll get some remainders $r[i]= 1..n-1$ Is there any law or theorem about their distribution? It seems Fermat's Little theorem and Chinese remainder theorem don't work.. I've tried it in Mathematica and it seems remainders are chaotic. But "Poincaré 3D view" $\{ r[i],r[i-1],r[i-2]\}$ shows some lines and nets.

UPD Thanks to everybody, esp. TonyK! It seems the answer is:

Let $\mathbb{P}(d)$ - probabilty for distance between successive primes to be $d$. (It depends on value of "first" number and known only numerically). If some prime number $p_1$ has reminder $r_1$ when divided by $n$, than probability for the next prime $p_2$ to have reminder $r_2$ is: $$\sum_{k=0}^{\infty} \mathbb{P}(r_2-r_1+k \cdot n)$$

-

1
$0$ will appear at most once. – Henry Dec 30 '12 at 14:47

## 1 Answer

The Wikipedia article Dirichlet's theorem on arithmetic progressions answers your question:

...different arithmetic progressions with the same modulus have approximately the same proportions of primes. Equivalently, the primes are evenly distributed (asymptotically) among each congruence class modulo d.

In other words, for any $k$ with $0 < k < n$, the proportion of integers $i$ such that $r[i] = k$ is equal to $1/(n-1)$ (since $n$ is prime).

More formally: Given an integer $N > 0$, let $p_N(k)$ be the proportion of integers $i$ with $0 < i \le N$ such that $r[i] = k$. Then $p_N(k)$ tends to $1/(n-1)$ as $N$ tends to $\infty$.

It is possible to make a more precise statement concerning the rate of convergence of $p_N(k)$, but I don't expect that any more concrete result is possible.

-

Aha.. Many thanks! But for small $N$ some regularity appears. Is there some ideas about it? – lesobrod Dec 30 '12 at 15:59
Perhaps you are just imagining patterns in random data? People do that a lot, you know :-) (And do you mean small $N$, or small $n$?) – TonyK Dec 30 '12 at 16:11
Oh $n$ sorry.. What about patterns.. Reminders itself equally distributed with no doubts. But now I start analysis for pairs and triads 'cause it seems they have a big correlations... – lesobrod Dec 30 '12 at 16:37
Good luck with that... – TonyK Dec 30 '12 at 16:39
@lesobrod Primes get more 'rare' as you get to large numbers. Any kind of 'regularity' that you see in small cases, go out the window. For example, there exists strings of composite numbers of arbitrary length, since $N!+2, N!+3, \ldots, N!+N$ are all composite. – Calvin Lin Dec 30 '12 at 16:45
show 4 more comments
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 32, "mathjax_display_tex": 1, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 20, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9330188632011414, "perplexity_flag": "middle"}