From: Kurt Foster Subject: Re: Regularity of prime numbers Date: Fri, 22 Oct 1999 15:40:12 GMT Newsgroups: sci.math Keywords: Dirichlet, primes in arithmetic progression In <7uooqa$j2$1@ash.prod.itd.earthlink.net>, Tralfaz said: . Has there been any research on how evenly distributed the primes are . modulo a certain number? Yes, a great deal. . I know Direlict showed that there are an infinite number of primes . congruent to A mod B (A,B) = 1, but I don't know how that would affect . this problem. Dirichlet (note spelling) proved a bit more; namely B > 1 and any A with (A,B) = 1, then LIMIT, s -> 1+, [SUM, p == A (mod B), 1/p^s]/[SUM, all p, 1/p^s] = 1/phi(B) This is weaker than saying the "natural" density of p == A (mod B) is 1/phi(B), but it is enough to show that, if the natural density does exist then it must be 1/phi(B). Subsequent authors have proven that the "natural" density is indeed 1/phi(B), and given various estimates for how small the irregularities of distribution must be, how large they can be, and how often the difference between the number of p == A1 (mod B), p =< X and p == A2 (mod B), p =< X can change sign, when NOT(A1 == A2 (mod B)). ============================================================================== From: Robin Chapman Subject: Re: Regularity of prime numbers Date: Fri, 22 Oct 1999 16:17:39 GMT Newsgroups: sci.math In article <7uooqa$j2$1@ash.prod.itd.earthlink.net>, "Tralfaz" wrote: > Has there been any research on how evenly distributed the primes are modulo > a certain number? > > E. g. given the first 100000 primes > > Approximately 50000 are 1 mod 3 > Approximately 50000 are 2 mod 3 > > Approximately 25000 are 1 mod 5 > Approximately 25000 are 2 mod 5 > Approximately 25000 are 3 mod 5 > Approximately 25000 are 4 mod 5 > > etc. > > I know Direlict showed that there are an infinite number of primes congruent > to A mod B (A,B) = 1, but I don't know how that would affect this problem. By combining the standard proof of Dirchlet's theorem and the prime number theorem, one obtains the result that the number of primes <= x in a given congruence class modulo n and coprime to n is asymptotic to (1/phi(n)) x/log x. So to a first approximation the primes are equally distributed modulo n. However one finds, say, that the primes = 3 mod 4 seem to be slightly more numerous than those = 1 mod 4. For an interesting article on this phenomenon see M. Rubenstein & P. Sarnak, Chebyshev's bias, Experimental Mathematics, vol 3., 173-197 (1994). -- Robin Chapman http://www.maths.ex.ac.uk/~rjc/rjc.html "`Well, I'd already done a PhD in X-Files Theory at UCLA, ...'" Greg Egan, _Teranesia_ Sent via Deja.com http://www.deja.com/ Before you buy. ============================================================================== From: erick@sfu.ca (Erick Bryce Wong) Subject: Re: Regularity of prime numbers Date: 23 Oct 1999 11:26:38 GMT Newsgroups: sci.math Tralfaz wrote: >Along the lines of Dirichlet, it appears that given a and b where (a,b) = 1 >and the equation y = ax + b, that the lowest prime generated would occur >when x < a. Has this been proven? Linnik showed that there exists an L such that regardless of b, the lowest prime is at most a^L. This L is therefore known as Linnik's constant. The web page has a nice writeup on it. So far it is known that L <= 5.5, so that x < a^(9/2), but it is an unsolved conjecture whether L = 2 (whence x < a). It is, however, known that x < a for "almost all" a. -- Erick ============================================================================== From: Kurt Foster Subject: Re: Regularity of prime numbers Date: Sat, 23 Oct 1999 22:22:36 GMT Newsgroups: sci.math In <7ursva$qhm$1@fir.prod.itd.earthlink.net>, Tralfaz said: [snip] . Along the lines of Dirichlet, it appears that given a and b where . (a,b) = 1 and the equation y = ax + b, that the lowest prime generated . would occur when x < a. Has this been proven? [snip] It's NEVER true for ANY modulus a > 1. The least prime p == 1 (mod a) always satisfies p >= a+1, because 1 isn't prime. Even ignoring the "exceptional" remainder b = 1, however, it's still only true for a few small values of a, those with the property that every integer in (1, a) which is relatively prime to a, is actually a prime number. The largest value of the modulus a with this property is a = 30. [Every number with this property must be divisible by the product of all the primes less than its square root. But this requires that, if p is the largest prime < sqrt(a), and P is the next prime after p, then 2*3*...*p < P^2. This is true for P = 3, 5 and 7 only. The product grows MUCH faster than the square of the next prime. However [see one of the other followups] there is a universal exponent L such that p < a^L always holds, p the least prime == b (mod a), where b is relatively prime to a.