Elementary proof of existence of a prime in an arithmetic sequence Let $a,n$ be positive integers with $(a,n) = 1$. Then by Dirichlet's theorem on primes in an arithmetic progression we know that there are infinitely many primes $p$ satisfying $p\equiv a\pmod n$.
Dirichlet's theorem uses analytic number theory. I was wondering if there exists an elementary proof (not only meaning not using complex functions, but also relatively easy) of the existence of any (not infinitely many) prime in such an arithmetic progression. I couldn't come up with a proof myself.
 A: I don't know if this answers your question, but there is a simple proof that for all $n\geqslant 2$, there exists an infinite number of primes $p$ such that $p\equiv 1[n]$. Let $\Phi_n$ the $n$-th cyclotomic polynomial. We first prove that if $p$ is a prime number such that there exists $a\in\mathbb{Z}$ such that $p\mid\Phi_n(a)$ and $p\nmid \Phi_d(a)$ for all $d|n$ and $d<n$, then $p\equiv 1[n]$. Since
$$ X^n-1=\prod_{d|n}\Phi_d $$
$p|a^n-1$ and thus the order of $a$ in $(\mathbb{Z}/p\mathbb{Z})^*$ divides $n$. Let $d$ a divisor of $n$ with $d<n$, we have
$$ \overline{a}^d-1=\prod_{k|d}\overline{\Phi_k(a)} $$
in $\mathbb{Z}/p\mathbb{Z}$. But by hypothesis $\overline{\Phi_k(a)}\neq 0$ for all $k|d$ (because $k|n$ and $k<n$). Since $\mathbb{Z}/p\mathbb{Z}$ is a field, the above product is non-zero and thus $\overline{a}^d-1\neq 0$. This means that the order of $a$ in $(\mathbb{Z}/p\mathbb{Z})^*$ is $n$, and thus $n|p-1$ that is to say $p\equiv 1[n]$.
Now let $n\geqslant 2$ and let us suppose there is a finite number of primes $p_1,\ldots,p_s$ such that $p_i\equiv 1[n]$ for all $i$ and let $N=np_1\ldots p_s$. Let $Q=\prod_{d|N,d<N}\Phi_d$, then $Q\wedge\Phi_N=1$, by Bezout's theorem there exists $U,V\in\mathbb{Q}[X]$ such that $U\Phi_N+VQ=1$. Let $a\in\mathbb{Z}$ such that $aU,aV\in\mathbb{Z}[X]$. There is an infinite number of such $a$ so we can chose one such that $\Phi_N(a)\notin\{-1,0,1\}$. Let $p$ a prime divisor of $\Phi_N(a)$, then $\overline{a}^N=1$ in $\mathbb{Z}/p\mathbb{Z}$, thus $p\nmid a$ and $p\nmid Q(a)$, otherwise $p$ would divide $aU\Phi_N(a)+aVQ(a)=a$ which is not. Because of the lemma, $p\equiv 1[N]$ and since $n|N$, $p\equiv 1[n]$ but $p$ is not among the $p_i$ because $p\geqslant 1+N>p_i$ for all $i$.
