Period of the $p$-adic expansion of a rational number

Question

I have a problem I have been very stuck on.

Show that if $p \nmid n$, then the length of the period [of the expansion of $\frac{a}{n} \in \mathbb Q$] divides $e$, where $e$ is the least positive integer such that $p^e \equiv 1 \pmod n$.

I went to my professor for a hint, and his hint was to write $\frac{a}{n}$ as $$\frac{a k}{p^e - 1},$$ for some $k \in \mathbb Z$, then multiply both sides of the $p$-adic expansion $$\frac{a}{n} = \sum_{i = 0}^\infty q_i p^i$$ by $p^e - 1$ and group common powers of $p$. Thus, if $a k < 0$ (I imagine there is a similar argument for $a k \geq 0$ if I can make this one work), $$-a k = \sum_{i = 0}^{e - 1}q_i p^i + \sum_{i = e}^\infty (q_i - q_{i - e}) p^i,$$ and so if $q_i \geq q_{i - e}$ for all $i \geq e$, then this is the $p$-adic expansion of the non-negative integer $-a k$, which we know to be finite. Thus, $q_i = q_{i - e}$ for sufficiently large $i$, and I'm pretty sure I can show that the period divides $e$ from there. However, I can't figure out the details if there are any $i \geq e$ such that $q_i < q_{i - e}$.

Answer 1

Sorry for abandoning this question for a while, but the semester was keeping me busy. My professor eventually answered the question during an exam review, so I'm going to share his answer, which ended up being similar to reuns's and not using the hint he gave (apparently the source he got the problem from had a mistake which made the problem seem easier than it was).

First, we prove the result for $\frac{b}{n} \in [-1, 0)$. Let $$B = \frac{b (1 - p^e)}{n} \in \mathbb Z$$ and note that $0 < B \leq p^e - 1$. The $p$-adic expansion of $B$ is then $$B = \sum_{k = 0}^{e - 1}B_k p^k,$$ and so the $p$-adic expandsion of $\frac{b}{n}$ is $$\frac{b}{n} = \frac{B}{1 - p^e} = \sum_{j = 0}^\infty\sum_{k = 0}^{e - 1}B_k p^{k - j e},$$ which is periodic with period $e$.

Then, with $S_e$ as defined in reuns's answer, we show that if $x \in S_e$, then $x + m \in S_e$ for any $m \in \mathbb Z$. To show this, we show that if $x \in S_e$, then $x + 1, x - 1 \in S_e$, which we in turn show by showing that if $x \in S_e$, then $-x, -1 - x \in S_e$. Suppose $x \in S_e$ and the $p$-adic expansion of $x$ is $$x = \sum_{k = d}^\infty x_k p^k, \text{ with } x_d \neq 0.$$ Then \begin{align} -x &= p^d + (-1) p^d - x\\ &= p^d + \sum_{k = d}^\infty(p - 1) p^k - \sum_{k = d}^\infty x_k p^k\\ &= (p - x_d) p^d + \sum_{k = d + 1}^\infty(p - 1 - x_k) p^k\\ &\in S_e \end{align} and $$-1 - x = \sum_{k = 0}^{d - 1}(p - 1) p^k + \sum_{k = d}^\infty(p - 1 - x_k) p^k \in S_e$$ since $p - x_d, p - 1 - x_k \in \{0, \ldots, p - 1\}$ for all $k \geq d + 1$.

Finally, since $\frac{a}{n} = m + \frac{b}{n}$ for some $m \in \mathbb Z$ and some $\frac{b}{n} \in [-1, 0)$, this completes the proof.

Answer 2

Let $$S_e=\{ \sum_{m\ge 0} b_m p^m, b_m\in 0\ldots p-1,b_{m+e}=b_m \text{ for m large enough}\}$$

• Show that for $B\in S_e$ then $B+\frac1{1-p^e}\in S_e$.

• Whence $\frac{k}{1-p^e}+l\in S_e$ for all $k\in \Bbb{Z}_{\ge 0},l\in \Bbb{Z}$

• Show that for $B\in S_e$, $\frac1{1-p^e}-B\in S_e$.

Whence $\frac{a}{n}=\frac{a k}{p^e - 1}\in S_e$, your $q_i$ sequence is $e$-periodic for $i$ large enough, which implies that its least period divides $e$.

Answer 3

Maybe I am overlooking something, but:

Let's say in your expansion $\displaystyle \sum_{i=0}^\infty q_i p^i$ you choose all $q_i \in \{0,1, ..., p-1\}$. If I understand you correctly, you assume that $-ak \in \mathbb Z_{\ge 0}$, so it has a finite $p$-adic expansion $\sum_{i=0}^m r_i p^i$ ($r_i \in \{0,1, ..., p-1\}$), w.l.o.g. $m \ge e$. Then

$$0 = \sum_{i = 0}^{e - 1}(q_i-r_i) p^i + \sum_{i = e}^m(q_i - q_{i - e}-r_i) p^i + \sum_{i = m+1}^\infty(q_i - q_{i - e})p^i$$

Admittedly the "finite part" $\sum_{i = 0}^{e - 1}(q_i-r_i) p^i + \sum_{i = e}^m(q_i - q_{i - e}-r_i) p^i$ is not in "standard" $p$-adic expansion, and the coefficents might introduce some "carries". I.e. I assume you are worried that this might be something like $\sum_{i=0}^\infty a_i p^i$ with $a_0= p$, $a_1=a_2=... =p-1$ and you cannot conclude about the $q_i - q_{i-e}$ -- correct?

If so, good point. But let's look more closely. Because all $q_i$ and $r_i$ were taken out of $\{0,1, ..., p-1\}$, we actually have $ p \vert (q_i - r_{i}) \Leftrightarrow q_i = r_i$, and also $ p \vert (q_i - q_{i-e}) \Leftrightarrow q_i = q_{i-e}$. The first relation tells us (by induction) that up to index $e-1$, there are no "carries", and all $q_i-r_i$ are zero.

Now $q_e-q_0-r_e \in \{-2p+2, -2p+3, ...,-p-1, -p, -p+1, ..., 0, ..., p-1\}$.

So for $q_e-q_0-r_e$ to be divisible by $p$ (which it must be so the sum is $0$), it can happen (beside $q_e-q_0-r_e =0$) that $q_e-q_0-r_e = -p$, in which case we would get an extra carry of $-1$. In both cases, note that the term we get at $i=e+1$ after clearing the term at index $e$ is either $q_e-q_0-r_e$ or $q_e-q_0-r_e-1$, which "at worst" is in $\{-2p+\color{red}{1}, -2p+2, ..., p-1\}$, and again the worst that can happen is a carry of $-1$. This iterates all the way to $i=m$.

So at $i=m+1$ we have to look at either $q_i - q_{i-e}$ or $q_i -q_{i-e}-1$. If we're in the first case, there are no carries, and then inductively there will also be no ones ever after, meaning that indeed $q_j = q_{j-e}$ from now on.

Actually, note that as soon as for any index $j$ after $m+1$ there is no carry, then there cannot be a carry ever after, so we're done.

In the second case, we can get a carry, but if and only if $q_i = 0$ and $q_{i-e} = p-1$; and this causes another carry in the next place. Again, to get another carry there, we need $q_{i+1}=0$ and $q_{i+1-e}=p-1$. Iterating this $e$ times, we arrive at $q_{i+e}=0$ and $q_{i+e-e}=p-1$ which contradicts our established $q_i=0$.

The upshot being that "at worst", the carries "wear out" after index $m+1+e$, after which you still have infinitely to go and be periodic.

Added in response to comment: The above proof ends up showing that $q_i = r_i$ for all $i \le e-1$, and also that $q_i = q_{i-e}$ eventually, namely for $i \ge m+e+1$. I do not claim that all the "middle terms" $q_i-q_{i-e}-r_i$ are zero, nor that $q_i\stackrel{?}=q_{i-e}$ right away from $i=m+1$. Indeed, the whole point of us going through all this is that in general, those terms might not be zero. For concrete examples, look at:

Example 1: $a=1-2p, n=p-1$. With $k=1$ we have a period $e=1$, get $r_0=p-1, r_1=1$ and $m=1$, on the other hand $q_0=p-1, q_1=0, q_2=q_3=...=1$. So

• $q_0-r_0=0$ but
• $q_1-q_0-r_1 = \color{red}{-p}$ and
• $q_2-q_1=\color{red}{1}$ (which kills the carry $\color{blue}{-1}$ from before), only then
• $q_3-q_2=0$ and likewise $q_i - q_{i-1}=0$ for all $i \ge 3$.

Example 2: $a=1-2p^2, n=p^2-1$. With $k=1$ we have a period $e=2$, get $r_0=r_1=p-1, r_2=1$ and $m=2$, on the other hand $q_0=q_1=p-1, q_2=0, q_3=q_5=q_7=...=0, q_4=q_6=q_8=q_{10}=...=1$. So

• $q_0-r_0=0$ and $q_1-r_1=0$ but
• $q_2-q_0-r_2 = \color{red}{-p}$ as well as
• $q_3-q_1=\color{red}{1-p}$ (which with the carry $\color{blue}{-1}$ becomes $\color{red}{-p}$, making another carry) and
• $q_4-q_2=\color{red}{1}$ (which now gets killed by the carry $\color{blue}{-1}$ from the previous step), only then
• $q_5-q_3=0$ and likewise $q_i - q_{i-2}=0$ for all $i \ge 5$.

Exercise: Find more examples.