Addition with rightward carries, multiplication, and computing inverses digit by digit
One of the most surprising facts about p-adic numbers is that their arithmetic works almost exactly like ordinary base-p arithmetic -- with one crucial twist. Instead of digits extending to the right (as in decimal expansions), p-adic digits extend infinitely to the left. This means that carries propagate leftward, toward higher powers of p, rather than rightward.
This simple reversal of direction has profound consequences. Addition and multiplication follow the familiar column-by-column algorithms you learned in school, but now they produce infinite digit strings. Most remarkably, every integer coprime to p has a multiplicative inverse -- an infinite p-adic expansion whose product with the original number equals exactly 1.
Add two integers in their p-adic representation. Step through the algorithm column by column: at each position, add the two digits plus any incoming carry, take the result mod p to get the output digit, and pass the quotient leftward as the new carry.
Key insight: p-adic addition is identical to ordinary base-p addition, but carries propagate to the left (toward higher powers of p). For negative numbers, the digits eventually become p−1 repeating -- just like how −1 in base 10 would be ...99999 if we allowed infinite digits.
Multiply two integers using the standard long multiplication algorithm in base p. Each digit of the second number multiplies the entire first number, producing a shifted partial product. The partial products are then summed to give the final result.
Key insight: Multiplication in Qp uses the same long-multiplication algorithm as in school arithmetic. Each digit of the result depends only on finitely many digits of the inputs, which is why the p-adic product is always well-defined -- even for infinite digit strings.
Compute 1/n as a p-adic number by finding digits d0, d1, d2, ... one at a time. At each step, choose the digit that makes the product n × (partial sum) congruent to 1 modulo the next power of p. Watch the verification column confirm that each new digit extends the accuracy.
Computing 1/7 in Q3: digits of the inverse (least significant first)
Key insight: Every integer coprime to p has a p-adic inverse, which is an infinite series of digits. The algorithm builds this inverse one digit at a time using modular arithmetic -- the digit dk is chosen so that n × (partial sum) ≡ 1 (mod pk+1). This is a concrete instance of the general principle that Zp contains 1/(p−1) of all rational numbers.