% ----------------------------------------------------------------
% AMS-LaTeX Paper: ***********************************************
%
%    Title:        Variations on a Theme of Sierpi\'{n}ski
%
%    Author:       Lenny Jones
%
%    Address:      Department of Mathematics
%                  Shippensburg University
%                  1871 Old Main Drive
%                  Shippensburg, PA 17257
%
%
%    Phone:        717-477-1793 (office)
%
%    Email:        lkjone@ship.edu
%
%    Written:      Spring 2006
%    Last revised: April 13, 2007
%
%    Submitted to: The Journal of Integer Sequences
%              on: November 6, 2006
%     Accepted by: The Journal of Integer Sequences
%              on: April 10, 2007
% ----------------------------------------------------------------
\documentclass[12pt,reqno]{article}

\usepackage[usenames]{color}

\usepackage{graphicx}
\usepackage{amscd}

\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}

\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}

\usepackage{color}
\usepackage{fullpage}
\usepackage{float}

\usepackage{psfig}
\usepackage{graphics,amsmath,amssymb}
\usepackage{amsfonts}
\usepackage{latexsym}
\usepackage{epsf}

\usepackage{amsthm}


\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.5in}
\setlength{\textheight}{8.9in}

\newcommand{\seqnum}[1]{\href{http://oeis.org/#1}{\underline{#1}}}

\begin{document}

\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}


\newtheorem{thm}{Theorem}[section]
\newtheorem{lem}[thm]{Lemma}
\newtheorem{conj}[thm]{Conjecture}
\newtheorem{prop}[thm]{Proposition}
\newtheorem{cor}[thm]{Corollary}
\newtheorem{sch}[thm]{Scholium}
\newtheorem{guess}[thm]{Guess}
\newtheorem{ex}[thm]{Example}
\theoremstyle{remark}
    \newtheorem*{rem}{{\bf Remark}}   %no numbering for remarks
    %\theoremstyle{remarks}
    \newtheorem*{rems}{{\bf Remarks}}

    \newtheorem*{note}{Note}
\theoremstyle{definition}
    \newtheorem{defn}[thm]{Definition}

  




\numberwithin{equation}{section}
\def\ds{\displaystyle}\def\C{{\mathcal C}}
\def\Z {{\mathbb Z}}
%\def\F {{\mathbb F}}
%\def\N{{\mathcal N}}
%\def\Q {{\mathbb Q}}
%\def\T {{\tilde T}}
%\def\D {{\mathcal D}}
%\def\N {{\mathcal N}}
%\def\M {{\mathcal M}}
%\def\H {{\mathcal H}}
%\def\h {{\mathfrak h}}
%\def\l {\left\langle}
%\def\r {\right\rangle}
%\def\bip{{\mathrm{Bip}}}
\def\K{{\mathcal K}}
%\def\k{{\mathbf k}}
%\def\n{{\mathbf n}}

\begin{center}
\vskip 1cm{\LARGE\bf {Variations on a Theme of Sierpi\'{n}ski}}
\vskip 1cm
\large
Lenny Jones \\
Department of Mathematics \\
Shippensburg University \\
Shippensburg, Pennsylvania 17257 \\
USA\\
\href{mailto:lkjone@ship.edu}{\tt lkjone@ship.edu}\\ 
\ \\
\end{center}

\vskip .2 in

\begin{abstract}
Using an idea of Erd\H{o}s, Sierpi\'{n}ski proved that there exist
infinitely many odd positive integers $k$ such that $k\cdot 2^n+1$
is composite for all positive integers $n$. In this paper we give a
brief discussion of Sierpi\'{n}ski's theorem and some variations
that have been examined, including the work of Riesel, Brier, Chen,
and most recently, Filaseta, Finch and Kozek. The majority of the
paper is devoted to the presentation of some new results concerning
our own variations of Sierpi\'{n}ski's original theorem.
\end{abstract}

\vskip .2in

\renewcommand{\theequation}{\arabic{equation}}

\renewcommand{\theequation}{\arabic{equation}}




\section{Introduction}\label{Intro}

In 1960, using an idea of Erd\H{o}s, Sierpi\'{n}ski \cite{Sier}
proved that there exist infinitely many odd positive integers $k$
such that $k\cdot 2^n+1$ is composite for all positive integers $n$.
Such values of $k$ are called Sierpi\'{n}ski numbers.
%A by-product of Sierpi\'{n}ski's proof is that his
% infinite set of values of $k$ forms an arithmetic progression and consequently, has positive density.
 The smallest such integer produced by Sierpi\'{n}ski's method is $k=15511380746462593381$.
 In 1962, however, John Selfridge proved that the value $k=78557$ has the property that $k\cdot 2^n+1$ is composite for all positive integers $n$. The problem of determining the smallest such value of $k$ is known as {\it Sierpi\'{n}ski's Problem}. %While it is commonly believed that this value of $k$
Selfridge conjectured that $k=78557$ is indeed the smallest such
value of $k$. To establish this claim, one needs to show that for
each positive integer $k<78557$, there exists a positive integer $n$
such that $k\cdot 2^n+1$ is prime. Currently, there remain only
eight unresolved cases: $k=10223$, 19249, 21181, 22699, 24737,
33661, 55459, and 67607. For the most recent progress on this problem, we refer the interested reader to the distributed computing project known as {\it Seventeen or Bust}, which can be found at the
website www.seventeenorbust.com. The name of this project indicates
that when it was started, only 17 values of k were unresolved.

In 1956, four years prior to Sierpi\'{n}ski's original paper, Riesel
\cite{R} proved that there are infinitely many odd positive integers
$k$ such that $k\cdot 2^n-1$ is composite for all positive integers
$n$. Such values of $k$ are called Riesel numbers, and the problem
of finding the smallest Riesel number is known as {\it Riesel's Problem}.
To date, the smallest known Riesel number is $k=509203$. 
%Because Riesel's result predates Sierpi\'{n}ski's, perhaps the title of this
%paper should be: {\it Variations on a Theme of Riesel}. 
%Curiously though, 
Although Riesel and Sierpi\'{n}ski used the same methods, and Riesel's result predates Sierpi\'{n}ski's, it is curious that the result of Riesel did not originally garner as much focus as
Sierpi\'{n}ski's theorem. This is conceivably due, in part, to the
fact that Selfridge popularized Sierpi\'{n}ski's problem by
taking an active role in its solution. A related problem, due to
Brier, is to determine the smallest odd positive integer $k$ such
that both $k\cdot 2^n+1$ and $k\cdot 2^n-1$ are composite for all
positive integers $n$. Currently, the smallest known Brier
number is %$k=878503122374924101526292469$, 
$k=143665583045350793098657$, which was found recently by Filaseta, Finch and
Kozek \cite{FFK}. %by Gallot in 2002. 
Both the problems of Riesel and Brier now have dedicated
enthusiasts in pursuit of their solutions. More recently, some
modifications of the theorems of Sierpi\'{n}ski and Riesel have been
investigated by Chen \cite{C1,C2,C3,C4}, and Filaseta, Finch and
Kozek \cite{FFK}. These recent results also show that the set of all
values of $k$ for which each term of the sequence contains at least
$m$ distinct prime divisors, for certain fixed integers $m\ge 2$,
contains an infinite arithmetic progression or contains a subset that can be obtained from an infinite arithmetic progression.

The main purpose of this paper is to present some results concerning
new variations of Sierpi\'{n}ski's theorem. In particular, our main result, Theorem
\ref{Jmaxshort1}, provides a true generalization of Sierpi\'{n}ski's
original theorem. A by-product of the proof is that the sets of
values of $k$ that are produced all contain an infinite arithmetic
progression. We are not concerned here in any case with determining the smallest such value of $k$, although in certain situations this can be done quite easily.  
\section{Definitions and Preliminaries}
In this section we present some definitions and results which are used in the sequel.
\begin{defn}
  For any sequence $\left\{s_n \right\}_{n=1}^{\infty}$ of positive integers, we call a prime divisor $q$ of the term $s_n$ a {\it primitive prime divisor} of $s_n$, if $q$ does not divide $s_m$ for any $m<n$.
\end{defn}

\begin{rem}
  A term $s_n$ can have more than one primitive prime divisor, or none at all. See Theorem \ref{Bang} and Theorem \ref{Sch1}.
\end{rem}

The following result is originally due to Bang \cite{Bang}.
\begin{thm}\label{Bang}
Let $a$ and $n$ be positive integers with $a\ge 2$. Then $a^n-1$ has a primitive prime divisor with the following exceptions:\begin{itemize}
\item $a=2$ and $n=6$
\item $a+1$ is a power of $2$ and $n=2$.
\end{itemize}
\end{thm}
Many other proofs of Theorem \ref{Bang} and its generalizations have been published. Two of the most well-known papers are due to Zsigmondy \cite{Z}, and Birkhoff and Vandiver \cite{BV}. More recently, along these lines, Bilu, Hanrot and Voutier \cite{BHV} have settled completely the question of primitive prime divisors in Lucas and Lehmer sequences by showing that, for all $n>30$, the $n$--th term of any Lucas or Lehmer sequence has a primitive prime divisor.

% In 2004, Mih\u{a}ilescu \cite{M} proved the following result, which was conjectured in 1844 by Catalan, and which has been commonly referred to in the literature as {\it Catalan's Conjecture}.
%\begin{thm}\label{Mih}
% The only nontrivial solution to the Diophantine equation $x^y-z^w=1$ is $x=3$, $y=2$, $z=2$ and $w=3$.
%\end{thm}

The following concept is due to Erd\H{o}s.
\begin{defn}
A {\it finite covering} is a finite system of congruences $x\equiv
a_i \pmod{m_i}$, with $1\le i \le t$, such that every integer
satisfies at least one of the congruences.
\end{defn}
Note that we simply use the word ``covering" here to indicate a
finite covering, since we are not concerned with infinite coverings.
An example of a covering in which the modulii are not distinct is
given below.
\begin{ex}\text{}
  \begin{center}
    $\begin{array}{cccc}
      x&\equiv & 0 &\pmod{2}\\
      x&\equiv & 1 &\pmod{4}\\
      x&\equiv & 3 &\pmod{4}\\
    \end{array}$\\
  \end{center}

%  {\rm We can also represent this covering in the following way:}\\

%  \begin{center}
%$\begin{array}{ccccc}
%  a_i & & 0 & 1 & 3\\
%  m_i & & 2 & 4 & 4
%  \end{array}$
%  \end{center}
\end{ex}
%We occasionally use the second representation for space-saving reasons.

The following example is a covering with distinct modulii.

\begin{ex}\text{}
\begin{center}
$\begin{array}{cccc}
x& \equiv &0 &\pmod{2}\\
x& \equiv &0 &\pmod{3}\\
x& \equiv &0 &\pmod{5}\\
x& \equiv &1 &\pmod{6}\\
x& \equiv &0 &\pmod{7}\\
x& \equiv &1 &\pmod{10}\\
x& \equiv &1 &\pmod{14}\\
x& \equiv &2 &\pmod{15}\\
x& \equiv &2 &\pmod{21}\\
x& \equiv &23 &\pmod{30}\\
x& \equiv &4 &\pmod{35}\\
x& \equiv &5 &\pmod{42}\\
x& \equiv &59 &\pmod{70}\\
x& \equiv &104 &\pmod{105}\\
\end{array}$
\end{center}
%\begin{center}
%$\begin{array}{cccccccccccccccc}
%  a_i & & 0 & 0 & 0 & 1 & 0 & 1 & 1 & 2 & 2 & 23 & 4 & 5 & 59 & 104\\
%  m_i & & 2 & 3 & 5 & 6 & 7 & 10 & 14 & 15 & 21 & 30 & 35 & 42 & 70 & 105
%  \end{array}$
%  \end{center}
\end{ex}

There are still many unsolved problems regarding coverings. Two of the most famous open questions are the following: \cite{Guy}
\begin{enumerate}
  \item Does there exist a covering in which all moduli are odd, distinct and greater than one?
\item Can the minimum modulus in a covering with distinct moduli be arbitrarily large?\label{Erd}
\end{enumerate} Question \ref{Erd}. was first posed by Erd\H{o}s \cite{E}, and he offers posthumously \$1000 for a solution.


\section{Sierpi\'{n}ski's Theorem}
To illustrate a basic technique used in this paper, we present a
proof of the original theorem of Sierpi\'{n}ski \cite{Sier} from
1960, stated below as Theorem \ref{Sierpinski}.
\begin{thm}\label{Sierpinski}
There exist infinitely many odd positive integers $k$ such that
$k\cdot 2^n+1$ is composite for all positive integers $n$.
\end{thm}
\begin{proof}
Consider the following covering $n\equiv a_i \pmod{m_i}$:
%\begin{center}
%$\begin{array}{cccc}
%n & \equiv & 1 & \pmod{2}\\  n & \equiv & 2 & \pmod{4}\\ n & \equiv & 4 & \pmod{8}\\ n & \equiv & 8 & \pmod{16}\\ n & \equiv & 16 & \pmod{32}\\ n & \equiv & 32 & \pmod{64}\\ n & \equiv & 0 & \pmod{64}\\
%\end{array}$
%\end{center}
\begin{center}
$\begin{array}{ccccccccc}
  i & & 1&2&3&4&5&6&7\\ \hline
  a_i & & 1 & 2 & 4 & 8 & 16 & 32 & 0\\
 m_i & & 2 & 4 & 8 & 16 & 32 & 64 & 64.
  \end{array}$
 \end{center}
For each $i$, when $n\equiv a_i \pmod{m_i}$ and $k\equiv b_i
\pmod{p_i}$ (from below),
\begin{center}$\begin{array}{ccccccccc}
i & & 1&2&3&4&5&6&7\\ \hline
  b_i & & 1 & 1 & 1 & 1 & 1 & 1 & -1\\
  p_i & & 3 & 5 & 17 & 257 & 65537 & 641 & 6700417,
  \end{array}$
  \end{center}
  it is easy to check that $k\cdot 2^n+1$ is divisible by $p_i$. Now, apply the Chinese Remainder Theorem
  to the system $k\equiv b_i \pmod{p_i}$.
   Then, for any such solution $k$, each $k\cdot 2^n+1$ is divisible by at least one prime from the set $\C=\left\{ 3,5,17,257,641,65537,6700417 \right\}$.
\end{proof}

\begin{rems}\text{}
  \begin{itemize}
  \item The set $\C$ in the proof of Theorem \ref{Sierpinski} is called a {\it covering set}
   associated with the covering.
   \item Observe that a consequence of the method of proof of Theorem
   \ref{Sierpinski} is that the set of all odd positive integers $k$ such that $k\cdot 2^n+1$ is composite for all positive integers $n$ contains an infinite arithmetic progression.
   \end{itemize}
\end{rems}

While the proof of Theorem \ref{Sierpinski} is straightforward, the choice of the covering is the crucial and delicate step. What makes this particular covering useful is the fact that the Fermat number $2^{2^5}+1$ has two distinct prime divisors. A priori, it is conceivable that there are other coverings that could be used to prove Theorem \ref{Sierpinski}. In fact, Selfridge produced the smaller value $k=78557$ by using the covering:
\begin{center}
$\begin{array}{cccc}
n & \equiv & 0 & \pmod{2}\\  n & \equiv & 1 & \pmod{4}\\ n & \equiv & 3 & \pmod{36}\\ n & \equiv & 15 & \pmod{36}\\ n & \equiv & 27 & \pmod{36}\\ n & \equiv & 7 & \pmod{12}\\ n & \equiv & 11 & \pmod{12}\\
\end{array}$
\end{center}

%\begin{center}
%$\begin{array}{ccccccccc}
%  a_i & & 0 & 1 & 3 & 15 & 27 & 7 & 11\\
% m_i & & 2 & 4 & 36 & 36 & 36 & 12 & 12.
%  \end{array}$
% \end{center}
and associated covering set $\left\{3,5,7,13,19,37,73\right\}.$



The following questions come to mind upon examining the proof of Theorem \ref{Sierpinski}.
\begin{itemize}
\item {\it From among the coverings that can be used to prove Theorem \ref{Sierpinski}, which covering produces the smallest value of $k$?}\\
As mentioned in Section \ref{Intro}, Selfridge conjectured that $k=78557$ is the smallest value of $k$ such that $k\cdot 2^n+1$ is composite for all positive integers $n$. This problem is still unsolved.
\item {\it Is it possible to prove Theorem \ref{Sierpinski}, and perhaps produce a value of $k$ smaller than $k=78557$, using a method that does not involve a covering set?}\\
For example, in Section \ref{Jsection}, a covering set is not needed to prove Theorem \ref{J1}.
\item {\it Are there Sierpi\'{n}ski-like problems that cannot be solved using coverings?}\\
Erd\H{o}s \cite{Guy} conjectured that all sequences of the form $d\cdot2^n+1$, with $d$ fixed and odd, that contain no primes, can be obtained from coverings. There is evidence \cite{I}, however, to suggest that this conjecture might not be true.
\end{itemize}
\section{Variations of Sierpi\'{n}ski's Theorem}
\subsection{Some Recent Variations}

Certain variations of Theorem \ref{Sierpinski} have been concerned
with the number of distinct prime divisors that can occur in the
factorization of $k\cdot 2^n+1$. In particular, if $m\ge 2$ is some
fixed integer, does there exist a set of odd positive integers $k$
that contains an infinite arithmetic progression such that, for each
$k$, the integer $k\cdot 2^n+1$ has at least $m$ distinct prime
divisors for all positive integers $n$? In 2001, Chen \cite{C3}
answered this question in the affirmative for $m=3$.

Chen \cite{C4} also proved the following theorem in 2003.
\begin{thm}\label{Chen}
Let $r$ be a positive integer with $r\not \equiv 0, 4, 6, 8
\pmod{12}$. Then the set of odd positive integers $k$ such that
$k^r2^n+1$ has at least two distinct prime divisors for all positive
integers $n$ contains an infinite arithmetic progression.
\end{thm}

Because of the presence of the exponent $r$, we can think of Theorem
\ref{Chen} as a nonlinear variation of Sierpi\'{n}ski's original
theorem. Nevertheless, coverings still play a crucial role in the
proof, although other techniques are also employed by Chen.
Recently, the restrictions on $r$ in Theorem \ref{Chen} have been
overcome by Filaseta, Finch and Kozek \cite{FFK}. Again, while
coverings are used in their proof, additional methods are utilized.
Chen's paper \cite{C4} also contains an analogous result for
integers of the form $k^r-2^n$ with the same restrictions on $r$. In
this situation however, the recent work of Filaseta, Finch and Kozek
\cite{FFK} disposes of only the cases when $r=4$ or $r=6$.
%They have also proven a similar, but weaker, Riesel-type result.
%These results are given below as Theorem \ref{FFK1} and Theorem
%\ref{FFK2}.
%\begin{thm}\label{FFK1} Given any positive integer $r$, there exist infinitely many odd positive integers $k$ such that $k^{r}2^n+1$ has at least two distinct prime divisors for all positive integers $n$.
%\end{thm}

%\begin{thm}\label{FFK2} If $r=4$ or $r=6$, there exist infinitely many odd positive integers $k$ such that $k^{r}2^n-1$ has at least two distinct prime divisors for all positive integers $n$.
%\end{thm}

%Coverings are used in the proofs of Theorems \ref{Chen}, \ref{FFK1} and \ref{FFK2}, but additional machinery is needed as well.


\subsection{Some New Variations}\label{Jsection}

We first present a theorem that deviates somewhat from previous
investigations in the sense that here the ``multiplier" $k$ is
fixed. The proof uses a covering and an algebraic factorization,
rather than an associated covering set. A similar approach was
employed by Izotov \cite{I} to give a different proof of Theorem
\ref{Sierpinski}.


\begin{thm} \label{J1}
Let $k\ge 2$ be a fixed integer and let $f(x)\in \Z[x]$ be a
polynomial with positive leading coefficient such that $f(-1)\ge 2$.
Then the set of all positive integers $b$ such that $k f(b) b^n+1$
is composite for all positive integers $n$ contains an infinite
arithmetic progression.
\end{thm}

\begin{proof}
For any positive integer $c$, let $b=c(k^2f(-1)^2-1)-1$. Then, when $n$ is odd, we have
\[k f(b)  b^n+1 \equiv k f(-1) (-1)^n+1\equiv 0 \pmod{kf(-1)-1};\]
and when $n$ is even, we have
\[k f(b)  b^n+1 \equiv k f(-1) (-1)^n+1\equiv 0 \pmod{kf(-1)+1}.\]
Since $f(x)$ has a positive leading coefficient, there exists $N$ such that $kf(b)b+1>kf(-1)+1$ for all $c>N$, eliminating the possibility that $kf(b)b^n+1$ is prime for any positive integer $n$.
\end{proof}

The following corollary is immediate from Dirichlet's theorem on
primes in an arithmetic progression.
\begin{cor}
  Assume the hypotheses of Theorem \ref{J1}. Then there exist infinitely many prime numbers $p$ such that $k f(p) p^n+1$
is composite for all positive integers $n$.
\end{cor}

If certain further restrictions are imposed on the polynomial $f(x)$
in Theorem \ref{J1}, a lower bound can be placed on the number of
prime divisors of each term in the sequence of Theorem \ref{J1}.
More precisely, we have the following:
\begin{thm}\label{J1A}
In addition to the hypotheses of Theorem \ref{J1}, let $m\ge 2$ be a
fixed integer and let $z$ be an odd positive integer such that the
number of divisors of $z$ is $m+1$. If $f(-1)=k^{z-1}$, then the set
of all positive integers $b$ such that $k f(b) b^n+1$ has at least
$m$ distinct prime divisors for all positive integers $n$ contains
an infinite arithmetic progression.
\end{thm}

\begin{proof}
 Since $m\ge 2$, we have that $z>2$. Then, by Theorem \ref{Bang}, $kf(-1)-1=k^z-1$ has at least
  $m$ distinct prime divisors. Thus, when $n$ is odd, $k f(b) b^n+1$ has at least $m$ distinct prime
   divisors since, from the proof of Theorem \ref{J1}, we have that $kf(-1)-1$ divides $k f(b) b^n+1$.
    Also, by Theorem \ref{Bang}, $k^{2z}-1$ has at least $m$ distinct prime divisors.
    Consequently, $kf(-1)+1=k^z+1$ has at least $m$ distinct prime divisors. Therefore, when $n$ is even,
    $k f(b) b^n+1$ has at least $m$ distinct prime divisors since, from the proof of Theorem \ref{J1},
    we have that $kf(-1)+1$ divides $k f(b) b^n+1$.
\end{proof}

As before, we have the following corollary immediately from
Dirichlet's theorem.
\begin{cor}
  Assume the hypotheses of Theorem \ref{J1A}. Then there exist infinitely many prime numbers $p$ such that $k f(p) p^n+1$
has at least $m$ distinct prime divisors for all positive integers
$n$.
\end{cor}

While Theorem \ref{J1} is interesting, it does not generalize Theorem \ref{Sierpinski}. The following conjecture, however, is a natural generalization of Theorem \ref{Sierpinski}.

\begin{conj}\label{Conjecture}%{\rm \blue {\bf (J--2006)} }\label{Conjecture}
Let $a,m\ge 2$ be fixed integers. For any positive integer $n$,
define \[b_n:=a^{(m-1)n}+a^{(m-2)n}+\cdots +a^{n}.\] Then the set of
all positive integers $k$ such that $kb_n+1$ is composite for all
positive integers $n$ contains an infinite arithmetic progression.
\end{conj}

\begin{rem}
  Note that $a=m=2$ in Conjecture \ref{Conjecture} is Sierpi\'{n}ski's original result, Theorem \ref{Sierpinski}.
\end{rem}

It was our hope to find a proof of Conjecture \ref{Conjecture}. Unfortunately, known general techniques seem to fall
 short of achieving this goal. In particular, the major stumbling block seems to be that little is known concerning the number of primitive prime divisors in sequences whose terms are of the form $a^m-1$. Despite this lack of additional insight, we are able to prove Conjecture \ref{Conjecture} in many situations (see Theorem \ref{Jmax}).

We digress now for a brief discussion about the number of primitive prime divisors in sequences whose terms are of the form $a^m-1$, by first stating Conjecture \ref{C1}, whose truth is adequate to supply a proof of Conjecture \ref{Conjecture}, which is given at the end of this section.

\begin{conj}\label{C1}
  Let $a\ge 2$ be an integer and let $p$ be a prime. Then there exists a positive integer $t$ such that $a^{p^t}-1$ has at least two distinct primitive prime divisors. Equivalently, there exists a positive integer $z$ such that $\left(a^{p^z}-1\right)/\left(a-1\right)$ has at least $z+1$ distinct prime divisors.
\end{conj}

The best known result in the direction of Conjecture \ref{C1} is given below as Theorem \ref{Sch1}, which is a special case of a theorem of Schinzel \cite{S}. We need the following definition.

\begin{defn}\label{kernel}
  For any integer $a$, we define the {\it square-free kernel} of $a$, denoted $\K(a)$, to be $a$ divided by its largest square factor.
\end{defn}


\begin{thm}\label{Sch1}
  Let $a\ge 2$ and $m\ge 3$ be integers. Let $e=1$ if $\K(a)\equiv 1 \pmod{4}$, and let $e=2$ if $\K(a)\equiv 2,3 \pmod{4}$. If $m/\left(e\K(a)\right)$ is an odd integer, then $a^m-1$ has at least two distinct primitive prime divisors, with the following exceptions:
\begin{center}
$\begin{array}{cl}
a=2, & m\in\left\{4,12,20\right\}\\
a=3, & m=6\\
%a=3, & b=2, & m=12\\
a=4, & m=3.\\
%a=4, & b=3, & m=6.\\
\end{array}$
\end{center}
\end{thm}



The following conjecture is related to Conjecture \ref{C1}.

\begin{conj}\label{C2}
Let $a\ge 2$ be a positive integer and let $p$ be a prime. Let $\Phi_{p}(x)$ denote the $p$--th cyclotomic polynomial. Then there exists a positive integer $t$ such that $\Phi_{p}(a^{p^{t-1}})$ has at least two distinct prime divisors.
\end{conj}



%$\begin{array}{rl}
%a^{p^t}-1&=\left(a^{p^{t-1}}-1\right)\Phi_p\left(a^{p^{t-1}}\right)\\
%&=\left(a^{p^{t-2}}-1\right)\Phi_p\left(a^{p^{t-2}}\right)\Phi_p\left(a^{p^{t-1}}\right)\\
%&=(a-1)\Phi_p(a)\Phi_p\left(a^p\right)\cdots \Phi_p\left(a^{p^{t-1}}\right),
%\end{array}$

%\noindent
Since $a^{p^t}-1=\left(a^{p^{t-1}}-1\right)\Phi_p\left(a^{p^{t-1}}\right)$,
it follows from Theorem \ref{Bang} that, when $a\not \equiv 1 \pmod{p}$, Conjecture \ref{C2} is equivalent to Conjecture \ref{C1}.
Along these lines, for $p\ne 3$, a result of Schinzel and Tijdeman  \cite{ST} implies that there are at most finitely many triples $(x,y,m)$ of integers, with $x\ge 1$ and $y,m\ge 2$, such that $\Phi_{p}(x)=y^m$. Consequently, if Conjecture \ref{C2} is not true, then $\Phi_{p}(a^{p^{t-1}})$ is prime for all sufficiently large $t$, which seems quite implausible.
Computer evidence suggests that, most likely, the following somewhat stronger statement is true.
%Perhaps  like the following stronger conjecture, which has been verified up to a modest $p=229$, is true.

\begin{conj}\label{C3}
Let $a\ge 2$ be a positive integer. Then $\Phi_{p}(a^{p^2})$ has at least two distinct prime divisors for all sufficiently large primes $p$.
%Let $p\ge 61$ be prime. Then $\Phi_{p}(2^{p^2})$ has at least two distinct prime divisors.
\end{conj}

We turn now to our main result stated below as Theorem \ref{Jmaxshort1}. %For the remainder of the paper, we let $\T$ denote the set $\left\{1,2,2^2,2^3,\cdots \right\}$.

%{\rm \blue {\bf (J--2006)} }
\begin{thm}\label{Jmaxshort1}
Let $a,m\ge 2$ be fixed integers. For any positive integer $n$,
define \[b_n:=a^{(m-1)n}+a^{(m-2)n}+\cdots +a^{n}.\] Then the set of
all positive integers $k$ such that $kb_n+1$ is composite for all
positive integers $n$ contains an infinite arithmetic progression,
with the possible exception of the situation when $m$ and $a$
satisfy the following conditions:
\begin{itemize}
\item $m$ is a prime such that $m\equiv 1\pmod{12}$ and $m\equiv 1
\pmod{q}$ for all prime divisors $q$ of $a-1$,
\item $a$ is not of the form $c^2$ or $mc^2$ for some integer $c\ge 2$.
\end{itemize}
\end{thm}


%\begin{thm}{\rm \blue {\bf (J--2006)} }\label{Jmaxshort}
%Let $a,m\ge 2$ be fixed integers. For any positive integer $n$, define %\[b_n:=a^{(m-1)n}+a^{(m-2)n}+\cdots +a^{n}.\]
%Then there exist infinitely many positive integers $k$ such that $kb_n+1$ is composite %for all positive integers $n$, with the possible exception of the situation when $a=2$ %and $m$ is an odd prime with $m\equiv 1\pmod{12}$.
%\end{thm}

We restate Theorem \ref{Jmaxshort1} in a less succinct manner since
the proof is organized according to the cases indicated in the
restatement. \addtocounter{thm}{-1}
\begin{thm} {\rm ({\bf Restated})}\label{Jmax}%{\rm \blue {\bf (J--2006)} }\label{Jmax}
Let $a,m\ge 2$ be fixed integers. For any positive integer $n$,
define \[b_n:=a^{(m-1)n}+a^{(m-2)n}+\cdots +a^{n}.\] Then, in each
of the following cases, the set of all positive integers $k$ such
that $kb_n+1$ is composite for all positive integers $n$ contains an
infinite arithmetic progression:
\begin{enumerate}
\item There is a prime $q$ that divides $a-1$ but does not divide $m-1$\label{easycase1}
 \item $m$ is composite \label{composite} %\label{1}
 % \item $m=a=2$ (Sierpi\'{n}ski) \label{Sierp} %\label{2A}
 % \item $m=2$ and $a=c^2$ for some integer $c\ge 2$ \label{aissquare}%\label{4}
 % \item $m=2$ and $a=c^d$ for some integer $c\ge 2$, with $d\not \in \T$ \label{aisctod}%\label{2}
\item $m=2$ \label{easycase2andSier}%{\rm \hspace*{.11in}($a=2$ is Sierpi\'{n}ski)}\label{easycase2andSier}
%\item $m$ is an odd prime and $a\ge 3$ \label{misoddprimeandage3}
  \item $m$ is an odd prime with $m\not \equiv 1 \pmod{12}$ \label{misoddprime}%\label{3}
\item $m/\left(e\K(a)\right)$ is an odd integer, where $\K(a)$, $e$, $m$ and $a$ are as given in Definition \ref{kernel} and Theorem \ref{Sch1}.\label{Schinz}%\label{5}
%$m$ and $a$ satisfy the hypotheses of Theorem \ref{Sch1}, other than the exceptions stated there.\label{5}
\end{enumerate}
\end{thm}

The approach we use to prove Theorem \ref{Jmax} is, for the most part, a straightforward modification of Sierpi\'{n}ski's original method. For each case, we start by choosing a covering. We choose a corresponding covering set of primes to impose various congruence conditions on $k$ to guarantee the proper divisibility of each of the terms $kb_n+1$ by some prime in the covering set. Then we apply the Chinese Remainder Theorem to the set of congruence conditions on $k$ to find the values of $k$ that satisfy all conditions simultaneously. The tricky steps, as always in this process, are choosing the appropriate covering and corresponding covering set. While the techniques used in the proof of each case are similar, we provide most of the details in each situation.
%There is, at times, a need to invoke Theorem \ref{Sch1} to obtain the covering set of primes.
We point out that no attempt is made, at this time, to choose the covering or the covering set in any optimal manner. As previously mentioned, Sierpi\'{n}ski's original theorem is the special case of $a=m=2$ in Theorem \ref{Jmax}.

 Note that the parts in Theorem \ref{Jmax}, as they are presented in the restated version, are not mutually exclusive.
  For example, part (\ref{easycase2andSier}) is just a combination of a special case of part (\ref{easycase1})
   and Theorem \ref{Sierpinski}. We list this $m=2$ case separately in the attempt to categorize the cases
   according to whether $m$ is prime or not. Although there is some overlap among the parts in Theorem \ref{Jmax}, no part is a subset of any other. For example, the case $a=6$, $m=13$ is handled in part (\ref{easycase1}) and no other, while the case $a=4$, $m=13$ is addressed in part (\ref{Schinz}) and no other. Note also that, if $a$ is odd and $m$ is even in Theorem \ref{Jmax},
   then $kb_n+1$ is even for any odd positive integer $k$, and the theorem is trivially true.
%Other situations arise in Theorem \ref{Jmax} which could be labelled as trivial. For example, if there exists a prime $q$ that divides $a-1$ but does not divide $m-1$, then, for any $k\equiv -1/(m-1) \pmod{q}$, it is easy to see that $kb_n+1 \equiv 0 \pmod{q}$ for all $n$.
%This reason contributes to the fact that the cases where $a=2$ are nontrivial.
Since most of the arguments given in the proof of Theorem \ref{Jmax} are general enough,
it is often not necessary to distinguish the trivial situations from the nontrivial situations.
The drawback to this more general approach, however, is that sometimes in the trivial situations
we are providing an unnecessarily complicated or inefficient proof. Nevertheless, we have chosen
the more general path rather than deciding in every case which situations qualify as truly trivial.

We need the following lemma for the proof of Theorem \ref{Jmax}.

\begin{lem}\label{specialq}
Let $a\ge 2$ be an integer, and let $m\ge 6$ be a composite integer. Then there exists a prime $q$ such that all of the following hold:
\begin{itemize}
  \item $q$ divides $a^m-1$
  \item $q$ is not a primitive divisor of $a^m-1$
  \item $q$ does not divide $m-1$.
\end{itemize}
\end{lem}

 \begin{proof}
First suppose that $m$ is not the square of a prime. Write $m=xy$
with $1<x<y<m$ and $y\ne 6$. Note that $y>2$, so that $a^y-1$ has a
primitive prime divisor $q$. Then $q$ divides $a^m-1$ but is not a
primitive prime divisor of $a^m-1$. Since $q$ is a primitive prime
divisor of $a^y-1$, we have that $q-1=zy=zm/x$ for some positive
integer $z$. If $q$ divides $m-1$, then $m-1=wq$ for some positive
integer $w$. Combining these facts gives
\begin{equation}\label{Eq1}
  m-1=w\left( \frac{zm}{x}+1 \right),
\end{equation} which implies that $w<x$, or equivalently $w+1<x+1$. Rearranging (\ref{Eq1}) yields \[y(x-wz)=\frac{m}{x}\left( x-wz\right) =w+1, \] so that $y\le w+1$. Therefore, it follows that $y<x+1$, contradicting the fact that $x<y$.

Now suppose that $m=p^2$ for some prime $p\ge 3$. Let $q$ be a
primitive prime divisor of $a^p-1$. Then $q$ divides $a^{p^2}-1$ but
is not a primitive prime divisor of $a^{p^2}-1$. Suppose that $q$
divides $p^2-1$. Since $q$ is a primitive prime divisor of $a^p-1$,
we have that $p$ divides $q-1$, and so $p<q$. Then, since $q$
divides $p^2-1=(p-1)(p+1)$, it follows that $q=p+1$, which is
impossible since $p\ge 3$.
 \end{proof}


%Suppose also that $a+1\not \in \left\{2,2^2,2^3,2^4,\ldots \right\}$ if $m=1$.



\begin{proof}[Proof of Theorem \ref{Jmax}]
The proof of part (\ref{easycase1}) is trivial since, if there exists a prime $q$ that divides $a-1$ but does not divide $m-1$, then, for any $k\equiv -1/(m-1) \pmod{q}$, we have that $kb_n+1\equiv 0 \pmod{q}$ for all $n$. Also, note that
\[kb_n+1=k(a^{(m-1)n}+\cdots +a^n)+1\ge ka^n+1\ge a+1>q,\]
so that no term $kb_n+1$ is actually equal to the prime $q$.

To prove part (\ref{composite}), consider first the case when $m\ge 6$, and write $m=xy$ with $1<x<y<m$ and $y\ne 6$. For now, we exclude the particular case of $a=2$ and $m=6$. Let $q$ be a primitive prime divisor of $a^y-1$, which exists since $y>2$ and $y\ne 6$. Let $r$ be a primitive prime divisor of $a^m-1$, which exists since $m>2$ and $a\ne 2$ when $m=6$. We use the covering $n\equiv 0,1,2, \ldots ,m-1 \pmod{m}$. When $n\equiv 1,2,\ldots ,m-1 \pmod{m}$, we have that $a^n-1\not \equiv 0 \pmod{r}$, since $r$ is a primitive prime divisor of $a^m-1$. Consequently,\\
\begin{align*}
  b_n+1 &=\frac{\left(a^n\right)^m-1}{a^n-1}\\
  &=\frac{\left(a^m\right)^n-1}{a^n-1}\\
  &=\frac{\left(a^m-1\right) \left(\left(a^m\right)^{n-1}+\cdots +1\right)}{a^n-1}\\
  &\equiv 0 \pmod{r}.\\
\end{align*} Therefore, if $k\equiv 1 \pmod{r}$, it follows that $kb_n+1\equiv 0 \pmod{r}$. Also, since %\frac{a^m-1}{a-1}
\[b_1+1=\frac{a^{xy}-1}{a-1}=\frac{\left( a^y-1\right)\left(a^{y(x-1)}+\cdots+1\right)}{a-1}\equiv 0 \pmod{q},\]
we see that \[kb_n+1\ge b_n+1 \ge b_1+1\ge qr>r,\] and so $kb_n+1$
is never equal to the prime $r$. When $n\equiv 0 \pmod{m}$, we have
that $b_n\equiv m-1 \pmod{q}$. From the proof of Lemma
\ref{specialq}, $m-1 \not \equiv 0 \pmod{q}$. Hence, $kb_n+1\equiv 0
\pmod{q}$ if $k\equiv -1/(m-1) \pmod{q}$. Also, since $b_n>a^y-1\ge
q$, the term $kb_n+1$ is never equal to the prime $q$. Now apply the
Chinese Remainder Theorem to the system of congruences
\begin{center}
$\begin{array}{cccc}
k & \equiv & 1 & \pmod{r}\\  k & \equiv & -1/(m-1) & \pmod{q}\\
\end{array}$
\end{center}to finish the proof of the theorem for composite $m\ge 6$, with the exception of the case $a=2$ and $m=6$.
 For this particular case,
 we have that $b_n+1=2^{6n}-1 \equiv 0 \pmod{3}$ and $b_n>3$ for all $n$.
 Hence, if $k\equiv 1 \pmod{3}$, then $kb_n+1\equiv 0 \pmod{3}$, and is never equal to 3, for all $n$.

Suppose now that $m=4$. As mentioned in the discussion prior to Lemma \ref{specialq}, the theorem
 is trivially true if $a$ is odd, so we assume that $a$ is even. For $a\ge 4$, we use the
 covering $n\equiv 0,1,2,3 \pmod{4}$. Let $r$ be a primitive prime divisor of $a^4-1$.
 If $a\equiv 4 \pmod{6}$, let $q$ be a primitive prime divisor of $a^2-1$, which exists since $a+1$ is not a power of 2.
 Note that $q\ne 3$ since 3 divides $a-1$. If $a\equiv 0,2 \pmod{6}$, let $q$ be any prime divisor of $a-1$.
 Observe that $q\ne 3$ here as well. Thus, when $n\equiv 1,2,3 \pmod{4}$, we see that $b_n \equiv -1
 \pmod{r}$, and consequently, $kb_n+1\equiv 0 \pmod{r}$ if $k\equiv 1 \pmod{r}$. Also, since \[kb_n+1>ka^{2n}+1\ge a^2+1\ge
 r,\]
 it follows that $kb_n+1$ is never equal to the prime $r$. When $n\equiv 0 \pmod{4}$,
  we have that $b_n \equiv 3 \pmod{q}$,
 and therefore $kb_n+1\equiv 0 \pmod{q}$ if $k\equiv -1/3 \pmod{q}$.
 As above, it is easy to see that $kb_n+1$ is never equal to the prime $q$.
  Then apply the Chinese Remainder Theorem to the system of congruences
\begin{center}
$\begin{array}{cccc}
k & \equiv & 1 & \pmod{r}\\  k & \equiv & -1/3 & \pmod{q}.\\
\end{array}$
\end{center}
%\begin{note}
%  This is exactly the same system of congruences as above since here $m-1=3$.
%\end{note}
For the case $a=2$, we use the covering
\begin{center}
$\begin{array}{cccc}
n & \equiv & 1,2,3 & \pmod{4}\\  n & \equiv & 0 & \pmod{8}\\ n & \equiv & 4 & \pmod{16}\\ n & \equiv & 12 & \pmod{32}\\ n & \equiv & 28 & \pmod{64}\\ n & \equiv & 60 & \pmod{64}\\
\end{array}$
\end{center}
and the corresponding covering set
$\left\{5,17,257,65537,641,6700417\right\}$, which lead to the
system of congruences
\begin{center}
$\begin{array}{cccc}
k & \equiv & 1 & \pmod{5}\\  k & \equiv & 11 & \pmod{17}\\ k & \equiv & 1 & \pmod{257}\\ k & \equiv & 4368 & \pmod{65537}\\ k & \equiv & 400 & \pmod{641}\\ k & \equiv & 6135898 & \pmod{6700417},\\
\end{array}$
\end{center}
having $k=4331277253353619796$ as its smallest solution. This completes the proof of part (\ref{composite}).

Part (\ref{easycase2andSier}) is just a special case of part (\ref{easycase1}) when $a\ge 3$, and it is just Theorem \ref{Sierpinski} when $a=2$.

%For the proof of part (\ref{aisoddprimeandage3}), let $m$ be an odd prime $p$. Let $q$ be a primitive prime divisor of $a-1$ and let $r$ be a primitive prime divisor of $a^p-1$.



%For the proof of part (\ref{misoddprime}), we use the letter $p$ in place of the letter $m$ to remind us that $m$ is a prime in this case.

To prove part (\ref{misoddprime}), let $m$ be an odd prime $p$, and assume first that $p\equiv 3 \pmod{4}$.
We use the covering
\begin{center}
$\begin{array}{cccc}
n & \equiv & 1,2,\ldots ,p-1 & \pmod{p}\\  n & \equiv & 0 & \pmod{2p}\\ n & \equiv & p & \pmod{4p}\\ n & \equiv & 3p & \pmod{4p}.\\
\end{array}$
\end{center}
Let $q$ be a primitive prime divisor of $a^p-1$.
When $n \equiv 1,2,\ldots ,p-1 \pmod{p}$, we have that $b_n\equiv -1 \pmod{q}$,
which implies that $kb_n+1\equiv 0 \pmod{q}$ if $k\equiv 1 \pmod{q}$. Therefore, since
\[kb_n+1\ge b_n+1 \ge b_1+1=a^{p-1}+a^{p-2}+\cdots +1\ge q,\] we conclude that $q$
 is a proper divisor of $kb_n+1$ when $k\equiv 1 \pmod{q}$ with $k>1$. In fact, $kb_n+1$ is never
 actually equal to the prime $q$ since forthcoming conditions on $k$ preclude the possibility that $k=1$.
 Now let $r$ be a primitive prime divisor of $a^{2p}-1$, except in the case $a=2$ and $p=3$, where we let $r=3$.
  With the exception of the case $a=2$ and $p=3$, note that $p<r$ since $2p$ divides $r-1$.
  So, in any case,
    when $n\equiv 0 \pmod{2p}$,  we see that $b_n\equiv p-1\not \equiv 0 \pmod{r}$.
     Thus, $kb_n+1\equiv 0 \pmod{r}$, if $k\equiv -1/(p-1) \pmod{r}$.
     Note that if $k=1$, then $p\equiv 0 \pmod{r}$, which is impossible, unless $a=2$ and $p=r=3$. Hence, $k>1$ unless $a=2$ and $p=r=3$.
      Now let $s$ be a primitive prime divisor of $a^{4p}-1$. Then, $a^p-1 \not \equiv 0 \pmod{s}$, and when $n\equiv p \pmod{4p}$, we have $b_n>s$ and
\[b_n\equiv \frac{a^p\left(a^{p(p-1)}-1\right)}{a^p-1} \not \equiv 0 \pmod{s},\]
since $p\equiv 3 \pmod{4}$. Next, let $u$ be a primitive prime divisor of $a^4-1$. Then, when $n\equiv 3p \pmod{4p}$, we have $b_n>u$ and  \[b_n\equiv \frac{a^{3p}\left(a^{3p(p-1)}-1\right)}{a^{3p}-1} \not \equiv 0 \pmod{u},\] since $p\equiv 3 \pmod{4}$. Finally, apply the Chinese Remainder Theorem to the system of congruences
\begin{center}
$\begin{array}{cccc}
k & \equiv & 1 & \pmod{q}\\ k & \equiv & -1/(p-1) & \pmod{r}\\  k & \equiv & -(a^p-1)/\left(a^p\left(a^{p(p-1)}-1\right)\right) & \pmod{s}\\ k & \equiv & -(a^{3p}-1)/\left(a^{3p}\left(a^{3p(p-1)}-1\right)\right) & \pmod{u}.\\
\end{array}$
\end{center} Note that when $a=2$ and $p=r=3$, we have that $s=13$. Therefore, the third congruence
 above is $k\equiv 11 \pmod{13}$, which implies that $k\ne 1$.
This completes the proof when $p\equiv 3 \pmod{4}$.

Now suppose that $p\equiv 5 \pmod{12}$. We use the covering
\begin{center}
$\begin{array}{cccc}
n & \equiv & 1,2,\ldots ,p-1 & \pmod{p}\\  n & \equiv & 0 & \pmod{2p}\\ n & \equiv & p & \pmod{6p}\\ n & \equiv & 3p & \pmod{6p}\\  n & \equiv & 5p & \pmod{6p}.\\
\end{array}$
\end{center}

We let $\left\{ q,r,s,u,v\right\}$ be the corresponding covering set of primes, where $q$, $r$, $s$, $u$ and $v$
 are, respectively, primitive prime divisors of $a^p-1$, $a^{2p}-1$, $a^3-1$, $a^{3p}-1$ and $a^{6p}-1$. 
 As above, similar arguments show the following for any $n$:
\begin{itemize}
\item $b_n$ is larger than the corresponding prime from the covering set
  \item $b_n$ is not divisible by the corresponding prime from the covering set (using the fact that $p\not \equiv 1 \pmod{12}$).
  %\item there are infinitely many values of $k$ such that $kb_n+1$ is divisible by, and not equal to, the corresponding prime from the covering set.
\end{itemize}
To finish the proof when $p\equiv 5 \pmod{12}$, apply the Chinese Remainder Theorem to the following system of congruences for $k$:
\begin{center}
$\begin{array}{cccc}
k & \equiv & 1 & \pmod{q}\\ k & \equiv & -1/(p-1) & \pmod{r}\\  k & \equiv & -(a^p-1)/\left(a^p\left(a^{p(p-1)}-1\right)\right) & \pmod{s}\\ k & \equiv & -1/(p-1) & \pmod{u}\\ k & \equiv & -(a^{5p}-1)/\left(a^{5p}\left(a^{5p(p-1)}-1\right)\right) & \pmod{v}.\\
\end{array}$
\end{center}
This completes the proof of part (\ref{misoddprime}).

%Next, for the proof of part (\ref{4}), we let $a$ be a perfect square, and let $m$ be any prime $p$. We use the covering $n\equiv 1,2,\ldots ,p-1 \pmod{p}$ and $n\equiv 0 \pmod{p}$. Let $q$ be a primitive prime divisor of $(a^{1/2})^p-1$, and let $r$ be a primitive prime divisor of $a^p-1$, which exists, except in the case when $a=4$ and $p=3$. In this exceptional case, we let $q=7$ and $r=3$ to achieve the desired result. When $n\equiv 1,2,\ldots ,p-1 \pmod{p}$, we have that $b_n\equiv -1 \pmod{q}$, and when $n\equiv 0 \pmod{p}$, we have that $b_n\equiv p-1 \pmod{r}.$ It is easy to see that $b_n$ is larger than the prime divisor in each of these situations. Then, using the Chinese Remainder Theorem to solve the system of congruences for $k$
%\begin{center}
%$\begin{array}{cccc}
%k & \equiv & 1 & \pmod{q}\\ k & \equiv & -1/(p-1) & \pmod{r},\\
%\end{array}$
%\end{center}
%finishes the proof of part (\ref{4}).

Finally, for the proof of part (\ref{Schinz}), suppose that $m/\left(e\K(a)\right)$ is an odd integer, where $\K(a)$, $e$, $m$ and $a$ are as given in Definition \ref{kernel} and Theorem \ref{Sch1}. Note that the exceptions mentioned in Theorem \ref{Sch1} are addressed in parts (\ref{composite}) and (\ref{misoddprime}) of this theorem. We can assume that $m$ is odd, since part (\ref{composite}) of this theorem handles the cases when $m\ge 4$ is even. We use the covering $n\equiv 0,1,2,\ldots ,m-1 \pmod{m}$. From Theorem \ref{Sch1}, we have that $a^m-1$ has at least two distinct primitive prime divisors. Let $q$ and $r$ be two such divisors. When $n\equiv 1,2,\ldots ,m-1 \pmod{m}$, we have that $b_n\equiv -1 \pmod{q}$, and when $n\equiv 0 \pmod{m}$, we have that $b_n\equiv m-1 \pmod{r}.$ It is easily verified that $b_n$ is greater than each of the primes $q$ and $r$. Then, we use the Chinese Remainder Theorem to solve the system of congruences:
\begin{center}
$\begin{array}{cccc}
k & \equiv & 1 & \pmod{q}\\ k & \equiv & -1/(m-1) & \pmod{r},\\
\end{array}$
\end{center}
which completes the proof of the theorem.
%and the proof is complete when $m$ is odd. %except when $m=3$ and $a=4$. In this particular situation, we let $q=7$ and $r=3$ to achieve the desired result.

%Now consider the case when $m$ is even. If $m\ge 4$, then this is just a subset of part (\ref{composite}) of this theorem. So suppose that $m=2$. We use the covering $n\equiv 0\pmod{2}$ and $n\equiv 1 \pmod{2}$. As before, from Theorem \ref{Sch1} we have that $a^2-1$ has at least two distinct primitive prime divisors. Let $q$ and $r$ be two such divisors. When $n\equiv 0 \pmod{2}$, we have that $b_n\equiv 1 \pmod{q}$, and when $n\equiv 1 \pmod{2}$, we have that $b_n\equiv -1 \pmod{r}.$ It is easy to see that $b_n$ is greater than the prime $q$ or $r$ in each of these situations. Then, we use the Chinese Remainder Theorem to solve the system of congruences:
%\begin{center}
%$\begin{array}{cccc}
%k & \equiv & -1 & \pmod{q}\\ k & \equiv & 1 & \pmod{r},\\
%\end{array}$
%\end{center}
%which completes the proof of the theorem.
\end{proof}

\begin{rem}\label{rem2}%\text{}
  %\begin{enumerate}
  %\item 
  For the case $a=2$ and $m=4$ in part (\ref{composite}) of Theorem \ref{Jmax},
  we can also use the covering and corresponding covering set that Sierpi\'{n}ski used in his original problem,
  namely:
\begin{center}
$\begin{array}{cccc}
n & \equiv & 1 & \pmod{2}\\  n & \equiv & 2 & \pmod{4}\\ n & \equiv & 4 & \pmod{8}\\ n & \equiv & 8 & \pmod{16}\\ n & \equiv & 16 & \pmod{32}\\ n & \equiv & 32 & \pmod{64}\\ n & \equiv & 0 & \pmod{64}\\
\end{array}$
\end{center}
and $\left\{3,5,17,257,65537,641,6700417\right\}$,
which lead to the system of congruences
\begin{center}
$\begin{array}{cccc}
k & \equiv & 1 & \pmod{3}\\ k & \equiv & 1 & \pmod{5}\\  k & \equiv & 1 & \pmod{17}\\ k & \equiv & 1 & \pmod{257}\\ k & \equiv & 1 & \pmod{65537}\\ k & \equiv & 1 & \pmod{641}\\ k & \equiv & 2233472 & \pmod{6700417}.\\
\end{array}$
\end{center}
The smallest solution is $k=10340920497641728921.$
%\item A slightly different argument for the situation when $a=2$ and $m=2^c$ in part (\ref{composite}) of Theorem \ref{Jmax} can be used. We use the same covering, but when $n\equiv 0 \pmod{2^c}$, we invoke a primitive prime divisor argument to show that $k=1$ will actually suffice: Let $2^w$ be the exact power of 2 that divides $n$; observe that a primitive prime divisor $q$ of $2^{2^{w+1}}-1$ divides $b_n$, and $b_n$ cannot be equal to $q$, so that $b_n$ is composite. Note that this argument does not work in Sierpi\'{n}ski's original problem since in that situation $b_n$ can actually be equal to $q$.
%\end{enumerate}
\end{rem}










We now give a proof of Conjecture \ref{Conjecture} assuming the truth of Conjecture \ref{C1}.



\begin{proof}[Proof of Conjecture \ref{Conjecture} assuming Conjecture \ref{C1}]
For composite $m$, the given proof of Theorem \ref{Jmax} suffices. So, assume that $m=p$ is prime.
Conjecture \ref{C1} implies that there exists a positive integer $t$ such that $a^{p^t}-1$ has at least two distinct primitive prime divisors: $q_t$ and $q_{t+1}$. We use the covering
\begin{center}
$\begin{array}{rccc}
n & \equiv & 1,2,\ldots ,p-1 & \pmod{p}\\
n & \equiv & p,2p,\ldots ,(p-1)p & \pmod{p^2}\\
\vdots & \vdots & \vdots & \vdots\\
n & \equiv & p^{t-2},2p^{t-2},\ldots ,(p-1)p^{t-2} & \pmod{p^{t-1}}\\
n & \equiv & p^{t-1},2p^{t-1},\ldots ,(p-1)p^{t-1} & \pmod{p^t}\\
n & \equiv & 0 & \pmod{p^t}\\
\end{array}$
\end{center}
with the corresponding covering set $\left\{q_1,q_2,\ldots ,q_{t+1}\right\}$ of primes, where $q_j$ is a primitive prime divisor of $a^{p^j}-1$, for $1\le j \le t-1$.
Then, when $n \equiv  p^{j-1},2p^{j-1},\ldots ,(p-1)p^{j-1}  \pmod{p^j}$, for any $1\le j \le t$, we have that \[b_n+1\equiv \frac{a^{zp^j}-1}{a^{zp^{j-1}}-1}\equiv 0\pmod{q_j},\]
for any $z\in \left\{1,2,\ldots ,p-1\right\}$. Also, when $n\equiv 0 \pmod{p^t}$, we have that $b_n\equiv p-1 \pmod{q_{t+1}}$. Since $p-1<p\le p^t<q_{t+1}$, it follows that $b_n\not \equiv 0 \pmod{q_{t+1}}.$ These conditions imply that, whenever $k$ satisfies the system of congruences
\begin{center}
$\begin{array}{ccccr}
k & \equiv & 1 & \pmod{q_j} &\hspace*{.11in} 1\le j\le t\\
k & \equiv & -1/(p-1) & \pmod{q_{t+1}},\\
\end{array}$
\end{center}
all terms $kb_n+1$ are composite. Again, by the Chinese Remainder Theorem, there exist infinitely many such positive integers $k$, and the proof is complete.
\end{proof}


\section{Acknowledgments}
The author thanks the referees for the valuable suggestions.

\begin{thebibliography}{99}
%widest-label}
\bibitem{Bang} A.S. Bang, Taltheoretiske Unders\S{o}gelser,
{\it Tidsskrift for Mat.} {\bf 5(4)} (1886), 70--80, 130--137
\bibitem{BHV} Yu. Bilu, G. Hanrot, P. M. Voutier, Existence of primitive divisors of Lucas and Lehmer numbers, With an appendix by M. Mignotte, {\it J. Reine Angew. Math.}  {\bf 539}  (2001), 75--122.
\bibitem{BV} G. D. Birkhoff and H. S. Vandiver, On the integral divisors of $a^n - b^n$, {\it Ann. of Math. (Second Series)} {\bf 5} (1903-1904), 173-180.

\bibitem{C1} Yong-Gao Chen, On integers of the form $2^n\pm p_1^{\alpha_1}\cdots p_r^{\alpha_r}$, {\it Proc. Amer. Math. Soc.}
{\bf 128} (2000), 1613--1616.

\bibitem{C2} Yong-Gao Chen, On integers of the form $k2^n+1$, {\it Proc. Amer. Math. Soc.} {\bf 129} (2001), 355--361.

\bibitem{C3} Yong-Gao Chen, On integers of the forms $k-2\sp n$ and $k2\sp n+1$, {\it J. Number Theory}  {\bf 89}  (2001), 121--125.


\bibitem{C4} Yong-Gao Chen, On integers of the forms $k\sp r-2\sp n$ and $k\sp r2\sp n+1$, {\it J. Number Theory}  {\bf 98}  (2003),  %no. 2, 
310--319.

\bibitem{E} P. Erd\H{o}s, On integers of the form $2\sp k+p$ and some related problems,  {\it Summa Brasil. Math.}  {\bf 2}  (1950), 113--123.

\bibitem{FFK} Michael Filaseta, Carrie Finch and Mark Kozek, {\it On powers associated with Sierpinski numbers, Riesel numbers and Polignac's conjecture}, (submitted).

\bibitem{Guy} Richard K. Guy, {\it Unsolved Problems in Number Theory, third edition},
Sringer-Verlag, 2004.

\bibitem{I} Anatoly S. Izotov, A note on Sierpi\'{n}ski numbers, {\it Fibonacci Quart.}  {\bf 33}  (1995), %no. 3,
206--207.

\bibitem{R} H. Riesel, N\aa gra stora primtal, {\it Elementa} {\bf 39} (1956), 258--260.

%\bibitem{M} Preda Mih\u{a}ilescu, Primary cyclotomic units and a proof of Catalan's conjecture.  J. Reine Angew. Math.  572  (2004), 167--195.

\bibitem{S} A. Schinzel, On primitive prime factors of $a\sp{n}-b\sp{n}$, {\it Proc. Cambridge Philos. Soc.}  {\bf 58} (1962), 555--562.

\bibitem{ST} A. Schinzel and R. Tijdeman, On the equation $y\sp{m}=P(x)$, {\it Acta Arith.} {\bf 31}  (1976), %, no. 2
199--204.

\bibitem{Sier} W. Sierpi\'{n}ski, Sur un probl\`{e}me concernant les nombres $k2^n+1$, {\it Elem. d. Math.} {\bf 15} (1960), 73--74.

\bibitem{Z} K. Zsigmondy, Zur Theorie der Potenzreste, {\it Monatshefte f|r Math. u. Phys.} {\bf 3} (1892), 265--284.







\end{thebibliography}
 
\bigskip
\hrule
\bigskip

\noindent 2000 {\it Mathematics Subject Classification}:
Primary 11B25, 11B07; Secondary 11B99.

\noindent \emph{Keywords: } Sierpi\'{n}ski number; arithmetic progression; primitive divisor.


\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received November 14 2006;
revised version received April 14 2007.  
Published in {\it Journal of Integer Sequences}, April 14 2007.

\bigskip
\hrule
\bigskip

\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in


\end{document}

                                                                                



