On Saturday 27 January 2007 18:07, Paul R. Pudaite wrote:
In the December 2006 issue of Am. Math. Monthly , Filip Saidak presents "A New Proof of Euclid's Theorem." Here's a concise rendition: Let f(x) = x^2 + x, let g[0] be a positive integer, and for n = 1, 2, 3, ..., let g[n] = f(g[n-1]). Then g[n] has at least n different prime factors. I omit the proof for those who might enjoy working it out for themselves.
Pretty, but it seems to me to be just a repackaging of Euclid's original proof and strictly inferior to it: to understand why this proof works, you need to understand exactly the same points as for Euclid's, plus a little extra obfuscating machinery. Question: Suppose you do this with some other integer polynomial f. Under what conditions are you guaranteed to get infinitely many prime factors of the iterates? Obviously not if f = aX^k for some a,k; is that the only way in which you can fail? -- g