Normat 61:3, 153–160 (2013) 153
p-adic numbers
Ulf Persson
Matematiska Institutionen
Chalmers Tekniska Högskola och
Göteborgs Universitet
ulfp@chalmers.se
Introduction
Consider an infinite sum
3+1◊ 7+
or more generally for any p a general sum of type
a
0
+ a
1
p + a
2
p
2
+ a
3
p
3
+ ...
given by an infinite sequence of intergers (a
0
,a
1
,a
2
...) where each a
i
we have
0 Æ a
i
<p. What sense can we make of this?
Let us try it from another angle. Let x
n
be an infinite sequence of integers,
such that x
n
= x
n+1
(p
n+1
). We c an then define addition and multiplication of
such sequences and s till stay within them. The congruence says that by adding a
suitable a
n+1
p
n+1
to x
n
we can arrange it so that x
n
+ a
n+1
p
n+1
= x
n+1
(p
n+2
).
Thus we can think of each of the elements x
n
as the truncation of the formal
infinite sum
q
iØ0
a
i
p
i
, specifically x
n
is the truncated
q
n
iØ0
a
i
p
i
. Those finite
sums present no problems, they are just expansions of integers using a base p
instead of the familiarbase 10. Writing the infinite sum from left to right is just a
convention and hence a matter of taste. One could as well write it from right to left,
as the Arabs do, and as we do in a sense when we write down numbers in standard
decimal notation. What is different now is that we allow the digits to c ontinue
indefinitely (from right to left). This might be unsettling, but of course we are
used to writing expansions from left to right when we consider infinite expansions
where we replace p by 1/10. The point is of course that the further right we go,
the less significant are the digits, at least if we are merely concerned about the
size. If two decimal expansions agree to the n-th digit means that the difference
between them is less than 10
≠n
. We can think of fi say as an infinite sequence
of finite expansions which agree with each other up to the relevant accuray. Thus
3, 3.1, 3.14, 3.141, 3.1415, 3.14159 .... Similarly we can say that two integers are
close to each other if their differe nce is divisible by a high power of p. We can write
any numb er as p
n
a where (a, p)=1and define its norm as p
≠n
. We then get a
metric on Z, in fact an ultrametric, that satisfies the stronger version of the triangle
154 Ulf Persson Normat 3/2013
inequality, in fact d(x, y) Æ max(d(x, z),d(y, z)).Thep-adic integers simply form
the completion of Z under this me tric, where the integers form a dense set and can
approximate any p-adic number arbitrarily close.
Dividing p-adic numbers
We note that any p-adic number not divisible by p (i.e. a
0
”=0)isinvertible.To
find its inverse we start with a X = a
0
+ a
1
p + a
2
p
2
... and make an ’Ansatz
b
0
+ b
1
p + b
2
p
2
+ .... As a
0
”=0by assumption we can find a b
0
such that a
0
b
0
=
mp +1. This means that 1 ≠ b
0
X = 0(p) or 1 ≠ b
0
X = pX
1
. Now chose b
1
such
X
1
≠b
1
X = 0(p) this means that we can write 1 ≠b
0
X ≠b
1
pX = p
2
X
2
. Generally
if we have found X
n
we choose b
n
such that X
n
≠ b
n
X = 0(p) which is always
possible because only a
0
is involved. This means that X
n
≠ b
n
X = pX
n+1
and
we have now found the next X
n
. Note that only the first constant coefficient is
of interest, but of course the choice of X
n
will influence the first coefficients of all
subsequent. Putting it all together we get
1 ≠ (b
0
+ b
1
p + b
2
p
2
+ ...p
n
)X = p
n+1
X
n+1
= 0(p
n+1
)
Note that this way of division is much easier than the long division we are used
to. In fact if we would like to divide two numbers in decimal notation, where the
factor only ends in 1, 3, 7, 9 (the units modulo ten) we can determine the last digit
of the quotient (if exists as an integer). Multiplying the factor by that digit and
subtracting we get a new number that ends w ith a zero, which we can cancel, and
start again. If the process terminates, and it is easy to see when there will no longer
be any hope of termination, we have in fact found the qoutient with less trouble
than using long division. If the process does not terminate the putative factor does
not exist. One may, however, acc ept the infinite long sequence of digits as some
kind of strange number. Doing so, we are working in the spirit of p ≠adic numbers
(although one does not usually consider 10-adic numbers.
As an illustration to this let us consider two typical case as illustrations.
6731/67 The last digit has to be a 3 we have 6731 ≠ 3 ◊ 67 = 1530 cancel the
last zero and the next to last has to be 9 and we do 653 ≠ 9 ◊ 67 = 50 and by
now we see that it will not work out, all we can say is that the number was 500
too big (and if we want we can repeat the process hoping to get the smallest
remainder). Another example is 2967/69 we get 3 and 2967 ≠ 3 ◊ 69 = 2760
and then 4 and 276≠ 4◊ 69 = 0 and we are done with the result 43 (remember
to read from right to left).
Now let us play a little. We see that
1
1≠p
=1+p + p
2
+ p
3
+ and if we multiply
with (p-1) we obtain that ≠1=(p ≠1) + (p ≠1)p
2
+(p ≠1)p
3
+ .. We can of course
use this to get a representation for any negative numb er. Or we could proce ed in a
straightforward way. Let us consider the number 2345 (picked at random). Using
say the 7-adics we can write it as 6 ◊ 7+5◊ 7
2
+6◊ 7
3
. Or if we prefer as 0656.
We then need to write 1 ◊ 7+1◊ 7
2
+6◊ 7
4
+6◊ 7
5
+ ... to get things to
cancel additively. Or 01106666666666 ... representing ≠2345. We may write it as
Normat 3/2013 Ulf Persson 155
0110 + 0000666666 where the first term represents 56 and the second term ≠7
4
hence the sum is 56 ≠ 2401 = ≠2345 as expected of course. This gives us another
method of finding the negative of a number A s imply choose the smallest power P
of 7 bigger than A and consider P ≠ A. Convert A 7-adically and attach after the
last digit the infinite sequence of 6
Õ
s.
Let us now look at something more interesting, namely fractions. We know since
childhood that those are characterized by having periodic decimal expansions. To
find it, you need to do the long division, to go backwards you use a nice trick, which
in fact is nothing else than summing a geometric series. Can something similar hold
for p-adic integers?
One direction is easy and natural enough. Look at a periodic expansion
A + p
k
A + p
2k
A + p
3k
A + ...
where we assume that A gives the periodicity, i.e.A<p
k
(and thus A has length
k).
We can easily sum it as
A
1≠p
k
. The problem is (if it is a problem) that this is a
negative number. Can only negative numb ers occur as perio dics ? Let us find the
negative of our number. That means finding B such that A + B = p
k
(recall that
A<p
k
so B>0.AddingB will leave a one to carry, so if B
Õ
= B ≠1 we can write
down the following identity
B+p
k
B
Õ
+p
2k
B
Õ
+···=
A
p
k
≠ 1
=
p
k
≠ 1 ≠ B
Õ
p
k
≠ 1
= 1+
B
Õ
1 ≠ p
k
= 1+B
Õ
+p
k
B
Õ
+p
2k
B
Õ
...
and everything makes sense. (Now we will leave it to the reader to handle the
cases when the periodicity is just asymptotic and prefigured by a random expres-
sion.)
But what about the converse? When we divide in the ordinary setting it is
obvious that we will get something periodic, as there will only be a finite number
of possible remainders, and once we return to an old one, the process starts again.
This incidentally also gives an upper bound on the length of the period in terms
of the size of the denominator. The division algorithm we described above gives no
such obvious indication of repetition, and certainly not as to its possible length.
For the convenience of the reader let us recall the salient features of periodic
decimal expansions. Let us restrict to fractions m/q where q is a prime (obviously
different from 2, 5) and 0 <m<q. We get that 10 is an element in Z
ú
q
(where we
now refer to Z
q
= Z/qZ
q
). The order k of ten is a divisor of the order q ≠ 1 of the
(cyclic) group Z
ú
q
which is also the length of period. If k = q ≠ 1 the situation is
particularly simple. The pe riodic expansion of 1/q is of length q ≠ 1 which should
really be presented in a circle, because the expansion of m/q is the same, except that
the starting point is different namely when the remainder m occurs. Furthermore
all digits occur essentially equally often, meaning no digit occurs more than one
more than any other digit, and if q = 1(10) all digits occur equally often. And what
is more, the same is true for combinations of digit up to a certain point. All of this
can be made very precise (and I refer to my Normat article...). If the period is not
maximal, there will be different periodic cycles, and the sets of remainders, (really
156 Ulf Persson Normat 3/2013
orbits under a natural action) will split up associated to each. Cycles will no longer
be equidistributed as to their digits, but their union will. Does something similar
hold in the p-adic setting? The abstract and elegant group theoretic explanation,
obscured by the rigors of long division, gives some hope, and in fact, the explanation
is even more transparent in our setting, given the formulas above.
So let us consider the quotient P/Q of ordinary (positive) integers, and let us
assume that P<Q.Therewillnowbeak such that Q|p
k
≠ 1 by Fermats small
theorem. The k can be chosen no bigger than Q ≠ 1. We can thus find a number
D so that P/Q = P D/QD = PD/(p
k
≠ 1) Note that PD < p
k
and we get the
periodic expansion (setting B
Õ
= p
k
≠ 1 ≠ PD) given by B + p
k
B
Õ
+ p
2k
B
Õ
+ ...
Let us do some examples: Set p =2and let us consider m/11. 2 is a primitive
root mo dulo 11 as neither 2
2
≠ 1=3nor 2
5
≠ 1 = 31 has eleven as a factor. We
now have 11 ◊ 93 = 2
10
≠ 1 = 1023 thus D is 93. We are thus considering
93
2
10
≠1
.
The period will thus be given by 1023 ≠93 = 930 or in binary notation 0100010111
. The first thing we notice is that there is the expected uniformity of digits five
zeros and five ones. We can also look at the binary expansions of 1023 ≠m ◊93 in
the ten cases, giving us
m period m period
1 0100010111 2 1010001011
3 0001011101 4 1101000101
5 0111010001 6 1000101110
7 0010111010 8 1110100010
9 0101110100 10 1011101000
We notice that all the periods are cyclic permutations of the first one, according
to the scheme 1, 2, 4, 8, 5, 10, 9, 7, 3, 6 of the successive powers of two modulo eleven.
This we can easily prove.
Notice that when we multiply with a power of p the period does not change.
If we make the same cutoffs what happens is that the beginning of the period is
shifted. This is easily seen by just looking at an example
4321|3025|3025|3025|3025|...
multiplying with p gives
0432|1302|5302|5302|5302|...
and with p
2
we get
0043|2130|2530|2530|...
. Note that the beginning may be affected, but the asymptotic p e riodicity is of
course not, as adding an integer to an infinite expansion does only affect the first
finite terms. Now every power of p has a remainder mod Q.Writep
m
= P
m
+ nQ
and we have
n + p
m
B + p
k
p
m
B
Õ
+ p
2k
p
m
B
Õ
+ ···= n +
p
m
A
p
k
≠ 1
=
p
k
≠ 1 ≠ P
m
D
p
k
≠ 1
Normat 3/2013 Ulf Persson 157
Note that the starting element of the period is simply given by finding the residue
of ≠1≠PD mod p the rest are just simply given by the powers of p. The sequence of
denominators that occurs in ordinary long division (corresponding to the powers of
ten) are now completely analogous to the sequence P
m
. But while in the standard
case division gives the digit, here we take modulos p which is easier. Obviously the
key point is to find D such that QD = p
k
≠ 1. In the familiar case this is done
by long division. Thus we find that there is a simple relation between the periods
of P/Q using the p-adic expansion and the other by using the ordinary expansion
using powers of p (instead of powers of 10). Adding the ’digits’ they should all add
up to p ≠ 1.
Square roots
We have that 2=3
2
(7) can we find a such that 2=a
2
(7
2
)?Weseta =3+7x
and get a
2
= 9 + 42x + 49x
2
= 2 + 7(1 + 6x)+7
2
x
2
. Thus we simply need to solve
1+6x = 0(7) which is easy namely put x =1so a =3+7will do. Can we go
further? Indeed we can if we have found A
n
=3+a
1
7+...a
n
7
n
we make a try
with A =3+a
1
7+...a
n
7
n
+ x7
n+1
= A
n
+ x7
n+1
.If2 ≠ A
2
n
= y
n
7
n+1
we get
2 ≠A
2
=(y
n
≠2a
0
x)7
n+1
(7
n+2
) and we need only to solve for x which is possible,
as 2a
0
=6”=0. In order to do it in practice we need to keep track of the y
n
’s.
Thus for simplicity let us do that in the general case. In order to be able to solve
y
2
= D it is nec es sary to do it modulo p,i.e.D needs to be a quadratic residue
modulo p. Choose one such solution A
0
= a
0
and then proceed inductively. Set
A
2
n
≠ D = y
n
p
n+1
and A
n+1
= A
n
+ a
n+1
p
n+1
.Thus
A
2
n+1
≠ D = yp
n+1
+ y
Õ
p
n+2
+2a
0
a
n+1
p
n+1
+2A
Õ
a
n+1
p
n+2
+ a
2
n+1
pp
n+2
where y
n
= y + k + py
Õ
and A
n
= a
0
+ pA
Õ
where k = y +2a
0
a
n+1
.Wethushave
to solve y +2a
0
a
n
= 0(p) and then set y
n+1
= y
Õ
+ k +2A
Õ
a
n+1
+ a
2
n+1
p
n
.This
can easily be implemented on a computer thinking of the p-adic numbers as long
arrays. The square root starts
3+7+2· 7
2
+6· 7
3
+7
4
+2· 7
5
+7
6
+2· 7
7
+7
8
+2· 7
9
+
+4· 7
10
+6· 7
11
+6· 7
12
+2· 7
13
+7
14
+7
15
+2· 717 ... (1)
while the other square root is of course then given by
3+5· 7+4· 7
2
+5· 7
4
+4· 7
5
+6· 7
6
+4· 7
7
+5· 7
8
+
+4· 7
9
+2· 7
10
+4· 7
13
+5· 7
14
+5· 7
15
+6· 7
16
+4· 717 ... (2)
One can easily compute tens of thousands of ’digits’ giving a random-looking se-
quence of integers 0, 1, 2 ...6 more or less equally distributed. If one doe s it for ten
thousand terms, we get a distribution of 1397, 1402, 1446, 1403, 1465, 1428, 1459 re-
spectively.
158 Ulf Persson Normat 3/2013
Another way of computing it is to use the Pell’s equation. We have that the
equation x
2
≠2y
2
=7has the solution (3, 1) think of it as z =3+1·
Ô
2. We can do
natural conjugation ¯z =3≠1
Ô
2 and then the norm z¯z becomes multiplicative. In
particular z
n
= x
n
+y
n
Ô
2 and 7
n
(z¯z)
n
= x
2
n
≠2y
2
n
where we easily can wrtite down
a recursive formula for (x
n
,y
n
). We then obtain (x
n
/y
n
)
2
= 2(7
n
). Recall that in
the real case we instead start with a solution (x, y)=(3, 2) to x
2
≠2y
2
=1getting
in the same way (x/y)
2
≠ 2=1/(y
2
) with (x
n
/y
n
) a good real approximation of
Ô
2. From this we see that the 7-adic presentation of
Ô
2 has nothing to do, with
the ’heptanary’ expansion of the number.
Z
2
and the Cantor set
The metric defines a topology on Z
p
. This is a totally discontinous topology (the
maps onto the finite subgroups Z/p
n
Z with discrete topology) which can be identi-
fied with a Cantor set. In the case of p =2this can be beautifully presented using
the standard Cantor set.
Recall that the Cantor set is constructed by succesively removing the open one-
third of each interval. More explicitly we get for each integer n an interval I
n
where
the binary representation of n gives an address. Thus I
13
= I
1101
denotes that we
consider the compact interval of length (1/3)
4
given by chosing the right, left,
right, right interval in the construction. Each point in the Cantor set is uniquely
determined by the intervals I
n
which containts it, and its address will be infinite
given by a sequence of 0’s and 1’s, hence we can associate a unique element of Z
2
to it. We may also equivalently describe the Cantor set as the real numbers inside
[0, 1] whose triadic expansion only contains 0’s and 2’s. Thus to each infinite binary
sequence a
0
,a
1
,a
2
... we associate the real numb e r
q
Œ
nØ0
2a
n
3
≠n
.Therewillbe
three types of elements in the Cantor set. Those which are isolated on the left, they
will correspond to left end points of the intervals I
n
, those which are isolated on the
right, they will correspond to the right end points, and the rest. The first ones are
characterized by only having a finite number of 2’s in their expansions, the second
ones by only having a finite number of 0’s (thus in these cases the expansions will
end with an infinite sequence of o’s or2’s). The rest will have an infinite number
of both 0’s and 2’s. In terms of 2-adic numbers the first will correspond to non-
negative integers, the second to negative integers, and the third to the non-integral
elements, of which the proper fractions will constitute an interesting subset.
The Cantor set is a so called self-similar set. If L denotes the left third, and
R the right third (in the previous terminology I
0
and I
1
respectively) we have a
homeomorphism ◊ : C = L fi R æ L given by x ‘æ
1
3
x with the inverse x ‘æ 3x.
Furthermore we have an isomorphism Ÿ : L æ R given by x ‘æ x +
2
3
with the
inverse x ‘æ x ≠
2
3
(or x +
2
3
(1) considered modulo the integers.).
We can now identify the elements of Z
2
with the elements of the Cantor set. It
can be instructive to indicate the first few constructions
0 0111 ... • 1 1111..
0 ≠ 2 • 1 ≠ 1
Normat 3/2013 Ulf Persson 159
0 0011 . .. • 01 0111 ... •• 1 1011 ... • 110 1111 ...
0 ≠ 4 • 2 ≠ 2 •• 1 ≠ 3 • 3 ≠ 1
The above isomorphisms can also be expressed using 2-adic numbers as ◊(x)=
2x and Ÿ(x)=
1
2
x +1
Those can be used to inductively construct the Cantor set in a simple mindless
way. We start out with
0 ≠ 21 ≠ 1
which leads to on the lefthand side when multiplied by two
0 ≠ 42 ≠ 2
the righthand then becomes when added one
1 ≠ 33 ≠ 1
and together
0 ≠ 42 ≠ 213 ≠ 31
doing it again yields
0 ≠ 84 ≠ 426 ≠ 6 ≠ 21 ≠ 75 ≠ 337 ≠ 5 ≠ 1
and again
0, ≠16, 8, ≠8, 4, 12, ≠12, ≠4, 2, ≠14, 10, ≠6, 6, 14, ≠10, ≠2, 1, ≠15, 9,
≠ 7, 5, 13, ≠11, ≠3, 3, ≠13, 11, ≠5, 7, 15, ≠9, ≠1 (3)
What we have here is a lexiographic ordering of the 2-adics, or rather of Z
2
flZ
as those with an infinite number of ’digits’ will never occur explicitly. Note that
there are pairs such as (≠2, 1) and (≠3, 3) which once they appear they will always
persist. Those corresponds to the removed middles. Starting with the first (≠2, 1)
they are generated by the operations of x ‘æ 2x, x ‘æ x +1. Note in fact that every
positive number n has an immediate predecessor, but none on the right, while
every negative number has an immediate successor. How to find the p os ition of
any positive number? If it is odd, it belongs to the right half, then subtract one
and divide by two, otherwise just divide by two. Code the first with one, the second
with zero. Continue inductively. We are just getting the binary representation. We
will in the end get to one, and then decide to stop there. So 26 will be coded by
01011 or 26 = 2 ◊ (2 ◊ 2 ◊ (2 ◊ 1) + 1) + 1). Now replace the innermost 1 by ≠2
and consider 2 ◊(2 ◊2 ◊(2 ◊(≠2) + 1) + 1) = ≠22.Thus(≠22, 26) will be an open
interval removed and ≠22 be the immediate predecess or to 26. In fact 26 = 01011
then ≠22 = 0101011 ... (as 01101 cancels it.)
The representation of the 2-adic numbers as a Cantor set does not do justice to
the ultrametric, the metric induced by R although equivalent to the 2-adic metric
160 Ulf Persson Normat 3/2013
is not equivalent to it. Distances between x and y from two different intervals are
always the same. However we can embed the Cantor set in a function space with
the L
1
-norm such that this will be true. Let us denote by I
n
also the characteristic
function of the interval I
n
and we then define for any element x œ C the function
f
x
=
q
xœI
n
I
n
.Fixingx we will have f
x
(y)=Πiff x = y and
s
1
0
f
x
(t)dt =
1+
1
3
+
1
9
=3/2.Wewillthendefined(x, y)=
s
1
0
|f
x
(t) ≠ f
y
(t)|dt.Thiswillhave
the ultra-metric property, in fact if the first n digits of x and y agree, the distance
will be 2
q
kØn
(
1
3
)k =
1
3
n≠1
with the 2 adic distance beeing 2
≠n
. With some fudging
of the definition of f
x
we can arrange it so that we have actually equality.
