Let π denote the number of primes of the form nk + m up to x. By the prime number theorem, extended to arithmetic progression, i.e., half of the primes are of the form 4k + 1, and half of the form 4k + 3. A reasonable guess would be that π > π and π < π each also occur 50% of the time. This, however, is not supported by numerical evidence — in fact, π > π occurs much more frequently. Indeed this inequalityholds for all primes x < 26833 except 5, 17, 41 and 461, for which π = π. Besides, the first primex such that π > π is 26861, i.e. π ≥ π for all primes x < 26861. In general, if 0 < a, b < n are integers, GCD = GCD = 1, a is a quadratic residuemodn, b is a quadratic nonresidue mod n, then π > π occurs more often than not. This has been proved only by assuming strong forms of the Riemann hypothesis. The stronger conjecture of Knapowski and Turán, that the density of the numbers x for which π > π holds is 1 > π, turned out to be false. They, however, do have a logarithmic density, which is approximately 0.9959....
Generalizations
This is for k = −4 to find the smallest prime p such that , however, for a given nonzero integer k, we can also find the smallest prime p satisfying this condition. By the prime number theorem, for every nonzero integer k, there are infinitely many primes p satisfying this condition. For positive integersk = 1, 2, 3,..., the smallest primes p are For negative integers k = −1, −2, −3,..., the smallest primes p are 2, 3, 608981813029, 26861, 7, 5, 2, 3, 2, 11, 5, 608981813017, 19, 3, 2, 26861, 2, 643, 11, 3, 11, 31, 2, 5, 2, 3, 608981813029, 48731, 5, 13, 2, 3, 2, 7, 11, 5, 199, 3, 2, 11, 2, 29, 53, 3, 109, 41, 2, 608981813017, 2, 3, 13, 17, 23, 5, 2, 3, 2, 1019, 5, 263, 11, 3, 2, 26861,... For every nonsquare integer k, there are more primes p with than with more often than not. If strong forms of the Riemann hypothesis are true.
Let m and n be integers such that m≥0, n>0, GCD = 1, define a function, where is the Euler's totient function. For example, f = f = 1/2, f = f = 0, f = 1/2, f = 0, f = 5/6, f = f = 1/2, f = f = 0, f = 1/3, f = 1/2, f = f = f = 0, f = 5/6, f = f = 0, f = f = 1/2, f = 1/3. It is conjectured that if 0 < a, b < n are integers, GCD = GCD = 1, f > f, then π > π occurs more often than not.
