# Reference for a conjecture on the first primes congruent to 1 modulo other primes

Given a prime $p$, define $f(p)$ to be the smallest prime congruent to $1$ modulo $p$. For example, $f(7)=29$. It has been conjectured that $f(p)<p^2$ always: by Schinzel in his "Hypothesis H" paper with Schinzel (Acta Arith. 1958), and also by Kanold (Arch. Math. 1963). Of course this is also related to Linnik's theorem, and to the conjecture of Chowla that $f(p) \ll_\varepsilon p^{1+\varepsilon}$. (And all of these conjectures hold for any reduced residue class $a\pmod p$, not just $1\pmod p$.)

One surprising consequence of the conjectured bound $f(p)<p^2$ is that the function $f$ is injective! For if not, then there exist primes $p_1<p_2$ such that $f(p_1)=f(p_2)=q$. But then both $p_1$ and $p_2$, hence their product, divides $q-1$, and so $p_1^2<p_1p_2\le q-1<q=f(p_1)<p_1^2$, a contradiction.

Does anyone know where this latter conjecture - the injectivity of $f$ - appears in the literature? (with or without the relationship to the first conjecture)

(For that matter, if anyone knows where the aforementioned conjecture of Chowla appears in the literature, I'd be happy for that pointer as well.)

There are even stronger conjectures in the literature:

1) D.R. Heath-Brown, Almost-primes in arithmetic progressions and short intervals. Math. Proc. Cambridge Philos. Soc. 83 (1978), no. 3, 357–375. http://journals.cambridge.org/action/displayAbstract?fromPage=online&aid=2079092

quoting from the first few lines: "... if $(l,k)=1$, there exists a prime $p$ satisfying $$p \equiv l \bmod k, \quad p\leq k^2, \quad (k\geq 2).$$ Indeed the bound for $p$ may presumably be reduced to $p \ll k(\log k)^2$. "

Actually, Heath-Brown unconditionally proves that there are many (i.e. the expected number) $P_2$ numbers smaller than $k^{2-\delta}$, for small $0\leq \delta \leq 0.035$. Maybe this gives a partial result for your injectivity question.

Further references:

A paper by A. Granville (Least primes in arithmetic progressions. Th\'{e}orie des nombres (Quebec, 1987), 306–321, de Gruyter, Berlin, 1989) http://www.dms.umontreal.ca/~andrew/1989.htm

points to an even more explicit version of a least prime conjecture: following a heuristic of Wagstaff, see http://www.ams.org/journals/mcom/1979-33-147/S0025-5718-1979-0528061-7/ , McCurley observed that this heuristic implies: $\lim\sup_{k\rightarrow \infty} \frac{p(k)}{k(\log k)^2} =2$.

A final comment: Your function $f(p)$ is (presumably) injective on the primes, but not on all integers. (Say 11 is the least prime 1 mod 10, and the least 1 mod 5). This may explain why others, possibly, did not study the question from your point of view.

Update: Computing the first values of least primes 1 mod p, and checking the OEIS http://oeis.org/A035095

where we find the comment:

"Formula: According to a long-standing conjecture (see the 1979 Wagstaff reference), a(n) <= prime(n)^2+1. This would be sufficient to imply that a(n) is the smallest prime such that greatest prime divisor of a(n)-1 is prime(n), the n-th prime: A006530(a(n)-1)=A000040(n). This in turn would be sufficient to imply that no value occurs twice in this sequence. - Franklin T. Adams-Watters, Jun 18 2010"

It seems, the last half sentence is the injectivity you are looking for, based on an explicit bound of your $f(p)$.

Further, in http://oeis.org/A066674 we find the discussion, if the two sequences above are the same, with related comments by Poonen and Bach.

• Oooo, that's a tantalizing lead! I've contacted Franklin to see if he has any additional information. – Greg Martin Nov 25 '13 at 20:43
• As far as I can tell, the conjecture is original to Franklin T. Adams-Watters and appeared only on the OEIS web site. Bounty earned - thank you! – Greg Martin Dec 1 '13 at 1:20

For your parenthetical request: S. Chowla, On the least prime in an arithmetic progression. J. Indian Math. Soc. 1 (1934) 1-3.

• Thanks very much! Any chance you know of a way to get an electronic copy of that old paper? – Greg Martin Nov 25 '13 at 20:43
• @GregMartin I'm sorry, I do not. – S. Carnahan Nov 26 '13 at 11:09
• @GregMartin, Chowla's collected works have been published by the University of Montreal - ams.org/mathscinet-getitem?mr=1829817 - you might be amused to see that the MSN reviewer says this is a good thing because "many of Chowla's papers are difficult to locate" – Nick Gill Nov 26 '13 at 15:35
• Also, I think Scott's reference should have "arithmetical" rather than "arithmetic" in the title (according to the contents page of the collected works). – Nick Gill Nov 26 '13 at 15:36