PlanetMath (more info)
 Math for the people, by the people. Sponsor PlanetMath
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS  
Login
create new user
name:
pass:
forget your password?
Main Menu
Owner confidence rating: High Entry average rating: Very high
[parent] special case of Dirichlet's theorem on primes in arithmetic progressions (Theorem)

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.

Let $ f(n)=\frac{n^q-1}{n-1}=1+n+n^2+\dotsb+n^{q-1}$ . Let $n>1$ be an integer, and suppose $p\mid f(n)$ . Then $n^q\equiv 1\pmod p$ which implies by Lagrange's theorem that either $q\mid p-1$ or $n\equiv 1\pmod p$ . 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\pmod q$ . Let $p$ be any prime divisor of $f(P)$ . If $p\equiv 1\pmod q$ , then $p\mid P$ which contradicts $f(P)\equiv 1\pmod P$ . Therefore, by the above $P\equiv 1\pmod p$ . Therefore $ f(P)\equiv 1+P+P^2+\dotsb+P^{q-1}\equiv 1+1+1+\dotsb+1\equiv q\pmod p$ . Since $q$ is prime, it follows that $p=q$ . Then $P\equiv 1\pmod p$ implies $P\equiv 1\pmod q$ . However, that is inconsistent with our deduction that $P\equiv 2\pmod q$ above. Therefore the original assumption that there are only finitely many primes congruent to $1$ modulo $q$ is false.

References

1
Henryk Iwaniec and Emmanuel Kowalski.
Analytic Number Theory, volume 53 of AMS Colloquium Publications.
AMS, 2004.




"special case of Dirichlet's theorem on primes in arithmetic progressions" is owned by bbukh.
(view preamble | get metadata)

View style:


This object's parent.
Log in to rate this entry.
(view current ratings)

Cross-references: inconsistent, product, divisor, prime divisor, Lagrange's theorem, implies, integer, modification, congruent, arithmetic progressions, primes, theorem

This is version 6 of special case of Dirichlet's theorem on primes in arithmetic progressions, born on 2004-09-10, modified 2007-03-13.
Object id is 6158, canonical name is SpecialCaseOfDirichletsTheoremOnPrimesInArithmeticProgressions.
Accessed 3565 times total.

Classification:
AMS MSC11N13 (Number theory :: Multiplicative number theory :: Primes in progressions)

Pending Errata and Addenda
None.
[ View all 7 ]
Discussion
Style: Expand: Order:
forum policy

No messages.

Interact
post | correct | update request | prove | add result | add corollary | add example | add (any)