There is a simple non-analytic proof for $p\equiv 1 \bmod n$; see e.g. Proposition $3$ in [this note][1].

Edit:  [This paper][2] by Murty and Thain discusses obstructions to Euclid-style proofs for various congruence classes.  I believe that a proof has been carried out for $p\equiv a\bmod b$ for $(a, b)=1$ for all $b\leq 24$ in the style of Euclid, however.

Here is an open-access [paper][3] by Keith Conrad expositing this impossibility theorem and giving some background.


  [1]: http://stanford.edu/~dalitt/primes1mod4.pdf
  [2]: http://projecteuclid.org/DPubS?verb=Display&version=1.0&service=UI&handle=euclid.facm/1229442627&page=record
  [3]: http://www.math.uconn.edu/~kconrad/blurbs/gradnumthy/dirichleteuclid.pdf