# How to define the addition and multiplication of p-adic integers as infinite formal sums?

On page 269 in Dummit&Foote's Abstract Algebra, 3rd edition, it gives that every element in $$\mathbb{Z}_p=\varprojlim\mathbb{Z}/p^i\mathbb{Z}$$ can be written uniquely as an infinite formal sum $$\sum^{\infty}_{k=0}b_kp^k$$ with each $$b_k\in[0,p-1]$$ . But I was confused about how to define the addition and multiplication on $$\sum^{\infty}_{k=0}b_kp^k$$ such that it could keep the structure of rings. The following is my attempt: $$\begin{cases} \displaystyle\left(\sum_{k=0}^{\infty}b_kp^k\right)+\left(\sum_{k=0}^{\infty}c_kp^k\right)=\sum_{k=0}^{\infty}\big(b_k+c_k\ \ (\mathrm{mod}\ \ p)\big)p^k \\\displaystyle\left(\sum_{k=0}^{\infty}b_kp^k\right)\cdot\left(\sum_{k=0}^{\infty}c_kp^k\right)=\sum_{k=0}^{\infty}\big(b_k\cdot c_k\ \ (\mathrm{mod}\ \ p)\big)p^k \end{cases}$$ where $$\big(b_k+c_k\ \ (\mathrm{mod}\ \ p)\big)$$ and $$\big(b_k\cdot c_k\ \ (\mathrm{mod}\ \ p)\big)$$ are in $$[0,p-1]$$ . But I am not sure that whether it is true.

Update on 2024.03.29: follow the hints from the comments I try to define new operations such that they hold for ordinary integers: $$\begin{cases} \displaystyle\left(\sum_{k=0}^{\infty}b_kp^k\right)+\left(\sum_{k=0}^{\infty}c_kp^k\right)=\sum_{k=0}^{\infty}\big(b_k+c_k\big)p^k \\\displaystyle\left(\sum_{k=0}^{\infty}b_kp^k\right)\cdot\left(\sum_{k=0}^{\infty}c_kp^k\right)=\sum_{k=0}^{\infty}\left(\sum_{n=0}^kb_nc_{k-n}\right)p^k \end{cases}$$ More exactly, for the addition, we define the following maps: \begin{cases} \pi_p:[0,2p-1]\to[0,p-1] \\\pi_p:d\mapsto\begin{cases}\begin{aligned}&d\ ,\hspace{-15pt}&d if $$\left(\sum_{k=0}^{\infty}b_kp^k\right)+\left(\sum_{k=0}^{\infty}c_kp^k\right)=\sum_{k=0}^{\infty}a_kp^k$$ , then for $$k\geqslant1$$ , $$a_k=\pi_p\big(b_k+c_k+\pi_2(b_{k-1}+c_{k-1})\big)\ ,$$ such expression for $$a_k$$ keeps $$a_k$$ in the interval $$[0,p-1]$$ .

But for the multiplication I think it is a little harder to find a universal way to restrict the coefficient $$a_k$$ of $$p^k$$ for the product $$\left(\sum_{k=0}^{\infty}b_kp^k\right)\cdot\left(\sum_{k=0}^{\infty}c_kp^k\right)=\sum_{k=0}^{\infty}a_kp^k$$ to be in $$[0,p-1]$$ as desired.

Under such operations, it is easy to check that $$1=1\cdot p^0+\sum_{k=1}^{\infty}0\cdot p^k$$ and $$0=\sum_{k=0}^{\infty}0\cdot p^k$$ is the multiplicative identity and the zero element of $$\mathbb{Z}_p$$ resp.

• Your formulas already do not work for finite sums (ie for ordinary integers). Commented Mar 27 at 15:50
• To quote Hendrik Lenstra, "expansion in $\mathbb{Z}_p$ is just like decimal expansion on $\mathbb{Z}$, except that $10$ is not a prime and the expansion goes the wrong way." Think about how you would add two decimal numbers $0.a_1a_2a_3\ldots$ and $0.b_1b_2b_3\ldots$. You need to add carries. Commented Mar 27 at 19:03
• Note that your attempt at addition is wrong only because you didn't take carries into account. For multiplication, though, even after you take carries into account, your attempt still won't work, even for ordinary integers. Commented Mar 27 at 19:56
• Note that in base 10, you cannot describe the $k$th digit of a sum solely in terms of the $k$th and $(k-1)$st digits of the summands. You actually have to do a recursive definition, where you define a result and a carry for the $k$th term, and then use those to define a result and a carry for the $k+1$st term; it is a recursive definition, which is reflected in how we add numbers with pencil-and-paper: by starting on the left and then doing one column at a time, with a carry determined by the previous column. Commented Mar 28 at 16:29
• "Base 10" is how we usually write numbers. $p$-adic numbers take a "base $p$" expansion but allow for "infinite expansions" (that is, they do not require that the $b_k$ be zero for sufficiently large $k$). You can do the exact same construction to get "$10$-adic numbers", but they would not be an integral domain, since for example the element $\sum 2\times 10^k$ multiplied by the element $\sum 5\times 10^k$ would give the result $\sum 0\times 10^k$. Commented Mar 28 at 16:50

It would not be easy to produce simple formulas. Roughly speaking, the connection between arithmetic and bitwise operations is complicated as seen from computer science. Had there been, math education in elementary school can be significantly simplified, since the formula must be able to re-produce the results for natural numbers. However, there is a very concrete way to understand and perform the operations.

Given two positive integers $$a=\sum_{i=0}^n a_i l^i$$ and $$b=\sum_{i=0}^n b_i l^i$$ written in $$l$$-adic manner where $$l$$ doesn't even have to be a prime. By the same way we perform addition and multiplication for $$l=10$$ in real life and scientific investigations, we can perform the operation for general $$l$$.

Here is the key insight: There is nothing that stopped us from defining $$a=\sum_{i=0}^\infty a_i l^i$$ and $$b=\sum_{i=0}^\infty b_i l^i$$ formally (i.e. as two infinite sequences $$(a_1, a_2, \cdots)$$ and $$(b_1, b_2, \cdots)$$), and their additions and multiplications as above. It's just that you may never finish the calculation but you can always produce the next symbol if requested. In particular, if we stopped at $$i=n$$, then we are essentially dropping everything that is a multiple of $$l^n$$, hence the calculation is really performed as in $$\mathbb Z/l^n\mathbb Z$$.

For example, in the case of $$l=2$$, we can define the sum of $$a=\sum_{i=0}^\infty 2^n = 111111\cdots$$ (well we usually write $$\cdots 11111$$ when the string is finite with least significant bit at tail, but this is not important) and $$b=1$$, note that $$1+1$$ is $$0$$ with $$1$$ as the carry, hence by performing the usual arithmetic in base $$2$$ indefinitely, we can show $$a+b=0000\cdots$$, that is $$a=-1$$ in the ring. This explains why in the two's complement represetation, $$-1$$ is always full of $$1$$'s, no matter how many bits are allowed, because $$111\cdots1$$ is an approximation of $$-1$$ (and precisely $$-1$$ if infinitely extended).

Then why $$l$$ has to be a prime? It doesn't have to be. That is you can always define the ring $$\varprojlim \mathbb Z/l^n\mathbb Z$$ as above, a concrete hands-on approach without abstract algebra, but only when $$l$$ is a prime power, this ring is an integral domain.

• "only when $l$ is a prime number, this ring is an integral domain": or when it is a prime power.
– KCd
Commented Mar 28 at 22:28
• @DianWei The style of the question seems to be about algorithms. For a more abstract point of view, Witt vectors provides a precise way to construct $\mathbb Z_p$ from only $\mathbb F_p$, not $\mathbb Z/p^n\mathbb Z$, where a series of polynomials are systematically constructed to handle the "carry" problem. Those Witt polynomials are probably the closest to what you want. Commented Mar 29 at 5:18
• Great! The link states that "It is hard to provide an algebraic expression for addition and multiplication using this representation, as one faces the problem of carrying between digits." for the $p$-adic expandsion restricted each coeffient to $[0,p-1]$ , which is just one way to pick the representatives. Thanks for your leading. Commented Mar 29 at 5:44
• The inverse limit of all $\mathbf Z/(p^k)^n\mathbf Z$ as $n$ varies (fixing $k$) is just $\mathbf Z_p$ in disguise: imagine taking the inverse limit of all $\mathbf Z/p^m\mathbf Z$ for $m \geq 1$ and only keeping track of components where $m$ is divisible by $k$. That gives you a map from $\mathbf Z_p$ to the inverse limit of all $\mathbf Z/(p^k)^n\mathbf Z$. To go the other way, just fill in the missing quotient groups because when you know what is happening in any $\mathbf Z/p^{nk}\mathbf Z$ you can reduce to get consistent numbers to put into $\mathbf Z/p^m\mathbf Z$ for all $m \leq nk$.
– KCd
Commented Mar 30 at 15:30
• If you want to directly show the inverse limit of all $\mathbf Z/(p^k)^n\mathbf Z$ (as $n$ varies, fixing $k$) is a domain, consider that when two numbers in $\mathbf Z/p^{nk}\mathbf Z$ have a product equal to $0$, at least one of the numbers is highly divisible by $p$ (at least by around $p^{nk/2}$). And remember you are working in an inverse limit. No $\mathbf Z/p^{nk}\mathbf Z$ is a domain when $k\geq 2$, but the inverse limit is not that. It might be easier to show two nonzero elements in the inverse limit have a nonzero product: think about $p$-power divisibility in a nonzero element.
– KCd
Commented Mar 30 at 15:36

You basically need to do the definition recursively rather than attempt to find a closed formula for the $$k$$th "digit" that does not depend on all previous digits.

Let $$\displaystyle a=\sum_{i=0}^{\infty}a_ip^i$$ and $$\displaystyle b=\sum_{i=0}^{\infty}b_ip^i$$, we let $$a+b=\sum_{i=0}^{\infty}s_ip^i\qquad\text{and}\qquad a\times b = \sum_{i=0}^{\infty} m_ip^i,$$ and define the digits and carries recursively as follows. For the sum, we define the summand digits $$s_j$$ and the carries $$c_j$$ by:

1. Define the $$0$$th digit of the sum $$s_0 = a_0+b_0\bmod p$$ (the remainder when dividing by $$p$$), and the first carry by $$c_1=\left\{\begin{array}{ll} 0&\text{if }a_0+b_0\lt p,\\ 1 &\text{if }a_0+b_0\geq p. \end{array}\right.$$
2. Assuming you have defined the $$k$$th digit of the sum $$s_k$$ and the $$(k+1)$$st carry $$c_{k+1}$$, define $$s_{k+1}=a_{k+1}+b_{k+1}+c_{k+1}\bmod p$$, and $$c_{k+2} = \left\{\begin{array}{ll} 0&\text{if }a_{k+1}+b_{k+1}+c_{k+1}\lt p,\\ 1 &\text{if }a_{k+1}+b_{k+1}+c_{k+1}\geq p. \end{array}\right.$$

Note that since $$0\leq a_k,b_k\lt p$$, then $$a_k+b_k\leq 2p-2$$, so $$a_k+b_k+c_k\lt 2p$$. So when adding two $$p$$-adic numbers, you never have more than a $$1$$ as a carry.

We define the digits $$m_i$$ and the carries $$c_i$$ also recursively, as follows:

1. We write $$a_0b_0 = qp + r$$ with $$0\leq r\lt p$$. Then let $$m_0=r$$ and $$c_1=q$$. Note that $$q\lt p$$.
2. Assuming we know $$m_k$$ and $$c_{k+1}$$, write $$a_{k+1}b_0 + a_{k+1}b_1+\cdots + a_0b_{k+1} + c_{k+1} = qp+r,\quad 0\leq r\lt p.$$ Define $$m_{k+1}=r$$ and $$c_{k+2}=q$$.

Note that in this case, the carry can be large (in fact, it may be larger than $$p^{k+2}$$). Namely, we have $$0 \leq a_nb_0+\cdots + a_0b_n \leq n(p-1)^2,$$ so if we write $$n=qp+r$$ with $$0\leq r\lt p$$, then just this computation may yield a carry as large as $$n(p-2)+q$$.

• Thanks for your advice, I have already given up the idea to find a closed formula, since it depends on all previous digits and this is hard to deal with. There is a typo in "Note that since $0\leq a_k,b_k<p$ , then $a_k+b_k\leq p-2$" , it must be $2p-2$ instead of $p-2$ . Commented Mar 29 at 5:53
• @DianWei Thank you for pointing out the type; I've corrected it now. Commented Mar 29 at 17:02

Thanks for the help given by the warm-hearted friends, I give up the idea of finding a non-recursive formula for each coefficient $$a_k$$ in either $$\left(\sum_{k=0}^{\infty}b_kp^k\right)+\left(\sum_{k=0}^{\infty}c_kp^k\right)=\sum_{k=0}^{\infty}a_kp^k$$ or $$\left(\sum_{k=0}^{\infty}b_kp^k\right)\cdot\left(\sum_{k=0}^{\infty}c_kp^k\right)=\sum_{k=0}^{\infty}a_kp^k$$ . And the operations defined recursively are given by Arturo Magidin in the answer: define the digits and carries recursively .

In the following, I will provide my new operations based on the connection between the two representations (formal power series and infinite direct product) of $$p$$-adic integers.

Let $$\sum_{k=0}^{\infty}b_kp^k,\sum_{k=0}^{\infty}c_kp^k\in\mathbb{Z}_p$$ , then there are corresponding elements $$b,c$$ in $$\varprojlim\mathbb{Z}/p^i\mathbb{Z}\subseteq\prod_{i=1}^{\infty}\mathbb{Z}/p^i\mathbb{Z}$$ for them respectively.

Note first that the finite sum $$\sum_{k=0}^{j-1}b_kp^k$$ is in the interval $$\left[\sum_{k=0}^{j-1}0\cdot p^k\ ,\ \sum_{k=0}^{j-1}(p-1)p^k\right]=[0,p^j-1]$$ , then the natural projection $$\mu_{ji}$$ from the $$j$$-th to the $$i$$-th component of $$\varprojlim\mathbb{Z}/p^i\mathbb{Z}$$ is: \begin{aligned} \mu_{ji}\left(\sum_{k=0}^{\infty}b_kp^k\ \ \mathrm{mod}\ p^j\right)&=\sum_{k=0}^{\infty}b_kp^k\ \ \mathrm{mod}\ p^i \\\mu_{ji}\left(\sum_{k=0}^{j-1}b_kp^k\right)&=\sum_{k=0}^{i-1}b_kp^k\ , \end{aligned} this gives rise to $$b=\left(\sum_{k=0}^{{\color{red}{0}}}b_kp^k\ ,\ \sum_{k=0}^{{\color{red}{1}}}b_kp^k\ ,\ \cdots\right)\in\varprojlim\mathbb{Z}/p^i\mathbb{Z}\subseteq\prod_{i=1}^{\infty}\mathbb{Z}/p^i\mathbb{Z}\ .$$ Then we use the following lemma: for a inverse limit $$\varprojlim A_i$$ , if all $$A_i$$ are commutative rings with $$1$$ and all maps $$\mu_{ji}:A_j\to A_i$$ are ring homomorphisms, then $$\varprojlim A_i$$ is also a commutative ring with $$1$$ , and the addition and multiplication of $$\varprojlim A_i$$ are defined by component-wise addition and multiplication, i.e., $$(x_1,x_2,\cdots)+(y_1,y_2,\cdots)=(x_1+y_1,x_2+y_2,\cdots)$$ and $$(x_1,x_2,\cdots)\cdot(y_1,y_2,\cdots)=(x_1y_1,x_2y_2,\cdots)$$ .

Since $$\varprojlim\mathbb{Z}/p^i\mathbb{Z}$$ satisfies all of the hypotheses in the lemma, it possesses the properties as stated above, namely we can define the addition and multiplication component-wisely: \begin{cases} \begin{aligned} &\left(\sum_{k=0}^{\infty}b_kp^k\right)+\left(\sum_{k=0}^{\infty}c_kp^k\right) \\=&\left(\sum_{k=0}^{{\color{red}{0}}}b_kp^k\ ,\ \sum_{k=0}^{{\color{red}{1}}}b_kp^k\ ,\ \cdots\right)+\left(\sum_{k=0}^{{\color{red}{0}}}c_kp^k\ ,\ \sum_{k=0}^{{\color{red}{1}}}c_kp^k\ ,\ \cdots\right) \\=&\left(\sum_{k=0}^{{\color{red}{0}}}b_kp^k+\sum_{k=0}^{{\color{red}{0}}}c_kp^k\ ,\ \sum_{k=0}^{{\color{red}{1}}}b_kp^k+\sum_{k=0}^{{\color{red}{1}}}c_kp^k\ ,\ \cdots\right) \\=&\left(\sum_{k=0}^{{\color{red}{0}}}(b_k+c_k)p^k\ ,\ \sum_{k=0}^{{\color{red}{1}}}(b_k+c_k)p^k\ ,\ \cdots\right) \\=&\left<\sum^{i-1}_{k=0}(b_k+c_k)p^k\ \ \big(\mathrm{mod}\ p^i\big)\right>_{i\in\mathbb{Z}_{\geqslant1}} \end{aligned} \\\\ \begin{aligned} &\left(\sum_{k=0}^{\infty}b_kp^k\right)\cdot\left(\sum_{k=0}^{\infty}c_kp^k\right) \\=&\left(\sum_{k=0}^{{\color{red}{0}}}b_kp^k\ ,\ \sum_{k=0}^{{\color{red}{1}}}b_kp^k\ ,\ \cdots\right)\cdot\left(\sum_{k=0}^{{\color{red}{0}}}c_kp^k\ ,\ \sum_{k=0}^{{\color{red}{1}}}c_kp^k\ ,\ \cdots\right) \\=&\left(\left(\sum_{k=0}^{{\color{red}{0}}}b_kp^k\right)\cdot\left(\sum_{k=0}^{{\color{red}{0}}}c_kp^k\right)\ ,\ \left(\sum_{k=0}^{{\color{red}{1}}}b_kp^k\right)\cdot\left(\sum_{k=0}^{{\color{red}{1}}}c_kp^k\right)\ ,\ \cdots\right) \\=&\left<\left(\sum_{k=0}^{i-1}b_kp^k\right)\cdot\left(\sum_{k=0}^{i-1}c_kp^k\right)\ \ \big(\mathrm{mod}\ p^i\big)\right>_{i\in\mathbb{Z}_{\geqslant1}} \end{aligned} \end{cases} I think this is the answer that the author of this exercise essentially(probably) wants us to provide.