\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 $yb^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}