\documentclass[12pt]{article} \textwidth= 6.5in \textheight= 9.0in \topmargin = -20pt \evensidemargin=0pt \oddsidemargin=0pt \headsep=25pt \parskip=10pt \font\smallit=cmti10 \font\smalltt=cmtt10 \font\smallrm=cmr9 \usepackage{latexsym,amssymb} \begin{document} \vspace*{-40pt} \centerline{\smalltt INTEGERS: \smallrm ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY \smalltt 7 (2007), \#A03} \vskip 40pt \begin{center} {\bf GENERALIZATIONS OF MIDY'S THEOREM ON REPEATING DECIMALS} \vskip 20pt {\bf Harold W. Martin}\\ {\smallit Department of Mathematics and Computer Science, Northern Michigan University, Marquette, MI 49855, USA}\\ {\tt hmartin@nmu.edu}\\ \end{center} \vskip 30pt \centerline{\smallit Received: 4/14/06, Accepted: 1/2/07, Published: 1/25/07} \vskip 30pt \centerline{\bf Abstract} \noindent Let $n$ denote a positive integer relatively prime to 10. Let the period of $1/n$ be $a \cdot b$ with $b>1$. Break the repeating block of $a \cdot b$ digits up into $b$ sub blocks, each of length $a$, and let $B(n,a,b)$ denote the sum of these $b$ blocks. In 1836, E. Midy proved that if $p$ is a prime greater than 5, and the period of $1/p$ is $2 \cdot a$, then $B(p,a,2) = 10^a - 1$. In 2004, B. Ginsberg [2] showed that if $p$ is a prime greater than 5, and the period of $1/p$ is $3 \cdot a$, then $B(p,a,3) = 10^a - 1.$ In 2005, A. Gupta and B. Sury [3] showed that if $p$ is a prime greater than 5, and the period of $1/p$ is $a \cdot b$ with $b > 1$, then $B(p,a,b) = k \cdot (10^a - 1)$. (The results of Midy and Ginsberg follow quickly from this). In this paper we examine the case in which $p$ is not necessarily prime. Define two positive integers $u$ and $v$ to be {\it period compatible} provided that there exist odd integers $r$ and $t$ and a positive integer $s$ such that the periods of $1/u$ and $1/v$ are of the form $r \cdot 2^s$ and $t \cdot 2^s$ respectively. Let $n$ be a positive integer relatively prime to 10 and let the period of $1/n$ be $a \cdot b$ with $b > 1$. The following are proved: \vspace*{-10pt} \begin{quote} (i) If $n$ is relatively prime to $10^a - 1$, then $B(n,a,b) = k \cdot (10^a - 1)$.\\ (ii) If for every prime factor $p$ of $n$, the integer $a$ is not a multiple of the period of $1/p$, then $B(n,a,b) = k \cdot (10^a - 1)$.\\ (iii) If $b = 2$, then $B(n,a,2) = 10^a - 1$ if, and only if, every two prime factors of $n$ are period compatible. \end{quote} \pagestyle{myheadings} \markright{\smalltt INTEGERS:\smallrm ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY \smalltt 7 (2007),\#A03\hfill} \thispagestyle{empty} \baselineskip=15pt \vskip 20pt \section*{\normalsize Introduction} %%%%%%%%%%%%%% section 1 According to Dickson [1], Midy's Theorem was first given in [5]. The theorem, without reference to [5], is also proven in both [4] and [6]. Let $n$ denote a positive integer that is relatively prime to 10, and let $B(n)$ denote the smallest repeating block of digits in the decimal expansion of $1/n$. For example, $B(7) = 142857$, and $B(13) = 076923$. By the {\it period} of $1/n$ we mean the number of digits in $B(n)$, that is, the order of 10 ($mod$ $n$). A simple computation establishes the following identity, which we label for future reference: \qquad (1) \qquad \qquad $n \cdot B(n) = 10^k-1$, where $k$ is the order of 10 ($mod$ $n$). %%%%%%%%%%%% 1 If $k = a \cdot b$, then we can split $B(n)$ up into $b$ sub-blocks, each of length $a$. The $i^{th}$ such sub-block will be denoted by $B_i(n,a,b)$. For example, $$ \begin{array}{ll} B(31)= 032258064516129 & B_1(31,5,3) = 03225 \\ B_2(31,5,3) = 80645 & B_3(31,5,3) = 16129. \end{array} $$ Finally, let $B(n,a,b)$ denote the sum of the numbers $B_i(n,a,b)$ for $1\leq i \leq b$. In our example, \vskip 5pt \centerline{$B(31,5,3) = 03225 + 80645 + 16129 = 99999$.} Continuing to let $k$ denote the order of \emph{10 ($mod$ n)} and letting $k = ab$, define $N(a,b)$ by \qquad (2) \qquad \qquad $N(a,b) = (10^k - 1)/(10^a - 1)$. %%%%%%%%%%%%%%%%%% 2 \noindent Note that $N(a,b)= 10^{k-a} + 10^{k-2a} + \ldots + 10^a + 1$. Combining Equations (1) and (2), we get the following simple relationship: \qquad (3) \qquad \qquad $(10^a - 1)\cdot N(a,b) = n \cdot B(n)$. %%%%%%%%%%%%%%%%% 3 Let $n$ be a positive integer that is relatively prime to 10. Suppose that $k$ is the order of 10 ($mod$ $n$) and that $k = a \cdot b$ with $b > 1$. We say that $n$ has the \emph{9's property with respect to b} provided that $B(n,a,b)$ is a multiple of $10^a - 1$. In case $B(n,a,b) = 10^a - 1$, we say that $n$ has the \emph{9's property}. We abbreviate the phrase \emph ``{9's property with respect to $b$}'' by \emph ``{9's property[b]}.'' Theorem 1 below characterizes those integers $n$ such that $n$ has the 9's property[b]. From this we establish in Theorem 2 that if $p$ is a prime greater than 5 and the length of the period $B(p)$ is $a \cdot b$ with $b>1$, then $p$ has the 9's property[b]. In Section 3 we generalize Midy's Theorem in another way by giving a characterization of those integers $n$ that have the 9's property[2], (Theorem 8). \vskip 20pt \section*{\normalsize 1. The First Generalization}%%%%%%%%%%%% section 2 The following theorem is useful in proving the first generalization of Midy's Theorem. %%%%%%%%%% theorem 1 \noindent {\bf Theorem 1} \emph {Let $n$ be a positive integer relatively prime to 10, and $k = a \cdot b$ be the order of 10 ($mod$ $n$). The sum $B(n,a,b)$ is divisible by $10^a - 1$ if, and only if, $n$ divides $N(a,b)$. That is, $n$ has the 9's property[b] if, and only if, $n$ divides $N(a,b)$.} %%%%%%%%%%%% proof \noindent {\it Proof.} The period $B(n)$ in the decimal expansion of $1/n$ can be represented as follows: \begin{center} $B(n) = B_1(n,a,b) \cdot 10^{k-a} + B_2(n,a,b)\cdot 10^{k-2a}+\ \cdots\ + B_{b-1}(n,a,b) \cdot 10^{a} + B_{b}(n,a,b).$ \end{center} \noindent From this we get the following equation: %%%%%%%%%%%%%%%%%%%% 4 \quad(4)\quad $B(n) = B_1(n,a,b) \cdot [10^{k-a}-1] + B_2(n,a,b)\cdot [10^{k-2a}-1] +\ \cdots\ + B_{b-1}(n,a,b) \cdot [10^{a}-1]+ B(n,a,b)$. \noindent Since $10^a - 1$ divides $10^{k - ia} - 1$ for all $i$ satisfying $ 1\leq i < b$, from Equation (4) we derive the following: %%%%%%%%%%%%%%%%%%% 5 \quad (5) \quad $10^a - 1$ divides $B(n)$ if, and only if, $10^a -1$ divides $B(n,a,b)$. \noindent (Statement (5) is simply ``casting out 9's'' in base $10^a$). It is now easy to finish the proof. Assume that $10^a - 1$ divides $B(n,a,b)$. Then by Statement (5) it follows that $10^a - 1$ must divide $B(n)$. But then $10^a - 1$ factors out of both sides of Equation (3) and so it follows from Equation (3) that $n$ divides $N(a,b)$. Conversely, assume that $n$ divides $N(a,b)$. Then from Equation (3) it follows that $10^a - 1$ divides $B(n)$. But then $10^a - 1$ divides $B(n,a,b)$ by Statement (5), completing the proof. \hfill $\Box$ The following, the first generalization of Midy's Theorem, follows immediately from Equation (3) and Theorem 1. %%%%%%%%%%%%% theorem 2 \noindent {\bf Theorem 2}\ \emph{Let $n$ be a positive integer relatively prime to 10 and let $k = a \cdot b$ be the order of $n$ with $b > 1$. If $n$ is relatively prime to $10^a - 1$, then $B(n,a,b)$ is a multiple of $10^a -1$. In particular, if $n$ is a prime number greater than 5, then $n$ has the 9's property[b].} Here is another easy consequence of Theorem 1. %%%%%%%%%%%%%%%% theorem 3 \noindent {\bf Theorem 3} \emph{Let $n$ be a positive integer relatively prime to 10 and $k = a \cdot b$ be the period of $1/n$ with $b > 1$. If for every prime factor $p$ of $n$, the integer $a$ is not a multiple of the period of $1/p$, then $n$ has the 9's property [b]}. %%%%%%%%%%%%%%% proof \noindent {\it Proof.} Suppose that for every prime factor $p$ of $n$ we have that the integer $a$ is not a multiple of the order of 10 ($mod$ $p$). Then $p$, being prime, is relatively prime to $10^a - 1$. But $n$ divides $10^k - 1$ and so $p$ also divides $10^k - 1$. But then by Equation (2) and the fact that $p$ is relatively prime to $10^a - 1$, we have that $p$ is a divisor of $N(a,b)$. Let $i$ be the multiplicity of the prime $p$ as a factor of $n$. Then $p^i$ is relatively prime to $10^a - 1$, and the same argument we just used to show that $p$ is a divisor of $N(a,b)$ also shows that $p^i$ is a divisor of $N(a,b)$. Since $p$ was an arbitrary prime factor of $n$, it follows that $n$ is a divisor of $N(a,b)$. But then by Theorem 1 it follows that $B(n,a,b)$ is a multiple of $10^a - 1$, that is, $n$ has the 9's property[b]. \hfill $\Box$ The following example illustrates Theorem 3. %%%%%%%%%%%%% example 4 \noindent {\bf Example 4} Let $n = 217 = 7 \cdot 31$. The order of 10 ($mod$ 7) is 6, the order of 10 ($mod$ 31) is 15, and the order of 10 ($mod$ 217) is 30. In particular, B(217) is given by \qquad \qquad \qquad B(217) = 004608294930875576036866359447. \noindent The following table indicates whether $B(217,a,b)$ is a multiple of $10^a - 1$ or not. Whenever the integer $a$ is neither a multiple of 6 nor of 15, then Theorem 3 guarantees that the 9's property[b] will hold. Therefore, all the cases in the following table, except those for $a = 6$ and $a = 15$, are guaranteed by the theorem. \begin{center} \( \begin{array}{ccccccccccc} & & & & & & & \mbox{There exists {\it q} such that}\\ & a & & & b & & & B(217,a,b) = q \cdot (10^a - 1)\\ \hline %& & & & & & & & & \\ & 1 & & & 30 & & & \mbox{yes} \\ & 2 & & & 15 & & & \mbox{yes} \\ & 3 & & & 10 & & & \mbox{yes}\\ & 5 & & & 6 & & & \mbox{yes} \\ & 6 & & & 5 & & & \mbox{no} \\ & 10 & & & 3 & & & \mbox{yes} \\ & 15 & & & 2 & & & \mbox{no} \end{array}\) \end{center} \noindent \section*{\normalsize 2. The Second Generalization}%%%%%%%%%%%%%%%%section 3 The second generalization of Midy's Theorem returns to the restriction on the order of 10 ($mod$ $n$) being even, but relaxes the condition that $n$ be prime. In fact, under the condition that the order of 10 ($mod$ $n$) be even and $n$ is relatively prime to 10, the theorem characterizes those integers $n$ such that $B(n,a,2) = 10^a - 1$. Throughout this section $n$ is relatively prime to 10, and the period of $1/n$ is $k = 2a$. The block $B(n)$ is divided into two sub-blocks, so $b = 2$ and $a = k/2$. Also in this section, by \emph{9's property} we mean 9's property with respect to 2. Suppose that $n$ has the 9's property. By Theorem 1, $n$ divides $10^a + 1$. If $p$ is a prime factor of $n$, then $p$ also divides $10^a + 1$. But then $p$ clearly cannot divide $10^a - 1$. It follows that $n$ is relatively prime to $10^a - 1$. It is easy to see that $a$ is the smallest positive integer $j$ such that $n$ divides $10^j + 1$. What are the values of $j$ such that $n$ divides $10^j + 1$? It is not difficult to prove that this happens exactly when $j = a \cdot (2i + 1)$ for $i = 0, 1, 2, \ldots $\ . Conversely, suppose that $n$ divides $10^j + 1$ for some positive integer $j$. Then there must be a smallest such positive integer $j$, which we denote by $\alpha$. Let $\kappa = 2 \cdot \alpha$. Then $n$ divides $(10^\alpha + 1) \cdot (10^\alpha - 1)$, that is, $n$ divides $10 ^ \kappa - 1$. If there were a smaller positive even integer $i$ such that $n$ divides $10^i - 1$, then the minimal property of $\alpha$ would be violated. If there were a smaller such integer $i$ that were odd, then the fact that $n$ has even order would be violated. Therefore, $\kappa$ must be the order of 10 ($mod$ $n$). Now by Theorem 1 it follows that $n$ has the 9's property, and we have derived the following old theorem of Sch\"{o}lmilch: \noindent %%%%%%%%%%%%%%%% theorem 5 {\bf Theorem 5 (Sch\"{o}lmilch [7])} \emph{Let $n$ be a positive integer relatively prime to 10. The number $n$ has the 9's property if and only if there exists some integer $j$ such that $n$ divides $10^j + 1$. } Theorem 5, like Theorem 1 above, is limited as a test to see if a number has the 9's property. Nevertheless, it will play an important role in the development of a more satisfactory characterization of those integers that have the 9's property. The first task is to show that if $n$ has the 9's property, then every power of $n$ also has the 9's property. \noindent {\bf Lemma 6} %%%%%%%%%%%%%% lemma 6 If $n$ is any number that has the 9's property, then $n^i$ also has the 9's property for all positive integers $i$. \noindent %%%%%%%%%%%%%% proof {\it Proof.} Let the order of $n$ be $k = 2 \cdot a$. Then $n$ divides $10^a + 1$. Moreover, for any odd positive integer $j$, $10^a +1$ divides the quantity $10^{ja} + 1$. In fact, we have \quad (i) \quad $10^{ja} + 1 = (10^a +1) \cdot (10^{(j-1)a} - 10^{(j-2)a} + 10^{(j-3)a} - \ldots - 10^{a} + 1)$ \noindent For simplicity, let the right hand factor on the right hand side of Equation (i) be denoted by $E(j)$. A direct calculation shows that for a given odd $j$, there exists a quantity $Q(j)$ such that \quad (ii) \qquad \qquad \qquad $E(j) = Q(j) \cdot(10^a + 1) + j$. \noindent Choose $j = 10^a + 1$ in Equation (ii). Then, for this value of $j$, Equation (ii) shows that $E(j)$ is divisible by $10^a + 1$. But then by Equation (i) we see that $(10^a + 1)^2$ divides $10^t + 1$ when we choose $t$ to be the integer $a \cdot (10^a + 1)$. But $n$ divides $10^a + 1$ whence $n^2$ divides $10^t +1$. Therefore, by Theorem 3 we see that $n^2$ has the 9's property. Applying this result to $n^2$ shows that $n^4$ has the 9's property and, by iteration we see that $n^q$ has the 9's property whenever $q$ is any power of 2. Given any integer $i$, there exists an integer $u$ that is a power of 2 with $ i \leq u$. Since $n^u$ divides $10^v + 1$ for some integer $v$ and $n^i$ divides $n^u$, necessarily $n^i$ also divides $10^v + 1$. It follows by Theorem 3 that $n^i$ has the 9's property, completing the proof. \hfill $\Box$ The integer $t$ in the proof of Lemma 6 is much larger than the smallest integer that would yield the desired result that $n^2$ has the 9's property. For example, if $n = 7$, then $a = 3$ and the proof produces the value 3003 for the integer $t$. That is, the square 49 of 7 divides $10^{3003} + 1$. But the order of 49 is 42, so 49 also divides $10^{21} + 1$. Lemma 6 will be used in the proof of Theorem 8 below, which characterizes those numbers $n$ that have the 9's property in terms of a certain relationship between the prime factors of $n$. What Lemma 6 essentially allows us to do is to concentrate on the relationship between prime factors of $n$ without having to be concerned with their multiplicities. The number 1507 does not have the 9's property. Since the order of 1507 is only 8, it is an easy example with which to work. An analysis of why 1507 fails to have the 9's property is instructive and motivates the proof of Theorem 8. We have $B(1507) = 00066357$, that is, the period of 1/1507 is 8. Therefore, by Theorem 1, 1507 has the 9's property if and only if 1507 divides 10001. It doesn't, of course, but why it doesn't is revealing. The prime factors of 1507 are 11 and 137. Now 11 divides $10^1 + 1$ and 137 divides $10^4 + 1$. Observe that 11 divides $10^u + 1$ for $u = 1, 3, 5, \ldots$, and that 137 divides $10^v + 1$ for $v = 4, 12, 20, \ldots$\ . The set of $u$'s and the set of $v$'s are disjoint. Therefore, whenever 11 divides a number $10^t + 1$, 137 cannot divide it, and vice versa. It follows that their product, 1507, can never divide a number of the form $10^t + 1$, so by Theorem 5 the number 1507 cannot have the 9's property. This single example actually captures the whole essence of the 9's property for an arbitrary integer $n$. We previously discussed the result contained in the following lemma, but we formally state it here since it is important in the proof of Theorem 8 below. %%%%%%%%%%%%%%% lemma 7 \noindent {\bf Lemma 7} Let $n$ be a positive integer and $k = 2 \cdot a$ be the order of 10($mod$ $n$). Then, $n$ divides $10^t + 1$ if, and only if, $t = a \cdot (2i + 1)$ for all $i = 0, 1, 2, \ldots$\ . We will now prove the second generalization of Midy's Theorem, an internal characterization of those integers that have the 9's property. %%%%%%%%%%% theorem 8 \noindent {\bf Theorem 8} \emph{Given a positive integer $n$, let the prime factors of $n$ be denoted by $p_i$ for $1 \leq i \leq r$. For each $i$, let $h(i)$ denote the order of 10 ($mod$ $p_i$). Then $n$ has the 9's property if, and only if, the following condition is satisfied:} \begin{quote} \# \quad There exists a positive integer $s$ such that for each integer $i$ with $1 \leq i \leq r$, $h(i) = 2^s \cdot q(i)$ where $q(i)$ is an odd integer. [The $q(i)$'s may be different for different $i$'s, but for each $i$ the factor $2^s$ is the same.] \end{quote} %%%%%%%%%%%%%proof \noindent {\it Proof.} Let $p$ denote any prime number that has the 9's property. Suppose that the order of 10 ($mod$ $p$) is equal to $2 \cdot j$, that is, the shortest period length in the decimal expansion of $1/p$ is $2 \cdot j$. Then, by Lemma 7, $p$ divides $10^k + 1$ precisely when $k$ is a positive integer of the form $k = (2 \cdot i - 1) \cdot j$ for $i = 1, 2, 3, \ldots$\ . To prove the `only if' part of the theorem, assume that Condition \# does not hold. One possibility is that $s = 0$ for some $i$ whence $h(i) = q(i)$, that is, $h(i)$ is odd. But then the prime factor $p_i$ does not have the 9's property. In this case $n$ cannot have the 9's property either. For if it did, then $n$ would divide some number $10^k + 1$. But then every prime factor of $n$ would also divide this number, and so every prime factor would also have the 9's property. On the other hand, suppose that \# fails to hold because the number $n$ has prime factors $p$ and $q$ such that the order of 10 ($mod$ $p$) is $2 \cdot (2^a \cdot u)$ and the order of 10 ($mod$ $q$) is $2 \cdot (2^b \cdot v)$, where $a$ and $b$ are non-negative integers that are not equal and $u$ and $v$ are odd integers. Suppose that $n$ does have the 9's property. Then $n$ must divide some number $10^m + 1$. Let $\alpha = 2^a \cdot u$. Then $p$ divides $10^\alpha + 1$, and $\alpha$ is the smallest such exponent for 10 for which this is true. Likewise, $q$ divides $10 ^\beta + 1$ where $\beta = 2^b \cdot v$, and $\beta$ is the smallest exponent for which this is true. But $p$ and $q$ both divide $10^m + 1$. Therefore, by Lemma 7, \[ m =(2^a \cdot u) \cdot (2x+1)\ \mbox{for some}\ x = 1,2,3,\ldots\ , \] \noindent and \[ m =(2^b \cdot v) \cdot (2y+1)\ \mbox{for some}\ y = 1,2,3,\ldots\ . \] \noindent Now $u$ and $v$ are both odd integers, and therefore the multiplicity of the prime number 2 in the factorization of $m$ must be the number $a$ by one of the indented equations above and must be the number $b$ by the other equation. But this is impossible since $a \neq b$. Thus, if Condition \# fails to hold, then $n$ cannot have the 9's property. To prove the `if' part of the theorem, assume that Condition \# holds. For each integer $i$ with $1 \leq i \leq r$, let $d(i) = h(i)/2$. Also, for each $i$ let $m(i)$ denote the multiplicity of the prime $p_i$ in the factorization of the number $n$, that is, the number of times that the prime occurs as a factor of $n$. From Lemma 6 we know that $p_i^{m(i)}$ has the 9's property. But from the proof of Lemma 6 we also know that $p_i^{m(i)}$ divides the number $10^{t(i)} + 1$ where the exponent $t(i)$ is an odd multiple of $d(i)$ for all elements $i$ in the set $\{1, 2, \ldots r\}$. By Condition \#, for each $i$ we have $d(i) = 2^{s-1} \cdot q(i)$. Now each number $q(i)$ is odd so the product $q$ of all the numbers $q(i)$ is also odd. Let $t$ denote the product of all the numbers $t(i)$ for $i$ in the set $\{1, 2, \ldots r\}$. Then $t \cdot q$ is an odd number that is a multiple of every $q(i)$ and every $t(i)$. Let $e = t \cdot q \cdot 2^{s-1}$. Then for every $i$ we have that $p_i ^{m(i)}$ is a divisor of $10^e + 1$. But the numbers $p_i ^{m(i)}$ are relatively prime to one another for different values of $i$ and so their product, namely $n$, is also a divisor of $10^e + 1$. It follows by Theorem 5 that $n$ has the 9's property, completing the proof. \hfill $\Box$ %%%%%%%%%% example 9 \noindent {\bf Example 9} The order of 10 ($mod$ 49) is $42 = 6 \cdot 7$. However, 49 does not have the 9's property[7]. Therefore, if $p$ is a prime greater than 5, $p^2$ does not necessarily have the 9's property with respect to all divisors $b>1$ of the order of 10 ($mod$ $p^2$), unlike the prime $p$. \vskip 20pt \noindent \section*{\normalsize References} %%%%%%%%%% references \footnotesize \begin{enumerate} \item L. E. Dickson, \emph {History of the Theory of Numbers}, Vol. 1, Chelsea Publishing Company, New York, 1952. \item Brian D. Ginsberg, \emph {Midy's (nearly) secret theorem - an extension after 165 years}, College Math. Journal 35 (2004), 26-30. \item Ankit Gupta and B. Sury, \emph {Decimal expansion of $1/p$ and subgroup sums}, Integers: Electronic Journal of Combinatorial Number Theory 5 (2005), \#A19. \item Ross Honsberger, \emph {Ingenuity in Mathematics}, Random House/Singer, New Mathematical Library, 1970. \item E. Midy,\renewcommand{\thefootnote}{\fnsymbol{footnote}} \footnote[1]{The author has not seen these works. These works and others pertaining to Midy's Theorem are cited in [1].} \emph{De quelques proprietes des nombres et des fractions decimals periodiques}, Nantes, (1836), 21 pages. \item Hans Rademacher and Otto Toeplitz, \emph{The Enjoyment of Mathematics}, Princeton University Press, Princeton, 1957. \item O. Sch\"{o}lmilch, {*}Zeitschrift Math. Phys., 25 (1880), p. 416. \end{enumerate} \end{document}