\frac12(q-1)$. \end{lemma} \begin{proof} For squarefree positive integers $d\le q-1$, the residue classes $d+q\Z$ are distinct and contained in $S_q$. By \cite{rogers}, the number of such $d$ is at least $\frac{53}{88}(q-1)>\frac12(q-1)$. \end{proof} In addition, we need one further input from algebraic geometry: \begin{lemma}\label{l:hyp} Let $q$ be an odd prime number and $a\in(\Z/q\Z)^\times$. \begin{itemize} \item[(i)]If $q\ne5$ or $q=5$ and $a\ne3+5\Z$ then there exists $x\in(\Z/q\Z)^\times$ such that $\left(\frac{x+a/x}{q}\right)\ne1$. \item[(ii)]If $q\notin\{7,13\}$ then there exists $x\in(\Z/q\Z)^\times$ such that $\left(\frac{x^6+a}{q}\right)\ne1$. \end{itemize} \end{lemma} \begin{proof} We consider the sum $$ \sum_{x\in(\Z/q\Z)^\times}\left(\frac{x+a/x}{q}\right) =\sum_{x\in(\Z/q\Z)^\times}\left(\frac{x(x^2+a)}{q}\right). $$ For $q\ge3$, $x(x^2+a)$ has no repeated zeros in $\Z/q\Z$, so that $$ \{(x,y)\in(\Z/q\Z)^2:y^2=x(x^2+a)\} $$ are the affine points of an elliptic curve. For any fixed $x\in\Z/q\Z$, the number of $y\in\Z/q\Z$ such that $y^2=x(x^2+a)$ is $1+\left(\frac{x(x^2+a)}{q}\right)$. In addition, the curve has one point at infinity, so by the Hasse bound, we have $$ 1+\sum_{x\in\Z/q\Z}\left(1+\left(\frac{x(x^2+a)}{q}\right)\right) \le q+1+2\sqrt{q}, $$ whence $$ \sum_{x\in(\Z/q\Z)^\times}\left(\frac{x(x^2+a)}{q}\right)\le 2\sqrt{q}. $$ This last estimate is less than $q-1$ provided that $q\ge 7$, and we check the claim for $q\in\{3,5\}$ directly. Similarly, for $q\ge5$, $x^6+a$ has no repeated zeros in $\Z/q\Z$, so that $$ \{(x,y)\in(\Z/q\Z)^2:y^2=x^6+a\} $$ are the affine points of a genus $2$ curve. The curve has two points at infinity, so by the Weil bound, we have $$ 2+\sum_{x\in\Z/q\Z}\left(1+\left(\frac{x^6+a}{q}\right)\right) \le q+1+4\sqrt{q}, $$ whence $$ \sum_{x\in(\Z/q\Z)^\times}\left(\frac{x^6+a}{q}\right)\le 4\sqrt{q}-1-\left(\frac{a}{q}\right)\le 4\sqrt{q}. $$ This last estimate is less than $q-1$ provided that $q\ge 19$, and we check the claim for $q\in\{3,5,11,17\}$ directly. \end{proof} Theorem~\ref{t:main} follows by induction from the following proposition. \begin{proposition} Let $P$ be a finite set of prime numbers and $q$ the smallest prime not contained in $P$. Then there is a generalized Euclid sequence with seed $P$ that contains $q$. \end{proposition} \begin{proof} Suppose that $P=\{p_1,\ldots,p_k\}$, and put $n=p_1\cdots p_k$. If $q=2$ then $n+1$ is even, so we may choose $2$ as the next term, $p_{k+1}$. Hence we may assume that $q$ is odd. Put $$ S=\{d+q\Z:d\in\Z_{>0},\;d\mid n\}\subseteq(\Z/q\Z)^\times, $$ and note that $S\supseteq S_q$. Suppose first that $S=(\Z/q\Z)^\times$. If $\left(\frac{-n}{q}\right)=1$ then it follows that there is a $d\mid n$ such that $d+n/d\equiv0\pmod*{q}$, so we can choose $q$ as the next term. On the other hand, if $\left(\frac{-n}{q}\right)=-1$ then by Lemma~\ref{l:hyp}(i) we may choose $d\mid n$ such that $\left(\frac{d+n/d}{q}\right)=-1$, provided that $q\ne5$ or $n\not\equiv3\pmod*{5}$. For this choice of $d$ there must be a prime $p\mid(d+n/d)$ such that $\left(\frac{p}{q}\right)=-1$. Choosing this $p$ as the next term, we replace $n$ by $n'=pn$, so that $\left(\frac{-n'}{q}\right)=1$, and we may then follow this by $q$, as above. For $q=5$ and $n\equiv3\pmod*{5}$ we choose $d=1$; since $n+1\equiv-1\pmod*{5}$ there is a prime $p\mid(n+1)$ with $p\not\equiv1\pmod*{5}$, and replacing $n$ by $pn$ gives a different residue with which we can carry out the proof above. Now suppose that $S\ne(\Z/q\Z)^\times$. We seek to enlarge $S$ by continuing the sequence, i.e., we choose $p=p_{k+1}$ from $$ T=\{p:p\text{ prime and }p\mid(d+n/d)\text{ for some }d\mid n\}, $$ and replace $P$ by $P\cup\{p\}$, $n$ by $pn$ and $S$ by $S\cup pS$. We are free to repeat this procedure until either $q\in T$ (in which case we may choose $q$ as the next term) or $S$ stabilizes, so that $pS\subseteq S$ for every choice of $p\in T$. If that is the case then it is easy to see that for every $s\in S$, $S$ contains the coset $sG$, where $G\le(\Z/q\Z)^\times$ is the subgroup generated by $\{p+q\Z:p\in T\}$. Thus, $S=\bigcup_{s\in S}sG$ is a union of cosets; in particular, $\#G$ divides $\#S$. Next, let $H$ be a subgroup of $(\Z/q\Z)^\times$ of index at least $4$. For any $h\in H$, the number of $d\in(\Z/q\Z)^\times$ such that $d+n/d=h$ is at most $2$. Hence, $$ \#\{d\in(\Z/q\Z)^\times:d+n/d\in H\}\le 2\#H\le\tfrac12(q-1). $$ By Lemma~\ref{l:Sq}, it follows that there exists $d\mid n$ such that $(d+n/d)+q\Z\notin H$. In turn this implies that $p+q\Z\notin H$ for some $p\in T$. For any $r\mid(q-1)$, consider the subgroup $$ H_r=\bigl\{h\in(\Z/q\Z)^\times:h^{\frac{q-1}{r}}=1\bigr\} =\{x^r:x\in(\Z/q\Z)^\times\}, $$ which has index $r$ in $(\Z/q\Z)^\times$. Let $q-1=\prod_{i=1}^mr_i^{e_i}$ be the prime factorization of $q-1$. For each $r_i\ge5$ we apply the above argument with $$ H=H_{r_i}=\{h\in(\Z/q\Z)^\times: r_i^{e_i}\text{ does not divide the order of }h\} $$ to see that $G$ has order divisible by $r_i^{e_i}$. For $r_i\in\{2,3\}$ the index of $H_{r_i}$ is too small to apply the argument, but we may still apply it to $H_{r_i^2}$ (when $r_i^2\mid(q-1)$) to see that $G$ has order divisible by $r_i^{e_i-1}$. Thus we find that the index of $G$ in $(\Z/q\Z)^\times$ divides $6$. If $q\not\equiv1\pmod*{3}$ then $G$ has index at most $2$, so that $\frac12(q-1)\mid\#G\mid\#S$; by Lemma~\ref{l:Sq} it follows that $S=(\Z/q\Z)^\times$, as desired. If $q\equiv1\pmod*{3}$ then we apply the above argument with $H=H_6$ to see that there exists $p\in T$ such that $p^{\frac{q-1}{6}}\not\equiv1\pmod*{q}$. Since $p^{\frac{q-1}{6}}=p^{\frac{q-1}{2}}/p^{\frac{q-1}{3}}$, it follows that at least one of $H_2$ and $H_3$ does not contain $p+q\Z$. If $p+q\Z\notin H_3$ then again $G$ has index at most $2$, and we conclude that $S=(\Z/q\Z)^\times$ as above. Hence, we may assume that $p+q\Z\notin H_2$, so that $G$ has index dividing $3$. If $S=(\Z/q\Z)^\times$ then we are finished, so we may assume that $G=H_3$ and $\#S\#G$, and it follows that $\#S=2\#G=\frac23(q-1)$. Going through the argument above with $H=H_3$, since $d+n/d=h$ has at most two solutions for fixed $h$ and $\#S=2\#H_3$, to avoid concluding that there exists $p\in T$ such that $p+q\Z\notin H_3$, the function $d\mapsto d+n/d$ must map $S$ 2--1 onto $H_3$. By the quadratic formula, this means in particular that $\left(\frac{h^2-4n}{q}\right)=1$ for every $h\in H_3$, and thus $\left(\frac{x^6-4n}{q}\right)=1$ for every $x\in(\Z/q\Z)^\times$. However, that contradicts Lemma~\ref{l:hyp}(ii) for $q\notin\{7,13\}$, and for $q\in\{7,13\}$ we verify directly that $\#S_q>\frac23(q-1)$. This concludes the proof. \end{proof} \section{Acknowledgments} I thank Trevor Wooley and Carl Pomerance for supportive comments. \bibliographystyle{jis} \begin{thebibliography}{1} \bibitem{booker} Andrew~R. Booker, On {M}ullin's second sequence of primes, {\em Integers} {\bf 12} (2012), 1167--1177. \bibitem{bi} Andrew~R. Booker and Sean~A. Irvine, The {E}uclid-{M}ullin graph, {\em J. Number Theory} {\bf 165} (2016), 30--57. \bibitem{clark} Pete~L. Clark, On {E}uclid's proof of the infinitude of primes and generating primes, MathOverflow, \newblock \url{http://mathoverflow.net/q/4977}. \bibitem{cp} Richard Crandall and Carl Pomerance, {\em Prime Numbers: A Computational Perspective}, Springer, second edition, 2005. \bibitem{mullin} Albert~A. Mullin, Recursive function theory, {\em Bull. Amer. Math. Soc.} {\bf 69} (1963), 737. \bibitem{pt} Paul Pollack and Enrique Trevi{\~n}o, The primes that {E}uclid forgot, {\em Amer. Math. Monthly} {\bf 121} (2014), 433--437. \bibitem{rogers} Kenneth Rogers, The {S}chnirelmann density of the squarefree integers, {\em Proc. Amer. Math. Soc.} {\bf 15} (1964), 515--516. \bibitem{shanks} Daniel Shanks, Euclid's primes, {\em Bull. Inst. Combin. Appl.} {\bf 1} (1991), 33--36. \end{thebibliography} \bigskip \hrule \bigskip \noindent 2010 {\it Mathematics Subject Classification}: Primary 11A41; Secondary 11B83. \noindent \emph{Keywords: } prime number, Euclid-Mullin sequence. \bigskip \hrule \bigskip \noindent (Concerned with sequences \seqnum{A000945}, \seqnum{A000946}, and \seqnum{A167604}.) \bigskip \hrule \bigskip \vspace*{+.1in} \noindent Received May 26 2016; revised versions received June 16 2016; June 17 2016. Published in {\it Journal of Integer Sequences}, July 4 2016. \bigskip \hrule \bigskip \noindent Return to \htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}. \vskip .1in \end{document}