Computing quotient by dividing formally in $p$-adic number system

Question

From Gouvea's p-adic Numbers:

To pass from positive integers to positive rationals, we simply do exactly as in the other case, that is we expand both numerator and denominator in powers of p, and then divide formally. The only thing one has to be careful with is that one may have to 'carry.' The sum of two of our $a_i,$ for example, may be larger than p, and one has to do the obvious thing. It's probably easier to go straight to an example.

Here is his example:

Let's take $p = 3$ and consider the rational number 24/17. Then we have

$ a = 24 = 0 + 2 \times 3 + 1 \times 3^2 = 2p + 2p^2$

and

$ b = 17 = 2 + 2 \times 3 + 1 \times 3^2 = 2+ 2p + p^2$

(Though of course $p = 3$ it's probably less confusing to write $p$, because one is less tempted to "add it all up." The point is to operate formally with our expansions.) Then we get

$\frac{a}{b} = \frac{24}{17} = \frac{2p + 2p^2}{2 + 2p + p^2} = p + p^3 + 2p^ 5 + p^7 + p^8 + 2p^9 + ...$

I'm having trouble understanding what this formal division involves, and my attempt to perform conventional polynomial division hasn't yielded this series.

I had more success when I rewrote the numerator and denominator ($\frac{2p + 2p^2}{2 + 2p + p^2} = \frac{p^3-p}{2p^2 -1}$) and then performed something like conventional polynomial division (dividing the lowest power into the lower power). This is fine, but I can't figure out why this would work, or how I should "divide formally" in general.

Any help, please?

Answer 1

My method is much more direct, and to my mind, much more intuitive than that of @BenjaminDickman. Conceptually, it’s exactly like long division of decimally expressed reals, as you (one hopes) learned in elementary school. Unfortunately, it proceeds right to left, assuming that you write your $24_{10}$ as $220_3$ and your $17_{10}$ as $122_3$. I think that all you need to know is that $-1$ is written $3$-adically as $\cdots22222_3$. I’ll drop the subscripts from here on, but in case you doubt the infinite expansion of $-1$, notice that it represents $\sum_{n=0}^\infty2\cdot3^n$, a geometric series with initial term $a=2$ and ratio $r=3$, which is three-adically smaller than $1$, so that the series is convergent. And the value is $a/(1-r)=2/(-2)=-1$.

Step 1. Write the dividend on the left, the divisor on the right, leaving space above for the quotient. See in this case that the first digit is $0$, the second is $1$, so you will want to subtract $10\times122$ from the dividend. \begin{matrix} \text{(quotient)}&&&&&&1&0\\ &0&0&0&0&2&2&0&\bigl(&1&2&2\\ &(-)&&&1&2&2&0 \end{matrix}
Step2. Do the subtraction \begin{matrix} \text{(quotient)}&&&&?&0&1&0\\ &0&0&0&0&2&2&0&\bigl(&1&2&2\\ &(-)&&&1&2&2&0\\ &2&2&2&2&0&0 \end{matrix}
Here, you got a free digit of zero in the difference, so put a zero upstairs and ask what the next digit should be. You’re asking what the first digit of $\cdots2222/122$ should be; clearly $1$. So in the next step you’ll subtract $1\times122$ from the lowest line, but properly aligned. I’ll perform the subtraction, too: \begin{matrix} \text{(quotient)}&&&&&&1&0&1&0\\ &&&0&0&0&0&2&2&0&\bigl(&1&2&2\\ (-)&&&&&&1&2&2&0\\ &2&2&2&2&2&2&0&0\\ (-)&&&&1&2&2\\ &2&2&2&1&0&0 \end{matrix}
I won’t go any further, but you see that the next nonzero digit is going to be $2$. You need to do the multiplication, $2\times122=1021\>$, and continue this way. Unfortunately, this method is a natural for demonstration on the blackboard, but the static nature of the written (printed) word is almost completely unsuitable. I keep telling myself to make a video, but laziness seems to be holding me back. Anyway, my machine tells me that the quotient is $\cdots12\,02\,12\,21\,10\,20\,10\,10;$ Our rational number must have a periodic three-adic expansion, but since $\langle3\rangle$ is of multiplicative order $16$ in $\Bbb Z/17\Bbb Z$, the period of that expansion must be $16$, not so easily observed.

Answer 2

I believe there is a speedy way to do this algorithmically, but as no one has yet responded:

If I am working with the $p$-adic numbers for $p=3$ and trying to compute a formal quotient, then I would proceed as follows. First, I would rewrite the numerator and denominator as is done in the OP. Next, I would try to find the quotient by considering what can be multiplied by the denominator so as to obtain the numerator. In this particular case, that means multiplying $2+2p+p^2$ by something to get $2p + 2p^2$.

The unorthodox component here is, to my mind, a bit similar to computing the formal quotient in $\mathbb{R}$ of $1$ divided by $1/3$, where each is written in its decimal form; that is, finding a real number that can be multiplied by $0.333\ldots$ and yield $1$. Without a fair bit of familiarity with standard multiplication in the real number system, it might seem far-fetched to use $3$ and observe the product thereby obtained is $0.999\ldots = 1$, where that final equality is magical, obvious, or deep - depending on one's perspective and mood.

As to the example at hand:

We begin by multiplying $2 + 2p + p^2$ by $p$, which yields $2p + 2p^2 + p^3$. We want $2p + 2p^2$, and so we will need to pick a next term that adds on another $2p^3$, for this will result in $p^3 + 2p^3 = 3p^3 = p^4$, where we are remembering that $p$ is not-so-secretly $3$, and where the goal is going to be pushing all the rest of the terms into higher and higher powers of $p$ so that they vanish $p$-adically through what the author calls "carrying" (and analogous to our trick of getting an infinite string of nines so that they "carry" in the real case).

And so the next term in the formal quotient is $p^3$, which thereby yields:

$$2p + 2p^2 + p^3 + 2p^3 + 2p^4 + p^5 = 2p + 2p^2 + 3p^3 + 2p^4 + p^5 =$$

$$2p + 2p^2 + p^4 + 2p^4 + p^5 = 2p + 2p^2 + 3p^4 + p^5 = 2p + 2p^2 + p^5 + p^5 = $$

$$2p + 2p^2 + 2p^5$$

At long last, we have arrived at a similar juncture: We successfully maintained the $2p + 2p^2$ that we wanted, but now we are left with an undesirable $2p^5$. And so we resume matters by shrinking this term $p$-adically; in particular, our next term will be whatever we can multiply by the smallest degree term in the divisor (here, $2$) to obtain a coefficient for $p^5$ that is a multiple of $p$ (here, a multiple of $3$) so as to allow this process to continue on. With $2p^5$ we will be adding on $4p^5$ for a total of $6p^5 = 2 \cdot 3 p^5 = 2p^6$, and so on indefinitely.

In this way, we find the quotient begins: $p + p^3 + 2p^5 + \cdots$ (and could continue by hand, if desired).

Answer 3

My method uses the "formal division" in the good old-fashined basis $p$ (which many of us are familiar with), then converts it to a p-adic number. It might not be what you asked, but it is an alternative that I hope helps in your goals.

Step 1 Compute $1/17_3 = 0.(0011202122110201)_3$ as per the Euclidean algorithm

The number in brackets is the period. Note it has 16 digits.

Step 2 Compute the (p-1)-complement of each digit in the period. That is, replace each digit $d$ by $2-d$

$0011202122110201 \rightarrow 2211020100112021$

Step 3 Form the 3-adic inverse of 1/17. Using the result from previous step: $(2211020100112021) +1 = \sum_{n=0}^\infty 2211020100112021*10_3^{16 n} +1$

The number in brackets repeats indefinitely (to the left)

Step 4 Multiply by $24 == 220_3$

$24/17$ in 3-adic is thus $ \sum_{n=0}^\infty 211¦1202122110200020*10_3^{16 n} +220 = (1202122110201001) + 2$

The "¦" visually aids in separating the number at the 16-th digit

In the last step I simplified the resulting p-adic number. The repeating part has 19 digits. I removed the $211$ on the left by adding it to the right 16 digits $1202122110200020_3 + 211_3 = 1202122110201001_3$. I have to undo this offset at the very first iteration, when $n=0$, then $220_3 - 211_3 = 2_3$