## Existence of prime congruent to 1 modulo n [closed]

I am studying the special cases of Dirichlet theorem for infinitude of primes in arithmetic progressions, that is, $$There \ are \ infinitely \ many \ primes \ that \ have \ the \ form \ of \ nk+1$$ for a given natural number $n$

It is rather well-known that this statement has a non-analytic proof. ( such as http://mathoverflow.net/questions/32624/special-cases-of-dirichlets-theorem/32635#32635 )

Among such papers one assume the negative and make the enumeration of finite such primes like $p_1,p_2, ..., p_t$. But in order to make such enumeration, one should first prove that at least one prime of form $nk+1$ exists, in advance.

This is the point of my question. What do I have to prove the existence of prime of form $nk+1$ ?

-
Just allow the empty enumeration. (In fact, your "simpler" goal implies the full force of this special case: if you want infinitely many primes congruent to $1$ mod $n$, just find one prime congruent to $1$ mod $nk$ for $k=1,2,\ldots$.) – Sean Eberhard Aug 19 at 8:37
Presumably you are asking about Lemma 1 in Daniel Litt's note? stanford.edu/~dalitt/primes1mod4.pdf If so, then the set P_f in his lemma can never be empty, just by its definition – Yemon Choi Aug 19 at 8:40
Right. I am asking about Lemma 1 in that paper. (I cannot post a comment in the answer post of Daniel Liff's in mathoverflow.net/questions/32624/… .. Do you know how can I?) But the non-emptiness of $P_f$ doesn't seem trivial for me.. – guldam Aug 19 at 8:46
Lemma 1 does not use that at least one prime of the form $nk+1$ exists. As Sean Eberhard points out, that's equivalent to the theorem. Lemma 1 does not even use that $|P_f| \ge 1.$ By the way, Lemma 1 can also be proved by counting. Count the numbers up to N divisible only by a fixed set of k primes (at most $(log_2N)^k$) and the numbers represented by the polynomial (at least cN^{1/\text{degree}}) and since the latter is asymptotically greater than the former the primes dividing nonzero values of the polynomial must be infinite. There is no special problem with the $k=0$ case. – Douglas Zare Aug 19 at 9:00
Oops!! I mis-read the definition of $P_f$ in Lemma 1. I just read 'for all natural number n, prime p divides f(n)' not 'a natural number n exists such that p divides f(n)'. Sorry for my silly mistake.. and thanks a kind comment all above me. – guldam Aug 19 at 9:21
show 1 more comment