# Algorithm for keeping a concrete version of Euclid's argument simple

(My actual question is at the very bottom of this posting.)

Suppose you're teaching a course in mathematics-for-liberal-arts majors and it's the last math course they'll ever take. It has almost no prerequisites---say no algebra beyond solving quadratic equations and probably not even that.

Over a period of three weeks you've gotten them accustomed to the idea that consecutive integers can never have any prime factors in common. You don't prove this by a method that uses algebra (since then their attention would be on struggling to understand the algebra) but rather you've pointed out that if 56 is a multiple of 7, then the next multiple of 7 isn't due until 7 units later, and the last 7 units earlier, so 55 and 57 certainly cannot be multiples of 7. They've turned in homework on this idea; they've done in-class quiz problems on it.

Then you tell them: say we start with some finite list of prime numbers, e.g. $5$ and $7$. Mutliply them and get 35. Consider two consecutive integers, 35, and 36. They can't have prime factors in common: \begin{align} 35 & = 5\times 7 \\ 36 & = 2\times2\times3\times 3 \end{align} So you get some additional prime numbers that you now add to your list: $$5, 7, 2, 3$$ Now iterate $2\times3\times5\times 7 = 210$. Suppose this time we consider the consecutive integers 210 and 209, where I've chosen 209 rather than 211 because its prime factors aren't very big: \begin{align} 210 & = 2\times3\times5\times 7 \\ 209 & = 11\times 19 \end{align} Add this to the list: $$2, 3, 5, 7, 11, 19$$ Iterate: $2\times3\times5\times7\times11\times19=43890$.

Here's an unpleasant fact: $43889$ and $43891$ are prime. I can't pick one to keep the arithmetic moderately comfortable.

Of course all of this that one presents in class will be a story with a moral: this is how you prove that the prime numbers will always keep on going; your finite list can never be complete.

My question: Is there some way to churn out examples of reasonable starting sets and choices of $\pm1$ (such as I made in the case of $210$) that will let this go on for a fairly large number of steps without getting really big primes?

-
If I understand the question correctly, you don't really need an algorithm; it would be enough to have the (finite!) list of good starting sets/paths that don't exceed the "reasonable"/"moderately comfortable" criterion. Right? – ShreevatsaR Oct 12 '11 at 19:13
I notice that if I'd picked $34$ instead of $36$, I get: $5,7,2,17$, and then again subtracting $1$ rather than adding $1$ I get: $5, 7, 2, 17, 29, 41$. If on the next step I add $1$ rather than subtracting $1$, I get $5, 7, 2, 17, 29, 41, 3, 19, 103, 241$. One more step and I have the option of adding $13, 105727, 1456561$ to the list or else getting a 13-digit prime number. Could just doodling like this be the most efficient way to construct pedagogically good examples? – Michael Hardy Oct 12 '11 at 19:21
@ShreevatsaR: For the particular purpose mentioned here that's probably right. Another thought comes to mind: suppose some unpleasantly large number comes along, and we admit it, and go on from there; could it be that at the very next step we can get a long list of fairly small primes? – Michael Hardy Oct 12 '11 at 19:25

Instead of adding or subtracting 1, you can always divide the product of the current primes in two halves and look for a small sum or difference, following your example you could add $$3\times 7 \times 19 - 2 \times 5 \times 11 = 17^2$$ as in Euclid's argument no known prime divides this difference as they divide just one of the terms in the left. But this is slightly more difficult to explain and I'm not sure if this is what you are looking for.
Even with this idea you can't go too far into the primes as the numbers becomes huge rather fast. Starting from 2 and 3 and adding in every step the difference with least largest prime factor we get the following chain: \begin{align} 3 + 2 &= 5 \\ 2 \times 5 - 3 &= 7 \\ 3 \times 7 - 2 \times 5 &= 11 \\ 5 \times 11 - 2 \times 3 \times 7 &= 13 \\ 2\times 7 \times 13 - 3\times 5 \times 11 &= 17 \\ 2 \times 3 \times 11 \times 17 - 5 \times 7 \times 13& = 23 \times 29 \\ 7 \times 13 \times 17 \times 23 - 2 \times 3\times 5 \times 11 \times 29 &= 19 \times 37^2 \\ 5 \times 13 \times 19 \times 23 \times 29 \times 37 - 2 \times 3 \times 7 \times 11 \times 17 &= 47 \times 73 \times 83 \times 107 \end{align} the next term is \begin{align} & 3\times 5\times 11\times 17\times 23\times 37\times 73\times 107 - 2\times 7\times 13\times 19\times 29\times 47\times 83 = \\ &59\times 97\times 103\times 173\times 179 \end{align} but I haven't been able to compute the next one.