Apologies for not posting in awhile. Life's been busy In any case, Rational Solutions to Polynomials, Part III will have to wait because I'd like to take a moment to discuss some interesting ideas involved in solutions to USAMO 2008 #1. (By the way, for those of you wondering, I seriously doubt I made top 12 )

Problem: Prove that for each positive integer , there are pairwise relatively prime integers , all strictly greater than , such that is the product of two consecutive integers.

This post assumes familiarity with the official solutions. In the following post, "the first solution" refers to the first official solution of #1, and so forth.

The first solution is straightforward. The second solution requires some elaboration. In particular, it may not be clear why there are an infinite number of primes with quadratic residue .

Proposition: if and only if or (equivalently, ).

Proof 1. . By quadratic reciprocity,

$ \begin{eqnarray*} \left( \frac { - 3}{p} \right) & = & \left( \frac { - 1}{p} \right) \left( \frac {p}{3} \right) ( - 1)^{\frac {( - 3 - 1)(p - 1)}{4} } \\ & = & ( - 1)^{p - 1} \left( \frac {p}{3} \right) ( - 1)^{ - (p - 1)} \\ & = & \left( \frac {p}{3} \right) \\ \end{eqnarray*}$

and we know that are the quadratic residues .

Proof 2. If then , so . If , then and



so, in other words, the order of is . We write this . Because is a cyclic group of order , this is possible if and only if . In particular, let be a generator; then $ x = g^{\frac {p - 1}{3} }, g^{ 2 \frac {p - 1}{3}$ are the elements of order .

---

Note that the lemmas from the third solution now allow us to conclude that there are an infinite number of primes congruent to . A similar proof is possible for primes congruent to using . There are in fact other similarities: primes congruent to take the form and primes congruent to take the form (equivalently, ) (the proof is left as an exercise). The underlying concept here, analogous to the Gaussian integers, is the Eisenstein integers.

The first proof of the above proposition generalizes to all integer quadratic polynomials (complete the square). The second proof generalizes to the cyclotomic polynomials, as follows:

In a a previous post of mine (that motivated the ideas I used to do this problem), I used ideas similar to (but messier than) the third solution to prove that there were an infinite number of primes congruent to for any . We give a fuller proof of a key result from that post here, which generalizes the relevant part of Proof 2.

Lemma: .

Proof. Consider the factorization of the polynomial . Its roots consist of the elements of order dividing . Note that the elements of order dividing divide . We can then prove by strong induction on the divisors of (in increasing order) that the elements of order are precisely the roots of . The conclusion follows when .

It then follows that as before.

N.B. The first solution also generalizes to cyclotomic polynomials using the identity for a prime not dividing . The case gives , which is the crux of the first solution.

---

The elementary arguments that there are an infinite number of primes congruent to (using the polynomials respectively) along with the above argument begs the following question: are there other polynomials that allow us to prove other special cases of Dirichlet's theorem using the lemmas in the third solution? (My current opinion is "no." In the next post I may discuss an even more elegant way to phrase the above discussion that demonstrates some of the ideas that lead into the full proof of Dirichlet's theorem.)

---

Practice Problem 1: Show that the product of two integers expressible in the form is also expressible in that form.

Practice Problem 2: Show that the primes of the above form are precisely and the primes congruent to .

(Not really a practice) Problem 3: Show that there are an infinite number of primes congruent to .