FOM: Test Case for "Elementary" Proofs

[Lou van den Dries]

There is a very elementary proof of the n=1 case of Dirichlet's theorem:
given k > 1 there are infinitely many primes in the progression
[k+1, 2k+1, 3k+1, ...]. I can't resist indicating it (as i found it
myself in highschool, though of course it was well known as I learned
later from Dixon's history). The case k=10 will give the main idea:
if p is a prime number dividing x^{10}-1 but not x^5 -1 and also not
x^2 -1 (where x is some integer > 1), then by Fermat's little theorem
10 must divide p-1, that is, p must occur in the arithmetic progression
11, 21, 31, 41, ......
 Now, for x > 1 the prime factors of x^{10} -1 that are not among the
prime factors of x^5 -1 or x^2 -1 are prime factors of

   (x^{10} -1)/ (x^5 -1)(x^2 -1)  = x^3 + ..., -1.

By an euclidean type argument (as in "there are arbitrarily many primes")
one shows very easily that by letting x run through the integers > 1
one can produce given arbitrarily large primes dividing the
right hand side in the display above (by choosing x > 1 suitably).
These primes will indeed be in the above arithmetic progression.

(There are a few things to check here, and in general the argument
needs a careful counting of the degree of a polynomial, which turns out
to be the cyclotomic polynomial whose roots are the primitive k^th
roots of unity, but this is no real problem, and certainly elementary
according to any standards, I think.)

Actually, I already made a mistake, I now see: since x-1 is a common
factor of x^5 -1 and x^2 -1, I should compensate for this by
multiplying the LHS above by (x-1) (fortunately, since otherwise
the division would leave a remainder). So replace display above by

  (x^{10} -1) (x-1)/ (x^5 -1)(x^2 -1) = x^4 + ... + 1

Sorry. (In high school I didn't know about cyclotomic poly's, but I
did know that the division above would work for all x, and would
produce a number that grows like x^{\phi(k)}, where \phi(k) is
Euler's phi function. And that's enough.) 

Apologies for the nonfom nature of the message. -Lou van den Dries-