Maths WorkshopMaths problems with full solutions
Exercise 1833Number theory › PrimesOlympiadAdded 3 Nov 2026

Primes of the form $4n+1$

#Dirichlet#arithmetic progression#primes

Statement

Show that there are infinitely many primes of the form 4n+14n+1 (using a Euclid-style argument).

Hint

If p1,…,pnp_1,\ldots,p_n are all primes ≡1(mod4)\equiv1\pmod4, consider N=(p1⋯pn)2+1N=(p_1\cdots p_n)^2+1.

Show solutionHide solution

Solution

Setup. Suppose finitely many primes pi≡1(mod4)p_i\equiv1\pmod4. Let N=(p1⋯pn)2+1N=(p_1\cdots p_n)^2+1.

Mod 4. N≡1+1≡2(mod4)N\equiv1+1\equiv2\pmod4. Any odd prime divisor qq of NN has p12⋯pn2≡−1(modq)p_1^2\cdots p_n^2\equiv-1\pmod q, so −1-1 is a QR mod qq. By Euler's criterion, this forces q≡1(mod4)q\equiv1\pmod4.

Contradiction. But qq must be one of the pip_i, and pi∣Np_i\mid N would give pi∣1p_i\mid1, contradiction.

Conclusion. Infinitely many primes ≡1(mod4)\equiv1\pmod4.