\documentclass[12pt,reqno]{article}
\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{amscd}
\def\ds{\displaystyle}
\def\beq{\begin{equation}}
\def\eeq{\end{equation}}
\def\tm#1{\left(\text{mod }#1\right)}
\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{amsthm}
\usepackage{amsfonts}
\usepackage{latexsym}
\usepackage{epsf}
\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.5in}
\setlength{\textheight}{8.9in}
\newcommand{\seqnum}[1]{\href{http://www.research.att.com/cgi-bin/access.cgi/as/~njas/sequences/eisA.cgi?Anum=#1}{\underline{#1}}}
\begin{document}
\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}
\begin{center}
\vskip 1cm{\LARGE\bf
On the Equation $a^x\equiv x \tm {b^{n}}$
}
\vskip 1cm
\large
J. Jim\'enez Urroz and J. Luis A. Yebra\\
Departament de Matem\`{a}tica Aplicada IV\\
Universitat Polit\`{e}cnica de Catalunya \\
Campus Nord, Edifici C3 \\
C. Jordi Girona, 1-3 \\
08034 Barcelona\\
Spain\\
\href{mailto:jjimenez@ma4.upc.edu}{\tt jjimenez@ma4.upc.edu}\\
\href{mailto:yebra@ma4.upc.edu}{\tt yebra@ma4.upc.edu}\\
\end{center}
\vskip .2 in
\begin{abstract}
We study the solutions of the equation $a^x\equiv x \tm
{b^{n}}$. For some values of $b$, the solutions
have a particularly rich structure. For example, for $b=10$ we find that for
every $a$ that is not a multiple of $10$ and for every $n\geq 2$, the
equation has just one solution $x_n(a)$. Moreover, the solutions for
different values of $n$ arise from a sequence $x(a)=
\{x_{i}\}_{i\geq 0}$, in the form $x_n(a)=\sum_{i=0}^{n-1} x_i 10^i$.
For instance, for $a=8$ we obtain $$ 8\,^{56} \equiv 56 \tm
{10^2},\quad \qquad 8\,^{856} \equiv 856 \tm {10^{3}}, \quad\qquad
8\,^{5856} \equiv 5856 \tm {10^{4}},\quad \dots $$
In this paper we
prove these results and provide sufficient conditions for the base $b$
to have analogous properties.
\end{abstract}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{defin}[theorem]{Definition}
\newenvironment{definition}{\begin{defin}\normalfont\quad}{\end{defin}}
\newtheorem{examp}[theorem]{Example}
\newenvironment{example}{\begin{examp}\normalfont\quad}{\end{examp}}
\newtheorem{rema}[theorem]{Remark}
\newenvironment{remark}{\begin{rema}\normalfont\quad}{\end{rema}}
\def\de{\delta}
\def\ep{\varepsilon}
\def\vf{\varphi}
\def\sg{\sigma}
\def\ap{\alpha}
\def\A{\Cal A}
\def\om{\omega}
\def\ga{\gamma}
\def\be{\beta}
\newtheorem{thm}{Theorem}
\newtheorem{cor}[thm]{Corollary}
\newtheorem{lem}[thm]{Lemma}
\newtheorem{claim}[thm]{Claim}
\newtheorem{axiom}[thm]{Axiom}
\newtheorem{conj}[thm]{Conjecture}
\newtheorem{fact}[thm]{Fact}
\newtheorem{hypo}[thm]{Hypothesis}
\newtheorem{assum}[thm]{Assumption}
\newtheorem{prop}[thm]{Proposition}
\newtheorem{crit}[thm]{Criterion}
\newtheorem{defn}[thm]{Definition}
\newtheorem{exmp}[thm]{Example}
\newtheorem{rem}[thm]{Remark}
\newtheorem{probl}[thm]{Problem}
\newtheorem{prin}[thm]{Principle}
\newtheorem{alg}{Algorithm}
\newtheorem{obs}[thm]{Observation}
\section{Introduction}
\label{intro}
The fact that $\ds 7\,^{343}$ ends in $343$
might appear to be a curiosity. However, when this can be uniquely extended to
$$
7\,^{630680637333853643331265511565172343} = \cdots
630680637333853643331265511565172343 ,
$$
and more, it begins to be interesting. Besides, instead of $7$, any other positive integer $a$ (as long as it is not a multiple of $10$)
will do. For instance, for $a=12$, we find
$$
12\,^{52396359135848584931714421454012416} = \cdots
52396359135848584931714421454012416 .
$$
More precisely, we prove below that for any positive integer $a$, not a multiple of $10$, there exists just one infinite sequence of digits,
$$ x(a)= \cdots \, x_{i} \cdots x_2 \, x_1 \, x_0 $$
such that for every $n\geq 2$ the number
$$x_n(a) = \sum_{i=0}^{n-1} x_i 10^i=x_ {n-1}\cdots x_2 x_1 x_0$$
is the only such number that satisfies
\beq
a^{x_n(a)}\equiv x_n(a) \tm {10^{n}}.
\eeq
Moreover, this result holds not just for base $b=10$;
an analogous result holds when $b$ is squarefree and such that for every prime $p|b$ and every prime $q|p-1$ we have $q|b\:$.
For any positive integer $a$, not a multiple of $b$, there exists an infinite sequence of $b$-digits,
$$ x(a,b)= (\cdots \, x_{i} \cdots x_2 \, x_1 \, x_0)_b $$
such that for every $n\geq n(b)$, which is characterized below, the number
$$x_n(a,b) = \sum_{i=0}^{n-1} x_i b^i= (x_ {n-1} \cdots x_2 \, x_1 \, x_0 )_b $$
satisfies
\beq \label{meq}
a^{x_n(a,b)}\equiv x_n(a,b) \tm {b^{n}}.
\eeq
For instance, for $b=6$ and $a=4$ we have
$$
x(4,6)=\cdots 3211201450455542325540435055354110453104_6,
$$
so that when, say, $n=11$, we get
$$x_{11}(4,6)=54110453104_6= 344639488 \quad {\rm and }\quad 4^{344639488}\equiv 344639488 \tm {6^{11}}.$$
When the base $b$ is not squarefree, instead of multiples of $b$, we
must remove any multiple of $s(b)$, the squarefree part of $b$, for
obvious reasons.
Finally, the conditions described above are suffcient to guarantee the
existence of at least one such sequence $x(a,b)$, but they are not necessary. It might be
the case that for some other base $b$ and some value of $a$ there exist a sequence $x(a,b)$ as above. As an example we have for $b=9$ and $a=4$ the sequence $x(4,9)=\cdots 4444444_9$.
\section{Main results} \label{Mr}
We only use elementary number theory and refer to Hardy and Wright \cite{HW} or Riesel \cite{Rie} for any concept not defined here. We will write the prime factorization of an integer $b$ as $b=\prod_p p^{v_p(b)}$, and denote by $e(b)=\max_{p|b}\{v_p(b)\}$, the highest power of a prime dividing $b$.
We will also denote $s(b)=\prod_{p|b}p$ the squarefree part of $b$.
\begin{thm} \label{exp-solution} For every pair of integers $a,b$ there exists an
integer $x\ge e(b)+1$ such that
$$
a^x\equiv x\pmod b.
$$
\end{thm}
For the proof we will need the following observation.
\begin{lem}\label{Euler} Let $a,b$ integers and $x\ge e(b)$ a solution to the equation
$$
a^x\equiv x\pmod{\varphi(b)}.
$$
Then
$$
a^{a^x}\equiv a^x\pmod{b}.
$$
\end{lem}
{\it Proof:} Let $b=b_1b_2$ where $\gcd (b_1,a)=1$ and if $p|b_2$ then $p|a$. Then $\varphi(b_1)|\varphi(b)$ and, hence, $a^x\equiv x\tm{\varphi(b_1)}$. It is now a simple consequence of Euler\'{}s theorem to
get
$$
a^{a^x}\equiv a^x\tm{b_1}.
$$
On the other hand, we trivially have
$$
a^{a^x}\equiv a^x\equiv 0\tm{b_2}.
$$
The result now follows from the Chinese Remainder Theorem.
\
{\it Proof of Theorem \ref{exp-solution}:}
We proceed by induction on $b$, noting that the result is trivial for $b=1, 2$. Let us suppose we have already proven the theorem for every integer less than $b$ and we want to prove the result for $b$. We will also suppose $a>1$. Now, noting that $\varphi(b)**1$ and $x\ge 0$, we get $a^x\ge x+1\ge e(b)+1$,
as desired.
\
\noindent{\bf Definition:}
We say that an integer $b$ is a {\em valid base} if for every prime $p|b$ and every prime $q|p-1$ we have $q|b$. We will let $n(b)$ be the minimum integer such that $(p-1)|b^{n(b)}$ for every $p|b$.
\
\noindent{\bf Remarks:} The existence of such an integer $n(b)$ is clear from the definition of valid base. It is straightforward to see that a valid
base $b$ must be even. It is also easy to see that $b=2, 4, 6, 8, 10, 12, 16, 18, 20, 24,$ and $30$ are the first valid bases while $b=2, 6, 10, 30, 34, 42, 78, 102$ and $110$ are the first valid squarefree bases. Observe also that when $b$ is
squarefree, $n(b)=\max_{p|b}\{\max_{q|b}\{v_q(p-1)\}\}$. Thus,
we have $n(10)=2$ and $n(34)=4$, while $n(100)=1$.
\
Apart from the bases given in this Remark, one can ask whether
there exist other valid bases and how to find them. The following list
provides different ways of constructing new valid bases. In particular we note the existence of infinitely many valid bases.
\begin{itemize}
\item The product of valid bases is a valid base.
\item If $b$ is a valid base and $p$ is a prime such that $p-1|b^r$, for some $r$, then $pb$ is also a valid base.
\item $b=m!$ is a valid base for every $m$.
\item For every integer $r$, $b=\prod_{p\le r}p$ is a valid base.
\end{itemize}
The first two statements are direct consequences of the definition. For the third and fourth
we just have to note that if $p|b$ and $q|p-1$, then $q\le m$ in the third statement,
while $q\le r$ in the last one.
\
The main result, where we denote the number $x_n(a,b)$ by $x_n$ for short, follows.
\begin{thm}\label{main} Let $b$ be a valid base, and $s(b)$ its
squarefree part. Then, for every integer $a$ not a multiple of $s(b)$
there
exist a unique sequence $\{c_n\}_{n\ge n_b}$ of digits, $0\le c_n < b,$
such that the integers $x_{n+1}=x_n+c_nb^n$ verify
$$
a^{x_n}\equiv x_n\pmod {b^n},
$$
for every $n > n(b)$.
\end{thm}
{\it Proof:} To clarify the argument, we first present the case when $b$ is a squarefree integer. In all the cases below, we will proceed by induction on $n$.
{\bf Case I: } $b$ is squarefree and $\gcd (a,b)=1$.
Suppose that for some $n\ge n(b)$
$$
a^{x_n}\equiv x_n\tm {b^{n}}.
$$
(Observe that we know this is true for $n= n(b)$ by Theorem \ref{exp-solution} with $b^{n(b)}$ instead of $b$). Then,
$$
a^{x_n}\equiv x_n+c_nb^n\tm {b^{n+1}},
$$
for some $0\le c_n < b$. Now, it is immediate to observe that for a valid base it is
always true that $\varphi(p^{n+1})|b^n$ for every integer $n\ge n(b)$ and every prime $p|b$. Hence, since $a^{\varphi(p^{n+1})}\equiv 1\tm{p^{n+1}}$, we have, for every integer $m$
$$
a^{mb^n}\equiv 1\tm {b^{n+1}},
$$
by the Chinese Remainder Theorem. In particular
$$
a^{x_n+c_nb^n}\equiv a^{x_n}\tm {b^{n+1}}\equiv x_n+c_nb^n\tm {b^{n+1}},
$$
that is
$$
a^{x_{n+1}}\equiv x_{n+1} \tm {b^{n+1}},
$$
and the selection of $c_n$ is unique.
\
{\bf Case II: } $b$ is squarefree and $\gcd (a,b)>1$.
Let $b=b_1b_2$ be such that $\gcd (b_1,a)=1$, and $b_2|a$. Again the proof proceeds by induction, and we suppose
\begin{equation}\label{notcoprime}
a^{x_n}\equiv x_n\tm {b^{n}}\equiv x_n+c_nb^n\tm {b^{n+1}},
\end{equation}
for $n\ge n(b)$. In this case, and in the same way as before, we have for every integer $m$
$$
a^{mb^n}\equiv 1\tm {b_1^{n+1}},
$$
since $\gcd(a,b_1)=1$. In particular
$$
a^{x_n+c_nb^n}\equiv a^{x_n}\tm {b_1^{n+1}}\equiv x_n+c_nb^n\tm {b_1^{n+1}}.
$$
On the other hand, it is easy to see that $b_2^{n+1}|\gcd (a^{x_n+c_nb^n}, x_n+c_nb^n)$. Indeed, if $x_{n}\ge n+1$ then trivially $b_2^{n+1}|a^{x_{n}+c_nb^n}$ and
$b_2^{n+1}|\gcd (a^{x_{n}},b^{n+1})$. Hence, $b_2^{n+1}$ divides $x_{n}+c_nb^n$ by (\ref{notcoprime}). Furthermore, $x_n> 0$ and so, again by (\ref{notcoprime}), we can see that $b_2^n|x_n$ and, in particular, $x_{n}\ge n+1$. Hence,
$$
a^{x_n+c_nb^n}\equiv x_n+c_nb^n\tm {b_2^{n+1}},
$$
and the result follows from the Chinese Remainder Theorem.
\
{\bf Case III: } $b$ is not squarefree and $\gcd (a,b)=1$.
Let $b=\prod p^{v_p(b)}=P_1^{\ap_1}\cdots P_r^{\ap_r}$ where $\ap_1<\ap_2<\dots<\ap_r$ and $P_i$ are squarefree for $i=1,\dots, r$. We will also denote $B_j=\prod_{i=1}^{j-1}P_i^{\ap_i}$, and $B_1=1$. Suppose again
$$
a^{x_n}\equiv x_n\tm {b^{n}}
$$
for some $n\ge n(b)$. Then
$$
a^{x_n}\equiv x_n+c_{1,1,n}b^n\tm {P_1b^{n}},
$$
and $0\le c_{1,1,n} < P_1$. Again, as before, $\varphi(p^{nv_p(b)+1})|b^n$ for any $n\ge n(b)$ and $p|P_1$, so that, arguing as before, we get that for any integer $m$
$$
a^{mb^n}\equiv 1\tm {P_1b^{n}}.
$$
In particular,
$$
a^{x_n+c_{1,1,n}b^n}\equiv a^{x_n}\tm {P_1b^{n}}\equiv x_n+c_{1,1,n}b^n\tm {P_1b^{n}}.
$$
Repeating this process, and noting that $\varphi(p^{nv_p(b)+i})|P_1^{i-1}b^n$, we get
\begin{equation}\label{P1}
a^{x_{n,1}}\equiv x_{n,1}\tm {P_1^{\ap_1}b^{n}},
\end{equation}
for a unique
$$
x_{n,1}=x_n+\left(\sum_{i=0}^{\ap_1-1}c_{i,1,n}P_1^{i}\right)b^n,
$$
where $0\le c_{i,1,n}1$.
The proof is now the same as in Case II and we omit it.
\bigskip
\noindent {\bf Remark:} It is very important to notice that, whenever $n\ge n(b)$, even if the solution guaranteed by Theorem \ref{exp-solution} is $x\ge b^n$, we can find another one $y****b^n$, then $x=\sum_{i=0}^{n-1}c_ib^i+\sum_{i=n}^{k}c_ib^i=y+b^nY$ for some $y\ne 0$, since otherwise $a$ is a multiple of $s(b)$. But then,
$$
y\equiv 0\tm{b_2^n},
$$
since $a^x\equiv 0\tm {b_2^n}$ and $a^x\equiv y\tm {b_2^n}$. But then,
$y\ge b_2^n\ge e(b_2)n$, and we also have
$$
a^y\equiv 0\equiv y\tm {b_2^n}.
$$
Finally, since $n\ge n(b)$, $a^{b^n}\equiv 1\tm {b_1^n}$, and so
$$
a^y\equiv y\tm {b_1^n}.
$$
The result is now a consequence of the Chinese Remainder Theorem.
Besides, it is easily verified that when $b=10$ there is just one solution $y<10^{n(10)}=100$ for every $a$ (not a multiple of $10$), since it suffices to check values of $a \bmod 100$. Thus there is a unique sequence $x(a)$ for every $a$. Although this seems to be the case for all valid bases $b$, it does not follow from Theorem \ref{exp-solution}.
\begin{cor}\label{cor} If $b$ is a valid base, for every integer $a$,
not a multiple of $s(b)$, there exist a sequence $\{x_n\}_{n\ge 0}$
of digits $0\le x_n < b$ such that the integers
$$ x_n(a,b)=\sum_{i=0}^{n-1} x_i b^i= (x_ {n-1} \cdots x_2 \, x_1 \,
x_0 )_b $$
verify
\beq
a^{x_n(a,b)}\equiv x_n(a,b) \pmod {b^n}, \tag{\ref{meq}}
\eeq
for every $n\ge n(b)$. When $b$ is squarefree, $s(b)=b$ and this holds
for every integer $a$, not a multiple of $b$. For $b=10$ there exists just one such sequence $x(a)$.
\end{cor}
\section{Other bases} \label{Ob}
As we mentioned in the introduction, Corollary \ref{cor} uses
sufficient conditions for the base $b$ to ensure the existence of a
sequence $x(a,b)$ for any nontrivial integer $a$. When $b$ is not a
valid base, however, a sequence $x(a,b)$ can still appear for some
integers $a$. Indeed, as we can see in the proof of Theorem \ref{main},
the only condition needed is that $a^{c_nb^n}\equiv 1\tm {b^{n+1}}$
holds. This is true for any valid base, but we can build many other
examples for invalid bases. For example, consider an integer $b$ and
let
$m|b-1$ such that $m^b\equiv -1\tm b$, and let $a=m^m$. Then it is easy to see by induction that $m^{b^r}\equiv -1\tm {b^r}$ for any $r$, and so
$$
ma^{{\frac{b-1}{m}}\sum_{i=0}^{n-1}{b^i}}= m^{b^n}\equiv -1\tm {b^n}.
$$
On the other hand
$$
m\left(\frac{b-1}{m}\right)\sum_{i=0}^{n-1}{b^i}=b^n-1\equiv -1\tm {b^n},
$$
and so $x(a,b)=\overline{\left(\frac{b-1}{m}\right)}_b$ is the desired sequence which provides a solution to the equation
$a^{x_n}\equiv x_n\tm {b^n}$ for every $n$. The example at the end of the introduction, $x(4,9)=\bar4_9$, is a particular case of this example with $m=2$, $b=9$. Also this framework allows us to prove the following simple example
\begin{cor} Let $b>1$ an odd integer and $a=(b-1)^{b-1}$. Then
$$
a^{x_n}\equiv x_n \pmod {b^n},
$$
for any $n$ and $x_n=\sum_{i=0}^{n-1}b^i$. In other words, $x(a,b)=\bar1_b$.
\end{cor}
\bigskip
\noindent
\section{Acknowledgments}
This work was partially supported by Secretar\'{\i}a de Estado de
Universidades e Investigaci\'on del Ministerio de Educaci\'on y Ciencia
of Spain, DGICYT through grants MTM2006-15038-C02-02, TSI2006-02731 and
MTM2009-11068 for the first author and TEC2005-03575 for the second
author. It was done while the first author was visiting CRM at
Montreal, and he wishes to thank this institute for its hospitality.
Finally, the authors want to thank M. C. Mu\~noz Lecanda.
\bigskip
\begin{thebibliography}{99}
\bibitem{HW}G. H. Hardy and E. M. Wright, {\it An Introduction to the Theory of Numbers}, Oxford University Press, 2008.
\bibitem{Rie}
H. Riesel, {\it Prime Numbers and Computer Methods for Factorization},
Birkhauser, 1994.
\end{thebibliography}
\bigskip
\hrule
\bigskip
\noindent 2000 {\it Mathematics Subject Classification}:
Primary 11A07.
\noindent \emph{Keywords: } exponential, congruences, integer sequences.
\bigskip
\hrule
\bigskip
\noindent (Concerned with sequences
\seqnum{A133612},
\seqnum{A133613},
\seqnum{A133614},
\seqnum{A133615},
\seqnum{A133616},
\seqnum{A133617},
\seqnum{A133618},
\seqnum{A133619},
\seqnum{A144539},
\seqnum{A144540},
\seqnum{A144541},
\seqnum{A144542},
\seqnum{A144543},
\seqnum{A144544},
\seqnum{A151999}, and
\seqnum{A152000}.)
\bigskip
\hrule
\bigskip
\vspace*{+.1in}
\noindent
Received June 10 2009;
revised version received November 18 2009.
Published in {\it Journal of Integer Sequences}, November 25 2009.
\bigskip
\hrule
\bigskip
\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in
\end{document}
**