special case of Dirichlet’s theorem on primes in arithmetic progressions

The special case of Dirichlet’s theorem for primes in arithmetic progressions for primes congruent to $1$ modulo $q$ where $q$ itself is a prime can be established by the following elegant modification of Euclid’s proof (http://planetmath.org/ProofThatThereAreInfinitelyManyPrimes).

Let $f(n)=\frac{n^q-1}{n-1}=1+n+n^2+\mathrm{\cdots }+n^{q-1}$. Let $n>1$ be an integer, and suppose $p\mid f(n)$. Then $n^q\equiv 1(modp)$ which implies by Lagrange’s theorem that either $q\mid p-1$ or $n\equiv 1(modp)$. In other words, every prime divisor of $f(n)$ is congruent to $1$ modulo $q$ unless $n$ is congruent to $1$ modulo that divisor.

Suppose there are only finitely many primes that are congruent to $1$ modulo $q$. Let $P$ be twice their product. Note that $P\equiv 2(modq)$. Let $p$ be any prime divisor of $f(P)$. If $p\equiv 1(modq)$, then $p\mid P$ which contradicts $f(P)\equiv 1(modP)$. Therefore, by the above $P\equiv 1(modp)$. Therefore $f(P)\equiv 1+P+P^2+\mathrm{\cdots }+P^{q-1}\equiv 1+1+1+\mathrm{\cdots }+1\equiv q(modp)$. Since $q$ is prime, it follows that $p=q$. Then $P\equiv 1(modp)$ implies $P\equiv 1(modq)$. However, that is inconsistent with our deduction that $P\equiv 2(modq)$ above. Therefore the original assumption that there are only finitely many primes congruent to $1$ modulo $q$ is false.

Title	special case of Dirichlet’s theorem on primes in arithmetic progressions
Canonical name	SpecialCaseOfDirichletsTheoremOnPrimesInArithmeticProgressions
Date of creation	2013-03-22 14:35:38
Last modified on	2013-03-22 14:35:38
Owner	bbukh (348)
Last modified by	bbukh (348)
Numerical id	9
Author	bbukh (348)
Entry type	Theorem
Classification	msc 11N13