A point to ponder
by t0rajir0u, Jun 27, 2007, 5:11 AM
Recall the cyclotomic polynomials. As I recently learned from a problem given to me here at RSI, they can be used to quickly prove a subcase of Dirichlet's Theorem.
Problem: Given an integer
, show that there exist infinitely many primes of the form 
.
Solution: Consider the prime divisors of
for an arbitrary integer 
.
Lemma: Given an integer, a prime divisor 
of either divides or is congruent to 
.
Proof:
, so 
.
Case:
, in which case 
. Then, since
And
, it follows that
So
, as desired.
Case:
. Now, since the primitive 
roots of unity are distinct for distinct 
, it's not the case that divides 
for any 
. Correspondingly, 
. It follows that 
. Because 
we have 
, as desired.
Now, consider the set
It's well-known that
; hence if we restrict 
to primes we have a set of values of 
whose greatest common divisor is at best 
. This means that the other prime divisors of 
must be distinct for distinct .
In other words,
-
possibly contains the (finite) prime divisors of (by the lemma) and (by the previous argument.)
- contains an infinite number of primes. By the lemma, the primes that are not the finite primes above are congruent to .
QED.
This is a rather clever argument, and the original problem was proposed in stages to make it more obvious. There is probably a neater way to do that last bit, but the spirit of the intended solution remains.
Practice Problem (Hensel's Lemma): Let![$ F(x) \in \mathbb{Z}[x]$](//latex.artofproblemsolving.com/1/f/7/1f73e538a4166aa1eae2180883aff369592de36b.png)
, let be a prime, and let 
. Let 
be the highest power of dividing 
. Given that there exists 
such that 
is the highest power of dividing 
, prove that there exists an integer 
such that 
and 
.
(Hint: Expand
in powers of 
. )
Problem: Given an integer
, show that there exist infinitely many primes of the form 
.Solution: Consider the prime divisors of
for an arbitrary integer 
.Lemma: Given an integer
, a prime divisor 
of either divides or is congruent to 
.Proof:
, so 
.Case:
, in which case 
. Then, since
And
, it follows that
So
, as desired.Case:
. Now, since the primitive 
roots of unity are distinct for distinct 
, it's not the case that divides 
for any 
. Correspondingly, 
. It follows that 
. Because 
we have 
, as desired.Now, consider the set
It's well-known that
; hence if we restrict 
to primes we have a set of values of 
whose greatest common divisor is at best 
. This means that the other prime divisors of 
must be distinct for distinct .In other words,
-
possibly contains the (finite) prime divisors of (by the lemma) and (by the previous argument.)-
contains an infinite number of primes. By the lemma, the primes that are not the finite primes above are congruent to .QED.
This is a rather clever argument, and the original problem was proposed in stages to make it more obvious. There is probably a neater way to do that last bit, but the spirit of the intended solution remains.
Practice Problem (Hensel's Lemma): Let
![$ F(x) \in \mathbb{Z}[x]$](http://latex.artofproblemsolving.com/1/f/7/1f73e538a4166aa1eae2180883aff369592de36b.png)
, let be a prime, and let 
. Let 
be the highest power of dividing 
. Given that there exists 
such that 
is the highest power of dividing 
, prove that there exists an integer 
such that 
and 
.(Hint: Expand
in powers of 
. )
April 2009
March 2009