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

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.

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.

• This is great! I think a video could be very helpful, too. – Benjamin Dickman Sep 30 '18 at 14:51
• I have a question about the alignment in the last calculation. Shouldn't the 122 end below the last 2 in ...22222200? – Ben Blum-Smith Oct 1 '18 at 12:41
• @BenBlum-Smith — absolutely! I’ll fix that. Now corrected. All thanks to you – Lubin Oct 1 '18 at 13:53

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).

• Can you say more about what you mean by the parenthetical comment "analogous to our trick of getting an infinite string of nines so that they 'carry' in the real sense"...? Confused because in the $p$-adics, we are exploiting the fact that "carrying" happens "in the direction in which things get smaller," while in $\mathbb{R}$ "carrying" moves things from smaller to larger place values. I don't see the "carry" in $0.999...$ but interested to know what you mean. – Ben Blum-Smith Sep 30 '18 at 8:46
• @BenBlum-Smith My analogy is not great, and may even be bad, since the multiplication involves addition that, as you say, happens in the bigger direction, whereas, here we have terms crashing into each other and "carrying" into ($p$-adic) smallness. What I'm imagining is the commonality of pushing things off to an infinite place, whether a carrying that (not speaking rigorously) happens infinitely far to the right in the real case to make $0.999\ldots = 1$, or crashing terms into each other here so that they shrink $p$-adically towards $0$. In the real case, we get more $9$s hence close... – Benjamin Dickman Sep 30 '18 at 15:18
• ...the distance to $1$. In the $p$-adic case, we push off higher powers of $p$ hence close the distance to our dividend $p$-adically. (I was under the impression that my carrying analogy was not helpful and that there was a fast algorithm for computing this quotient - I am glad to see your comment and Lubin's answer today!) – Benjamin Dickman Sep 30 '18 at 15:20
• Thank you, this is clarifying! Maybe the $p$-adic process and the $0.999.... = 1$ are kind of "dual to each other"... – Ben Blum-Smith Oct 1 '18 at 12:36
• @BenBlum-Smith Almost included the word "dual" in my response! Yes, surely there is a discussion somewhere of this duality... – Benjamin Dickman Oct 1 '18 at 23:25