padic number
In mathematics the Template:Mvaradic number system for any prime number Template:Mvar extends the ordinary arithmetic of the rational numbers in a way different from the extension of the rational number system to the real and complex number systems. The extension is achieved by an alternative interpretation of the concept of "closeness" or absolute value. In particular, Template:Mvaradic numbers have the interesting property that they are said to be close when their difference is divisible by a high power of Template:Mvar – the higher the power the closer they are. This property enables Template:Mvaradic numbers to encode congruence information in a way that turns out to have powerful applications in number theory including, for example, in the famous proof of Fermat's Last Theorem by Andrew Wiles.^{[1]}
Template:Mvaradic numbers were first described by Kurt Hensel in 1897,^{[2]} though with hindsight some of Kummer's earlier work can be interpreted as implicitly using Template:Mvaradic numbers.^{[3]} The Template:Mvaradic numbers were motivated primarily by an attempt to bring the ideas and techniques of power series methods into number theory. Their influence now extends far beyond this. For example, the field of [[padic analysisTemplate:Mvaradic analysis]] essentially provides an alternative form of calculus.
More formally, for a given prime Template:Mvar, the field Q_{p} of Template:Mvaradic numbers is a completion of the rational numbers. The field Q_{p} is also given a topology derived from a metric, which is itself derived from the padic order, an alternative valuation on the rational numbers. This metric space is complete in the sense that every Cauchy sequence converges to a point in Q_{p}. This is what allows the development of calculus on Q_{p}, and it is the interaction of this analytic and algebraic structure which gives the Template:Mvaradic number systems their power and utility.
The Template:Mvar in padic is a variable and may be replaced with a constant (yielding, for instance, "the 2adic numbers") or another placeholder variable (for expressions such as "the ℓadic numbers"). The "adic" of "padic" comes from the ending found in words such as dyadic or triadic.
Contents
Introduction
This section is an informal introduction to padic numbers, using examples from the ring of 10adic (decadic) numbers. Although for padic numbers p should be a prime, base 10 was chosen to highlight the analogy with decimals. The decadic numbers are generally not used in mathematics: since 10 is not prime, the decadics are not a field. More formal constructions and properties are given below.
In the standard decimal representation, almost all^{[4]} real numbers do not have a terminating decimal representation. For example, 1/3 is represented as a nonterminating decimal as follows
Informally, nonterminating decimals are easily understood, because it is clear that a real number can be approximated to any required degree of precision by a terminating decimal. If two decimal expansions differ only after the 10th decimal place, they are quite close to one another; and if they differ only after the 20th decimal place, they are even closer.
10adic numbers use a similar nonterminating expansion, but with a different concept of "closeness". Whereas two decimal expansions are close to one another if their difference is a large negative power of 10, two 10adic expansions are close if their difference is a large positive power of 10. Thus 3333 and 4333, which differ by 10^{3}, are close in the 10adic world, and 33333333 and 43333333 are even closer, differing by 10^{7}.
More precisely, a rational number Template:Mvar can be expressed as 10^{e}·p/q, where Template:Mvar and Template:Mvar are positive integers and Template:Mvar is relatively prime to Template:Mvar and to 10. For each r ≠ 0 there exists the maximal Template:Mvar such that this representation is possible. Let the 10adic norm of Template:Mvar to be
Closeness in any number system is defined by a metric. Using the 10adic metric the distance between numbers Template:Mvar and Template:Mvar is given by x − y_{10}. An interesting consequence of the 10adic metric (or of a Template:Mvaradic metric) is that there is no longer a need for the negative sign. As an example, by examining the following sequence we can see how unsigned 10adics can get progressively closer and closer to the number −1:
and taking this sequence to its limit, we can say that the 10adic expansion of −1 is
In this notation, 10adic expansions can be extended indefinitely to the left, in contrast to decimal expansions, which can be extended indefinitely to the right. Note that this is not the only way to write Template:Mvaradic numbers – for alternatives see the Notation section below.
More formally, a 10adic number can be defined as
where each of the a_{i} is a digit taken from the set {0, 1, … , 9} and the initial index Template:Mvar may be positive, negative or 0, but must be finite. From this definition, it is clear that positive integers and positive rational numbers with terminating decimal expansions will have terminating 10adic expansions that are identical to their decimal expansions. Other numbers may have nonterminating 10adic expansions.
It is possible to define addition, subtraction, and multiplication on 10adic numbers in a consistent way, so that the 10adic numbers form a commutative ring.
We can create 10adic expansions for negative numbers as follows
and fractions which have nonterminating decimal expansions also have nonterminating 10adic expansions. For example
Generalizing the last example, we can find a 10adic expansion with no digits to the right of the decimal point for any rational number p⁄q such that q is coprime to 10; Euler's theorem guarantees that if Template:Mvar is coprime to 10, then there is an Template:Mvar such that 10^{n} − 1 is a multiple of q. The other rational numbers can be expressed as 10adic numbers with some digits after the decimal point.
As noted above, 10adic numbers have a major drawback. It is possible to find pairs of nonzero 10adic numbers (having an infinite number of digits, and thus not rational) whose product is 0.^{[5]} This means that 10adic numbers do not always have multiplicative inverses i.e. valid reciprocals, which in turn implies that though 10adic numbers form a ring they do not form a field, a deficiency that makes them much less useful as an analytical tool. Another way of saying this is that the ring of 10adic numbers is not an integral domain because they contain zero divisors. The reason for this property turns out to be that 10 is a composite number which is not a power of a prime. This problem is simply avoided by using a prime number Template:Mvar as the base of the number system instead of 10 and indeed for this reason Template:Mvar in Template:Mvaradic is usually taken to be prime.
padic expansions
{{ safesubst:#invoke:Unsubst$N=Unreferenced section date=__DATE__ $B= {{ safesubst:#invoke:Unsubst$N=Unreferenced date=__DATE__ $B= {{#invoke:Message boxambox}} }} }} When dealing with natural numbers, if we take Template:Mvar to be a fixed prime number, then any positive integer can be written as a base Template:Mvar expansion in the form
where the a_{i} are integers in {0, … , p − 1}.^{[6]} For example, the binary expansion of 35 is 1·2^{5} + 0·2^{4} + 0·2^{3} + 0·2^{2} + 1·2^{1} + 1·2^{0}, often written in the shorthand notation 100011_{2}.
The familiar approach to extending this description to the larger domain of the rationals (and, ultimately, to the reals) is to use sums of the form:
A definite meaning is given to these sums based on Cauchy sequences, using the absolute value as metric. Thus, for example, 1/3 can be expressed in base 5 as the limit of the sequence 0.1313131313..._{5}. In this formulation, the integers are precisely those numbers for which a_{i} = 0 for all i < 0.
With padic numbers, on the other hand, we choose to extend the base Template:Mvar expansions in a different way. Unlike traditional integers, where the magnitude is determined by how far they are from zero, the "size" of Template:Mvaradic numbers is determined by the [[Padic order#padic NormTemplate:Mvaradic Norm]], where high positive powers of Template:Mvar are relatively small compared to high negative powers of Template:Mvar. Consider infinite sums of the form:
where k is some (not necessarily positive) integer, and each coefficient can be called a Template:Mvaradic digit.^{[7]} With this approach we obtain the Template:Mvaradic expansions of the Template:Mvaradic numbers. Those Template:Mvaradic numbers for which a_{i} = 0 for all i < 0 are also called the Template:Mvaradic integers.
As opposed to real number expansions which extend to the right as sums of ever smaller, increasingly negative powers of the base Template:Mvar, Template:Mvaradic numbers may expand to the left forever, a property that can often be true for the Template:Mvaradic integers. For example, consider the Template:Mvaradic expansion of 1/3 in base 5. It can be shown to be …1313132_{5}, i.e., the limit of the sequence 2_{5}, 32_{5}, 132_{5}, 3132_{5}, 13132_{5}, 313132_{5}, 1313132_{5}, … :
Multiplying this infinite sum by 3 in base 5 gives …0000001_{5}. As there are no negative powers of 5 in this expansion of 1/3 (i.e. no numbers to the right of the decimal point), we see that 1/3 satisfies the definition of being a Template:Mvaradic integer in base 5.
More formally, the Template:Mvaradic expansions can be used to define the field Q_{p} of Template:Mvaradic numbers while the Template:Mvaradic integers form a subring of Q_{p}, denoted Z_{p}. (Not to be confused with the [[Modular arithmetic#Ring of congruence classesring of integers modulo Template:Mvar]] which is also sometimes written Z_{p}. To avoid ambiguity, Z/pZ or Z/(p) are often used to represent the integers modulo Template:Mvar.)
While it is possible to use the approach above to define Template:Mvaradic numbers and explore their properties, just as in the case of real numbers other approaches are generally preferred. Hence we want to define a notion of infinite sum which makes these expressions meaningful, and this is most easily accomplished by the introduction of the Template:Mvaradic metric. Two different but equivalent solutions to this problem are presented in the Constructions section below.
Notation
There are several different conventions for writing Template:Mvaradic expansions. So far this article has used a notation for Template:Mvaradic expansions in which powers of Template:Mvar increase from right to left. With this righttoleft notation the 3adic expansion of Template:Frac, for example, is written as
When performing arithmetic in this notation, digits are carried to the left. It is also possible to write Template:Mvaradic expansions so that the powers of Template:Mvar increase from left to right, and digits are carried to the right. With this lefttoright notation the 3adic expansion of Template:Frac is
Template:Mvaradic expansions may be written with other sets of digits instead of {0, 1, …, p − 1}. For example, the 3adic expansion of ^{1}/_{5} can be written using balanced ternary digits {1,0,1} as
In fact any set of Template:Mvar integers which are in distinct residue classes modulo Template:Mvar may be used as Template:Mvaradic digits. In number theory, Teichmüller representatives are sometimes used as digits.^{[8]}
Constructions
Analytic approach
{{#invoke:see alsoseealso}}
Template:Mvar = 2  ← distance = 1 →  
De ci mal 
Bi nary 
← d = ½ →  ← d = ½ →  

‹ d=¼ ›  ‹ d=¼ ›  ‹ d=¼ ›  ‹ d=¼ ›  
‹⅛›  ‹⅛›  ‹⅛›  ‹⅛›  ‹⅛›  ‹⅛›  ‹⅛›  ‹⅛›  
................................................  
17  10001  J  
16  10000  J  
15  1111  L  
14  1110  L  
13  1101  L  
12  1100  L  
11  1011  L  
10  1010  L  
9  1001  L  
8  1000  L  
7  111  L  
6  110  L  
5  101  L  
4  100  L  
3  11  L  
2  10  L  
1  1  L  
0  0…000  L  
−1  1…111  J  
−2  1…110  J  
−3  1…101  J  
−4  1…100  J  
Dec  Bin  ················································  

2adic ( Template:Mvar = 2 ) arrangement of integers, from left to right. This shows a hierarchical subdivision pattern common for ultrametric spaces. Points within a distance 1/8 are grouped in one colored strip. A pair of strips within a distance 1/4 has the same chroma, four strips within a distance 1/2 have the same hue. The hue is determined by the least significant bit, the saturation – by the next (2^{1}) bit, and the brightness depends on the value of 2^{2} bit. Bits (digit places) which are less significant for the usual metric are more significant for the Template:Mvaradic distance. 
The real numbers can be defined as equivalence classes of Cauchy sequences of rational numbers; this allows us to, for example, write 1 as 1.000… = 0.999… . The definition of a Cauchy sequence relies on the metric chosen, though, so if we choose a different one, we can construct numbers other than the real numbers. The usual metric which yields the real numbers is called the Euclidean metric.
For a given prime Template:Mvar, we define the padic absolute value in Q as follows: for any nonzero rational number Template:Mvar, there is a unique integer Template:Mvar allowing us to write x = p^{n}(a/b), where neither of the integers a and b is divisible by Template:Mvar. Unless the numerator or denominator of Template:Mvar in lowest terms contains Template:Mvar as a factor, Template:Mvar will be 0. Now define x_{p} = p^{−n}. We also define 0_{p} = 0.
For example with x = 63/550 = 2^{−1}·3^{2}·5^{−2}·7·11^{−1}
This definition of x_{p} has the effect that high powers of Template:Mvar become "small". By the fundamental theorem of arithmetic, for a given nonzero rational number x there is a unique finite set of distinct primes and a corresponding sequence of nonzero integers such that:
It then follows that for all , and for any other prime
It is a theorem of Ostrowski that each absolute value on Q is equivalent either to the Euclidean absolute value, the trivial absolute value, or to one of the Template:Mvaradic absolute values for some prime Template:Mvar. So the only norms on Q modulo equivalence are the absolute value, the trivial absolute value and the Template:Mvaradic absolute value which means that there are only as many completions (with respect to a norm) of Q.
The Template:Mvaradic absolute value defines a metric d_{p} on Q by setting
The field Q_{p} of Template:Mvaradic numbers can then be defined as the completion of the metric space (Q, d_{p}); its elements are equivalence classes of Cauchy sequences, where two sequences are called equivalent if their difference converges to zero. In this way, we obtain a complete metric space which is also a field and contains Q.
It can be shown that in Q_{p}, every element x may be written in a unique way as
where k is some integer such that a_{k} ≠ 0 and each a_{i} is in {0, …, p − 1 }. This series converges to x with respect to the metric d_{p}.
With this absolute value, the field Q_{p} is a local field.
Algebraic approach
In the algebraic approach, we first define the ring of Template:Mvaradic integers, and then construct the field of fractions of this ring to get the field of Template:Mvaradic numbers.
We start with the inverse limit of the rings Z/p^{n}Z (see modular arithmetic): a Template:Mvaradic integer is then a sequence (a_{n})_{n≥1} such that a_{n} is in Z/p^{n}Z, and if n ≤ m, then a_{n} ≡ a_{m} (mod p^{n}).
Every natural number m defines such a sequence (a_{n}) by a_{n} = m mod p^{n} and can therefore be regarded as a Template:Mvaradic integer. For example, in this case 35 as a 2adic integer would be written as the sequence (1, 3, 3, 3, 3, 35, 35, 35, …).
The operators of the ring amount to pointwise addition and multiplication of such sequences. This is well defined because addition and multiplication commute with the "mod" operator; see modular arithmetic.
Moreover, every sequence (a_{n}) where the first element is not 0 has an inverse. In that case, for every n, a_{n} and p are coprime, and so a_{n} and p^{n} are relatively prime. Therefore, each a_{n} has an inverse mod p^{n}, and the sequence of these inverses, (b_{n}), is the sought inverse of (a_{n}). For example, consider the Template:Mvaradic integer corresponding to the natural number 7; as a 2adic number, it would be written (1, 3, 7, 7, 7, 7, 7, ...). This object's inverse would be written as an everincreasing sequence that begins (1, 3, 7, 7, 23, 55, 55, 183, 439, 439, 1463 ...). Naturally, this 2adic integer has no corresponding natural number.
Every such sequence can alternatively be written as a series. For instance, in the 3adics, the sequence (2, 8, 8, 35, 35, ...) can be written as 2 + 2·3 + 0·3^{2} + 1·3^{3} + 0·3^{4} + ... The partial sums of this latter series are the elements of the given sequence.
The ring of Template:Mvaradic integers has no zero divisors, so we can take the field of fractions to get the field Q_{p} of Template:Mvaradic numbers. Note that in this field of fractions, every noninteger Template:Mvaradic number can be uniquely written as p^{−n} u with a natural number n and a unit in the Template:Mvaradic integers u. This means that
Note that S^{−1} A, where is a multiplicative subset (contains the unit and closed under multiplication) of a commutative ring with unit , is an algebraic construction called the ring of fractions of by .
Properties
Cardinality
Z_{p} is the inverse limit of the finite rings Z/p^{k} Z, but is nonetheless uncountable,^{[9]} and has the cardinality of the continuum. Accordingly, the field Q_{p} is uncountable. The endomorphism ring of the [[Prüfer groupPrüfer Template:Mvargroup]] of rank Template:Mvar, denoted Z(p^{∞})^{n}, is the ring of n × n matrices over Z_{p}; this is sometimes referred to as the Tate module.
Topology
Define a topology on Z_{p} by taking as a basis of open sets all sets of the form
 U_{a}(n) = {n + λp^{a} : λ ∈ Z_{p}}.
where a is a nonnegative integer and n is an integer in [1, p^{a}]. For example, in the dyadic integers, U_{1}(1) is the set of odd numbers. U_{a}(n) is the set of all padic integers whose difference from n has padic absolute value less than p^{1−a}. Then Z_{p} is a compactification of Z, under the derived topology (it is not a compactification of Z with its usual discrete topology). The relative topology on Z as a subset of Z_{p} is called the [[padic topologyTemplate:Mvaradic topology]] on Z.
The topology of Z_{p} is that of a Cantor set.^{[10]} For instance, we can make a continuous 1to1 mapping between the dyadic integers and the Cantor set expressed in base 3 by mapping in Z_{2} to in C, where . Using a different mapping, in which the integers go to just part of the Cantor set, one can show that the topology of Q_{p} is that of a Cantor set minus a point (such as the rightmost point).^{[11]} In particular, Z_{p} is compact while Q_{p} is not; it is only locally compact. As metric spaces, both Z_{p} and Q_{p} are complete.^{[12]}
Metric completions and algebraic closures
Q_{p} contains Q and is a field of characteristic 0. This field cannot be turned into an ordered field.
R has only a single proper algebraic extension: C; in other words, this quadratic extension is already algebraically closed. By contrast, the algebraic closure of Q_{p}, denoted Template:Overline, has infinite degree,^{[13]} i.e. Q_{p} has infinitely many inequivalent algebraic extensions. Also contrasting the case of real numbers, although there is a unique extension of the Template:Mvaradic valuation to Template:Overline, the latter is not (metrically) complete.^{[14]}^{[15]} Its (metric) completion is called C_{p} or Ω_{p}.^{[15]}^{[16]} Here an end is reached, as C_{p} is algebraically closed.^{[15]}^{[17]} However unlike C this field is not locally compact.^{[16]}
C_{p} and C are isomorphic as fields, so we may regard C_{p} as C endowed with an exotic metric. It should be noted that the proof of existence of such a field isomorphism relies on the axiom of choice, and does not provide an explicit example of such an isomorphism.
If K is a finite Galois extension of Q_{p}, the Galois group Gal(K/Q_{p}) is solvable. Thus, the Galois group Gal(Template:Overline/Q_{p}) is prosolvable.
Multiplicative group of Q_{p}
Q_{p} contains the Template:Mvarth cyclotomic field (n > 2) if and only if n  p − 1.^{[18]} For instance, the Template:Mvarth cyclotomic field is a subfield of Q_{13} if and only if n = 1, 2, 3, 4, 6, or 12. In particular, there is no multiplicative Template:Mvartorsion in Q_{p}, if p > 2. Also, −1 is the only nontrivial torsion element in Q_{2}.
Given a natural number Template:Mvar, the index of the multiplicative group of the Template:Mvarth powers of the nonzero elements of Q_{p} in QTemplate:Su is finite.
The number [[e (mathematical constant)Template:Mvar]], defined as the sum of reciprocals of factorials, is not a member of any Template:Mvaradic field; but e^{ p} ∈ Q_{p} (p ≠ 2). For p = 2 one must take at least the fourth power.^{[19]} (Thus a number with similar properties as Template:Mvar – namely a Template:Mvarth root of e^{ p} – is a member of Template:Overline for all Template:Mvar.)
Analysis on Q_{p}
The only real functions whose derivative is zero are the constant functions. This is not true over Q_{p}.^{[20]} For instance, the function
has zero derivative everywhere but is not even locally constant at 0.
If we let R be denoted Q_{∞}, then given any elements r_{∞}, r_{2}, r_{3}, r_{5}, r_{7}, ... where r_{p} ∈ Q_{p}, it is possible to find a sequence (x_{n}) in Q such that for all Template:Mvar (including ∞), the limit of x_{n} in Q_{p} is r_{p}.
Rational arithmetic
Eric Hehner and Nigel Horspool proposed in 1979 the use of a Template:Mvaradic representation for rational numbers on computers^{[21]} called Quote notation. The primary advantage of such a representation is that addition, subtraction, and multiplication can be done in a straightforward manner analogous to similar methods for binary integers; and division is even simpler, resembling multiplication. However, it has the disadvantage that representations can be much larger than simply storing the numerator and denominator in binary; for example, if 2^{n} − 1 is a Mersenne prime, its reciprocal will require 2^{n} − 1 bits to represent.
The reals and the Template:Mvaradic numbers are the completions of the rationals; it is also possible to complete other fields, for instance general algebraic number fields, in an analogous way. This will be described now.
Suppose D is a Dedekind domain and E is its field of fractions. Pick a nonzero prime ideal P of D. If x is a nonzero element of E, then xD is a fractional ideal and can be uniquely factored as a product of positive and negative powers of nonzero prime ideals of D. We write ord_{P}(x) for the exponent of P in this factorization, and for any choice of number c greater than 1 we can set
Completing with respect to this absolute value ._{P} yields a field E_{P}, the proper generalization of the field of padic numbers to this setting. The choice of c does not change the completion (different choices yield the same concept of Cauchy sequence, so the same completion). It is convenient, when the residue field D/P is finite, to take for c the size of D/P.
For example, when E is a number field, Ostrowski's theorem says that every nontrivial nonArchimedean absolute value on E arises as some ._{P}. The remaining nontrivial absolute values on E arise from the different embeddings of E into the real or complex numbers. (In fact, the nonArchimedean absolute values can be considered as simply the different embeddings of E into the fields C_{p}, thus putting the description of all the nontrivial absolute values of a number field on a common footing.)
Often, one needs to simultaneously keep track of all the abovementioned completions when E is a number field (or more generally a global field), which are seen as encoding "local" information. This is accomplished by adele rings and idele groups.
Local–global principle
Helmut Hasse's local–global principle is said to hold for an equation if it can be solved over the rational numbers if and only if it can be solved over the real numbers and over the Template:Mvaradic numbers for every prime Template:Mvar. This principle holds e.g. for equations given by quadratic forms, but fails for higher polynomials in several indeterminates.
See also
 1 + 2 + 4 + 8 + ...
 Cminimal theory
 Hensel's lemma
 kadic notation
 Mahler's theorem
 Volkenborn integral
Notes
 ↑ F. Q. Gouvêa, A Marvelous Proof, The American Mathematical Monthly, Vol. 101, No. 3 (Mar., 1994), pp. 203–222
 ↑ {{#invoke:Citation/CS1citation CitationClass=journal }}
 ↑ {{#invoke:citation/CS1citation CitationClass=citation }}. Translation into English of Theorie der algebraischen Functionen einer Veränderlichen (1882) by John Stillwell. Translator's introduction, page 35: "Indeed, with hindsight it becomes apparent that a discrete valuation is behind Kummer's concept of ideal numbers."
 ↑ The number of real numbers with terminating decimal representations is countably infinite, while the number of real numbers without such a representation is uncountably infinite.
 ↑ See Gérard Michon's article at
 ↑ {{#invoke:citation/CS1citation CitationClass=book }}
 ↑ Template:Cite web
 ↑ {{#invoke:citation/CS1citation CitationClass=citation }}.
 ↑ Robert (2000) Chapter 1 Section 1.1
 ↑ Robert (2000) Chapter 1 Section 2.3
 ↑ See Talk:padic number#Topology.
 ↑ Gouvêa (2000) Corollary 3.3.8
 ↑ Gouvêa (2000) Corollary 5.3.10
 ↑ Gouvêa (2000) Theorem 5.7.4
 ↑ ^{15.0} ^{15.1} ^{15.2} Cassels (1986) p.149
 ↑ ^{16.0} ^{16.1} Koblitz (1980) p.13
 ↑ Gouvêa (2000) Proposition 5.7.8
 ↑ Gouvêa (2000) Proposition 3.4.2
 ↑ Robert (2000) Section 4.1
 ↑ Robert (2000) Section 5.1
 ↑ Eric C. R. Hehner, R. Nigel Horspool, A new representation of the rational numbers for fast easy arithmetic. SIAM Journal on Computing 8, 124–134. 1979.
References
 {{#invoke:citation/CS1citation
CitationClass=book }}
 {{#invoke:citation/CS1citation
CitationClass=book }}
 {{#invoke:citation/CS1citation
CitationClass=book }}
 {{#invoke:citation/CS1citation
CitationClass=book }}
 {{#invoke:citation/CS1citation
CitationClass=book }}
 {{#invoke:citation/CS1citation
CitationClass=book }}
 {{#invoke:citation/CS1citation
CitationClass=book }}
 {{#invoke:citation/CS1citation
CitationClass=book }}
External links
 Weisstein, Eric W., "padic Number", MathWorld.
 Template:Planetmath reference
 padic number at Springer Online Encyclopaedia of Mathematics
 Completion of Algebraic Closure – online lecture notes by Brian Conrad
 An Introduction to padic Numbers and padic Analysis  online lecture notes by Andrew Baker, 2007
 Efficient padic arithmetic (slides)