home | index | units | counting | geometry | algebra | trigonometry | calculus | functions
analysis | sets & logic | number theory | recreational | misc | nomenclature & history | physics

Final Answers
© 2000-2020   Gérard P. Michon, Ph.D.

p-adic Arithmetic

 Coat-of-arms of 
 John von Neumann (1903-1957)
In mathematics,  you don't understand things.
 You just get used to them.

John von Neumann  (1903-1957)
 border
 border
 border

On this site, see also:

Related Links (Outside this Site)

p-adic Numbers, in Wikipedia (with comments)  or MathWorld.
Reciprocal of a p-adic number   |   p-Adic Numbers and TGD
p-Adic and Adelic Physics   by  Matthew R. Watkins  (University of Exeter).
Lecture Notes on p-adic Numbers,  collected by Franz Lemmermeyer.
Quote notation  (Rick Hehner & Nigel Horspool, 1979).

Wikipedia :   p-adic numbers   |   Ostrowski's theorem   |   p-adic analysis   |   p-adic quantum mechanics

Introduction to p-adic numbers (21:28)  by  Daniel Chan  (2017-07-23).
Introduction to p-adic harmonic analysis (1:01:56)  James Arthur   (2008-08-12).
Fractal Flows and the Arrow of Time (1:30:47)  Leonard Susskind   (2012-04-04).
Representations of p-adic groups (57:34)  by  Jessica Fintzen   (2018-02-26).
p-adic K-theory of p-adic rings (1:09:20)  by  Peter Scholze   (2018-06-26).
Period maps in p-adic geometry (56:29)  P. Scholze  (Fields Medal, 2018-09-18).

 
border
border

Polyadic Arithmetic


(2006-02-06)   Zp :  The Ring of p-adic Integers
What integers become if they're allowed infinitely many radix-p digits.

Motivation :

The so-called "two's complement" binary numeration allows a representation of negative integers compatible with the rules of addition for positive numbers.  For example, consider the following sum, where the propagation of the bit "carried" from right to left cancels infinitely many bits from the first addend.

  ...111111111111111111111111111111010
+                                  110
=                                    0

As the  second  addend is the binary representation of the integer 6,  the  first  addend must represent -6.  A finite version of this is used in computers, where a predetermined number of bits  (e.g., 32 bits)  make up a word, with the convention that the leftmost bit in a  word  stands for infinitely many like bits to the left.

Similarly, here are three identical terms which add up to 1, in radix 5:

  ...131313131313131313131313131313132
+ ...131313131313131313131313131313132
+ ...131313131313131313131313131313132
=                                    1

If this makes any sense at all,  "...13131313132"  should thus be  one third  of unity in radix 5.  Well, a sensible definition of such things exists:

Definition & Basic Properties :

For technical reasons, the numeration radix is normally chosen to be a prime number  p.  Objects like the above are thus called  p-adic integers :

  A  p-adic integer  is a sequence of residues  an  modulo  pn  
(n > 0)   in which  an+1  is congruent to  an  modulo  pn.

The quantity  an  is called the  order-n residue  of such a p-adic integer.  An ordinary integer  N  (also called a  rational integer  in this context)  is a special case of a p-adic integer, whose order-n residue is simply  N mod pn.

The sum (or the product) of two p-adic integers is defined as the p-adic integer whose order-n residue is the sum (or the product) of the order-n residues of both operands.  Modular arithmetic then establishes that p-adic integers form a ring.

The ring of p-adic integers is  not  countable.  (Each radix-p expansion of a real between 0 and 1 corresponds to a p-adic integer.  Almost all reals have only  one  such expansion; countably many have  two.)

Invertible p-adic Integers :

The primality of p ensures that there are no  zero-divisors  in this ring  (i.e., the product of two nonzero p-adic integers cannot be zero).  If  a1  is nonzero, the p-adic integer  A = (an )  is said to be  invertible  because it has a reciprocal which is also a p-adic integer.  (HINT:  In this case, an  has an inverse modulo pn.)

Hensel's lemma   |   Kurt Hensel (1861-1941)
 
Hensel Lemma and p-adic numbers (14:20)  Harpreet Bedi  (2016-05-21).
p-adic integers defined (14:20)  Harpreet Bedi  (2016-07-09).


(2006-02-11)   Nomenclature:  Polyadic Integers

When considering a composite radix (or one which is not assumed to be prime) some authors prefer to use the symbol  g  for the radix and talk about  g-adic  integers.  The usual Greek scientific prefixes may be used:

g (or p) 2356 71011
g-adic dyadictriadicpentadichexadic heptadicdecadichendecadic

There's no need for a name when g is the power of a prime p  (4, 8, 9, 16, 25 ... )  since the corresponding set is isomorphic to the one obtained for  p.

When the value of  p  is irrelevant, it would be better to speak of  polyadic integers  rather than  p-adic integers  (or also  polyadic numbers  rather than  p-adic numbers).  Likewise, we speak of  polygons  rather than  n-gons  unless the value of  n  is explicitely used in a neighboring expression.

So far, mathematicians have ignored this proper usage.  Unfortunately, I am still occasionally guilty of that myself:  A proper title for this collection of articles should have been  Polyadic Arithmetic.


(2006-02-09)   What if p isn't prime?  Dealing with  zero-divisors.
Decimal examples appear in the next article, which may be read first.

With a prime radix p, the product of nonzero p-adic integers is never zero  (that's what makes the construction of the p-adic numbers possible).

With a composite radix (g) which is not the power of a prime (including decimal numeration) we have no such luck:  The existence of  zero-divisors  has to be kept in mind constantly  (in a ring, a  zero-divisor  is, by definition, a nonzero element whose product by some nonzero element is zero).  Here are explicit examples of  zero-divisors  among g-adic integers.

If the radix is not the power of a prime, it can be expressed as the product of two factors (p and q)  neither of which divides the other.  The following residue sequences then define two nonzero g-adic integers (u & v) whose product is 0:

un   =   qpn mod (pq)n                     [ note that   up = u ]
vn   =   pqn mod (pq)n                     [ note that   vq = v ]

Both of these are also introduced in the next article, with consistent notations, in the decimal case (p=2,q=5) using a more practical approach which makes it easy to establish that both sequences properly define pq-adic integers  (in the above sense).  We may  then  see that  uv = 0  although neither factor vanishes.

As shown next in the decimal case (g=10) even simple quadratic equations may have "extra" solutions when there are zero-divisors around...

x2 = 0  never has any nonzero solution in g-adic integers  (thus, the equation  (x-a)2 = 0  has only one solution).  There are no  (nonzero)  nilpotent  g-adics; a power of a nonzero g-adic integer is never 0  (HINT:  gkn | xnk  implies  gn | x).

More generally,  P(x)Q(x)  and  P(x)kQ(x)  have the same roots in g-adic integers  (HINT:  The latter divides [P(x)Q(x)]).


(2006-02-09)   10-adic Integers   (decadic integers, or decadics)
Some recreational  decimal  arcana...  Fun with  zero-divisors.

Let's consider a recursively-defined sequence of decimal residues  (5, 25, 625, 0625... A007185)  which determines a 10-adic (or decadic) integer u :

u1 = 5             un+1   =   (un ) 2  mod 10 n+1

An induction on  n  would show that  un+1  is, indeed, of the form   k 10n + un  (HINT:  2kun is a multiple of 10).  Also, since all of its successive decimal residues verify the following equation, so does  u  itself;  u is  idempotent.

x 2   =   x

In a unital ring, that equation factors as  x (x-1) = 0.  So, if there were no zero-divisors, it would have only  two  solutions  (0 and 1).  Actually, there are  four  10-adic solutions.  If  x  is a solution, so is (1-x).   (A016090)

0 = ...00000000000000000000000000000000000000000000000000000000000000000000000
1 = ...00000000000000000000000000000000000000000000000000000000000000000000001
u = ...62166509580863811000557423423230896109004106619977392256259918212890625
1-u = ...37833490419136188999442576576769103890995893380022607743740081787109376

To verify this, grab your calculator and punch in the last n digits of either nontrivial solution.  Square  that  to obtain a number whose last n digits are the same.  Alternately, multiply the thing by its "predecessor"  (ending with either ...890624 or ...109375)  and you obtain a number ending with n zeroes.

Similarly, although the equation  x2 = 1  can be factored as   (x-1)(x+1) = 0   it has   four  decadic solutions as well  (if  x  is a solution, so is -x )  namely:

1 = ...00000000000000000000000000000000000000000000000000000000000000000000001
1-2u = ...75666980838272377998885153153538207781991786760045215487480163574218751
2u-1 = ...24333019161727622001114846846461792218008213239954784512519836425781249
-1 = ...99999999999999999999999999999999999999999999999999999999999999999999999

The decadic solutions of  x 3 = x.  are called trimorphic.  There are 9 of those, including  all  of the above:   0, 1, 1-2u, u-1, u, -u, 1-u, 2u-1, -1.

x2+1 = 0  has no solutions  (as there are none modulo 100)  but  x (x2+1) = 0  has two solutions  (beside 0)  in decadic integers :

v = ...06862593839649523223304553032451441224165530407839804103263499879186432
-v = ...93137406160350476776695446967548558775834469592160195896736500120813568

Each such solution verifies  x5 = x  (as it makes  x(x2+1)(x2-1)  vanish).  This suggests the following recursive definition of the order-n residues of  v  (a proper definition of a decadic integer, which "works" whenever v1 is even).

v1 = 2             vn+1   =   (vn ) 5  mod 10 n+1

We may remark that   uv = 0   and   u = 1 + v 2.  In the jargon of recreational mathematicians, the solutions of   x 5 = x   are called pentamorphic.  There are  15 pentamorphic decadic integers, including all trimorphic decadics:

0 = ...00000000000000000000000000000000000000000000000000000000000000000000000
1 = ...00000000000000000000000000000000000000000000000000000000000000000000001
1-2u = ...75666980838272377998885153153538207781991786760045215487480163574218751
v = ...06862593839649523223304553032451441224165530407839804103263499879186432
-u-v = ...30970896579486665776138023544317662666830362972182803640476581907922943
u-v = ...55303915741214287777252870390779454884838576212137588152996418333704193
u-1 = ...62166509580863811000557423423230896109004106619977392256259918212890624
u = ...62166509580863811000557423423230896109004106619977392256259918212890625
-u = ...37833490419136188999442576576769103890995893380022607743740081787109375
1-u = ...37833490419136188999442576576769103890995893380022607743740081787109376
-u+v = ...44696084258785712222747129609220545115161423787862411847003581666295807
u+v = ...69029103420513334223861976455682337333169637027817196359523418092077057
-v = ...93137406160350476776695446967548558775834469592160195896736500120813568
2u-1 = ...24333019161727622001114846846461792218008213239954784512519836425781249
-1 = ...99999999999999999999999999999999999999999999999999999999999999999999999

If   xn = x   for  some  integer  n  greater than 1,  x  is called  polymorphic.  Surprisingly,  all  polymorphic 10-adic integers are pentamorphic...  The only polymorphic 10-adic integers are thus the 15 decadics listed above !


Let's now consider a factored  monic  quadratic equation in decadic integers:

(x - a) (x - b)   =   0

Since 4 is not a divisor of zero among decadic integers  (the reader may want to prove that an ordinary integer is never a zero-divisor among polyadic integers)  an  equivalent  of the above is obtained by multiplying into  4  and rearranging:

[ 2x - (a+b) ] 2   =   (a-b) 2

sufficient  condition for this to hold is that   2x = (a+b) + y (a-b)   where  y  is one of the four "square roots of unity" listed above  (i.e., 1, -1, 1-2u, 2u-1).  This yields four equations, in which we may cancel the factor 2 from both sides  (we may do so because 2 is not a divisor of zero among decadic integers).  This way, we obtain the following four solutions for x, which are usually distinct  (they're all equal if  a=b  and may yield only two values in special cases like  b = a+ku).

a ,         b ,         u a + (1-u) b ,         (1-u) a + u b

For example,  x2 + x + 8 = 0  has no real solutions, but four decadic ones:

w = ...846001309162982116098126825854038627744656299971933409202632873031
u-1+(2u-1)w = ...819351433154332034684514552613602518954295770465438321601810486343
-u +(1-2u)w = ...180648566845667965315485447386397481045704229534561678398189513656
-1-w = ...153998690837017883901873174145961372255343700028066590797367126968

The above approach  fails  for quadratic equations whose leading coefficient is  not  invertible.  For example,  x (5x-1) = 0  has only one nonzero solution:

u/5 = ...12433301916172762200111484684646179221800821323995478451251983642578125

Note that  u  is divisible by any power of 5  (since  (u/5)n = u/5)  just like
1-u  is divisible by any power of 2  (since  ((1-u)/2)n = (1-u)/2).

To solve the equation  x (5x-1) = 0  we may remark that it's equivalent to  5x (5x-1) = 0  (as  5  isn't a decadic divisor of zero).  So, we have  5x = y  where  y  is one of the  4  solutions  (0,1,u,1-u)  of the aforementioned  equation  y (y-1) = 0.  As only two of those are divisible by 5, the original equation only has the two advertised solutions  (0 and u/5).  In the realm of  decadic numbers  (introduced below for the usual case of a prime radix)  5  has a reciprocal  (namely: 0.2)  and  x (5x-1) = 0  does have  4  solutions:

0 = ...0000000000000000000000000000000000000000000000000000000000000000000   
u/5 = ...3301916172762200111484684646179221800821323995478451251983642578125   
1/5 = ...0000000000000000000000000000000000000000000000000000000000000000000.2
(1-u)/5 = ...6698083827237799888515315353820778199178676004521548748016357421875.2

The nonzero (10-adic) solutions of   n x2 = x   are called  n-automorphic.  If defined, each expression  1/n, u/n and (1-u)/n  gives one of those.  That's  0, 1 or 3  n-automorphic 10-adic integers,  depending on what  GCD (n,10)  is:

 GCD (n,10)  12510
n-automorphic
decadic integers
1 / n
u / n
(1-u) / n
 
 
(1-u) / n
 
u / n
 
none

In the broader realm of  decadic numbers  (allowing finitely many digits to the right of the decimal point)  every nonzero [ordinary] integer  n  has a reciprocal  (1/n)  and the equation  n x 2 = x  always  has 4 distinct solutions:

0 ,   1/n ,   u/n   and   (1-u)/n

Such extra solutions to polynomial equations are entertaining but  unwieldy.  They are shunned by considering only the case of a  prime  radix  p.  Period.


(2011-09-15)   A decadic puzzle by J.A.H. Hunter (1902-1986)
10-adic equations have inspired many recreational mathematicians...

The above can be used to make sense of the following pattern:

97  
2737  
1755937  
70495937  
2582935937  
225707335937  
174319439335937  
747756919335937  
203950881319335937  
107145357117319335937  
11956559419477319335937  
1539378434417877319335937  
  =   2 x  7 2 - 1
  =   2 x  37 2 - 1
  =   2 x  937 2 - 1
  =   2 x  5937 2 - 1
  =   2 x  35937 2 - 1
  =   2 x  335937 2 - 1
  =   2 x  9335937 2 - 1
  =   2 x  19335937 2 - 1
  =   2 x  319335937 2 - 1
  =   2 x  7319335937 2 - 1
  =   2 x  77319335937 2 - 1
  =   2 x  877319335937 2 - 1

This example is credited to the mathematical columnist J.A.H. Hunter (1902-1986).  It's just an embodiment of  one  decadic solution to the equation:

x   =   2 x 2  - 1

That equation has two solutions modulo 10  (namely, 1 and 7)  which seed two different solutions in  decadic integers, namely  1  and a nontrivial solution  h  consistent with the above.  In the broader context of  decadic numbers,  there are  two  other solutions...  (although  p-adic numbers are normally introduced only when the radix  p  is  prime ).  The 4 solutions are:

1 = ...000000000000000000000000000000000000000000000000000000000000000000001   
h = ...249764371295716500836135134846344163506159929966088384389877319335937   
½-h = ...750235628704283499163864865153655836493840070033911615610122680664063.5
-½ = ...999999999999999999999999999999999999999999999999999999999999999999999.5

Although  h  may have presented the best recreational value for  J.A.H. Hunter,  (½ - h)  is a close second that's easily overlooked!  For example:

30101090670122680664063.5   =   2 (122680664063.5) 2  -  1

Futility Closet (2011-09-13)   Math note #93  by  Greg Ross.   Attribution of the puzzle to J.A.H. Hunter.
The Math Less Traveled (2011-09-14)   A curiosity  by  Brent Yorgey  (backlink  via  Matt Gardner Spencer).
James Alston Hope Hunter (1902-1986) "Fun with Figures" Oxford University Press (1956) & Dover (1965)


(2006-02-06)   Qp :  The Field of p-adic Numbers  (for any  prime  p )
p-adic numbers were invented in 1897 by Kurt Hensel (1861-1941).

The field of p-adic numbers is to the ring of p-adic integers what the field of rationals is to the ring of ordinary integers:  More precisely,  the p-adic numbers form the quotient field of the ring of  p-adic integers.

A quotient field  cannot  be constructed with a ring containing  zero-divisors,  which imposes that  p  be a power of a prime.  Without loss of generality,  we'll assume that  p  is prime  (since the structure obtained with any power of  p  is isomorphic to what we get we  p  itself).

Any nonzero p-adic integer is of the form  A p, where A is an  invertible  p-adic integer  (m being zero for invertible p-adic integers themselves).  The  quotient  construct introduces inverses for power of  p  which we may call  negative powers  of p.

The inverse of a noninvertible p-adic integer is thus the product of an invertible p-adic integer by a  negative  power of p.  Therefore, as quotients of p-adic integers,  all  p-adic numbers are simply of the following form, where  m  may  be negative:

¥
å  q i pi         where q i is in { 0, 1, 2 ... p-1 }
i = m

When it has infinitely many nonzero terms, this sum converges only according to a metric for which high powers of  p are  small.  Such a metric is presented below, which makes the field  Q complete  (i.e., every Cauchy sequence converges in it).

Assuming qm is nonzero, the p-adic metric of the above p-adic sum is  p-m.


(2006-02-17)   Elementary division of two p-adic numbers
It's just like ordinary long division, only backwards...

Let's give a step-by-step computation for the decadic division of 7 into 1:

1/7 = ...57142857142857142857142857142857142857142857142857142857142857142857143

At each of the steps listed below, we're faced with a "remainder".  A new digit must be found whose product by the divisor (7 in this example) has a last digit matching the last nonzero digit of the remainder (underlined).  This product is then subtracted from the remainder to yield a new remainder for the next step...

Remainder(s):
             1         21 = 7 x 3
...99999999980         28 = 7 x 4   <-+
...99999999700          7 = 7 x 1     |
...99999999000         49 = 7 x 7     |
...99999950000         35 = 7 x 5     |
...99999600000         56 = 7 x 8     |
...99994000000         14 = 7 x 2     |
...99980000000         28 = 7 x 4   --+

Quotient = ...2857143 = ...2857142857142857143

By convention, a string of digits with a vinculum over it stands for infinitely many repetitions of that string.

Note that a satisfactory "next digit" may not always be found in decimal  (zero-divisors, like the multiples of the aforementioned u and v, do not have a multiplicative inverse).  However, it's uniquely determined when the radix is  prime, which is what we normally assume.

When the radix is not a prime-power, the above algorithm ambiguously divides a zero-divisor into one of its multiples  (if uv=0, dividing ux by u could yield many values, including x+yv for any y).

There's a  faster way to compute the reciprocal of a p-adic integer, which is best understood in terms of the  p-adic metric  that we'll introduce later.


(2012-10-29)   Overbar Notation
For p-adic and rational numbers alike.

As examplified in the previous section, an overbar may be used in the expansion of p-adic numbers to stand for infinitely many repetitions of the string of digits it  binds.

This is exactly the same meaning as what is traditionally used for ordinary fractions.  We merely distinguish between p-adic numbers and rational numbers by putting an ellipsis  (...)  to the left of the repeated strings in the former case.  An ellipsis to the right of the overbar is optional for rational numbers, but's is recommended  (for readability)  in any discussion, like this one, where p-adics and rational numbers coexist.  Examples:

1/7   =   ...2857143
1/7   =   0.142857...

An overbar may straddle the decimal point:

100/7   =   14.2857...

The only pocket calculators I've found which display results with overbars are  Casio's ES calculators.  Casio has decided to avoid overbars straddling the decimal point,  at the cost of not always displaying the shortest possible expression.  In our last example, the result displayed by Casio is therefore:

100/7   =   14.285714...

To save space, the pocket calculators don't display the terminating ellipsis, which is redundant in a context where p-adic numbers are ruled out...

A few other thought-provoking examples:

...14.2857  =  (...142857.3 - .3)/10000  =  (1/70-3/10)/10000  =  -1/35000
 
    2/19   =   0.105263157894736842...
-2/19   =   ...105263157894736842
 
    3/29   =   0.1034482758620689655172413793...
-3/29   =   ...1034482758620689655172413793

We'll soon explain those patterns, with the fundamental tool presented next.


(2006-02-06)   The p-adic Metric  | x |p  of a Rational Number  x :
If a nonzero rational number is expressed in lowest terms as  x = pn (a/b)  then, by definition,  | x |p  =  p-n.  (We also define  | 0 |p = 0 .)

This valuation was introduced in 1913 by József Kürschák (1864-1933).

For example:     | 12/7 | 2  =  ¼       | 12/7 | 7  =  7       | 12/7 | 5  =  1

The rationals are not complete with respect to this metric.  The completion of the rationals with respect to the p-adic metric  (based on equivalence-classes of Cauchy sequences)  is the aforementioned  field of p-adic numbers.

This approach may be construed as an  analytical  definition of the p-adic numbers, which we've already introduced  algebraically  as the quotient field of the p-adic integers and  formally  as objects expressed in positional numeration of radix  p  if infinitely many digits are allowed to the left of the radix point but only finitely many nonzero digits to the right of it...

Metric and Topological Properties :

In a field or a ring, a  scalar norm  (or valuation)  is a nonnegative [real] function  |.|  vanishing only at zero, which is  multiplicative  (i.e.,  |x.y| = |x|.|y|)  and obeys the  triangular inequality  |x+y| ≤ |x|+|y|.  The above p-adic metric is such a norm.

A "vectorial" norm ||.|| on a vector space over a field endowed with a valuation |.| must satisfy the relation  ||x V|| = |x|.||V||.

A distance is a nonnegative [real] symmetric function of two variables vanishing only when its arguments are equal, which satisfies the  triangular inequality:

d(x,z)   ≤   d(x,y) + d(y,z)

A distance is said to be  ultrametric  if it obeys the stronger inequality:

d(x,z)   ≤   max ( d(x,y) , d(y,z) )

The p-adic distance  (and/or the p-adic norm)  happens to be ultrametric.

Distances are commonly derived from norms  (although they need not be)  via the relation  d(x,y)=|x-y|  (or d(x,y)=||x-y||).  In that case, the terms "distance", "norm" and "metric" refer essentially to the same thing and are used somewhat interchangeably.

A  [closed]  ball of radius R is the set of all points that are at a distance at most equal to R from a given point.  With the p-adic metric, two balls of the same radius are either disjoint or identical !

Ostrowski's Theorem :

In 1916, Alexander Ostrowski (1893-1986) showed that there are only three ways to define an absolute value on the field of rational numbers:

  • The trivial absolute value  (0 for a zero argument, 1 otherwise).
  • Raising to a positive exponent  less than or equal to unity  the standard absolute value  (itself equal to the nonnegative number that match either the argument or its opposite).
  • Raising to the power of a fixed positive exponent some p-adic metric.


(2006-02-19)   Quick and easy computation of a p-adic reciprocal :
A p-adic multiplicative inverse is the limit of a simple sequence, whose convergence is best analyzed in terms of the p-adic metric.

Consider a p-adic number in the standard form  a pm, where a is an  invertible  p-adic integer,  its reciprocal (multiplicative inverse) is  (1/a) p-m, where  1/a  can be computed efficiently by successive approximations :

| 1/a - x1 | < 1         and         xn+1   =   ( 2 - a xn )  xn

This is the simplest case (k = 2) of the following sequence of approximations  (for a positive integer k)  where the right-hand side is actually a polynomial function of  a  and  xn  (the minuend cancels the subtrahend's first term).

| 1/a - x1 | < 1         and         xn+1   =   (1/a) - ak-1 (1/a - xn ) k

Let's analyze this algorithm.  First, since  a  is an invertible p-adic integer, the initial condition simply means that the last p-adic digit of our initial approximation  must  be correct.  For a small radix p, it's easy to make it so by building a table of reciprocals modulo p  (for a single shot, use trial and error).  For a large p, the multiplicative inverse of  a  modulo p can be obtained efficiently as a Bezout coefficient  (one method is to trace back the steps of Euclid's algorithm).

Now, observe that  (since  | ak-1 |p = 1)  the quantity  | 1/a - xn |p  gets precisely raised to the power of  k  with each iteration that increments  n.

Therefore, the number of correct digits is multiplied by  k  at each step...  In the simplest process  (k = 2, as presented first)  the number of correct digits doubles with each iteration, for little more than the cost of two modular multiplications !

If  an  and  bn are the residues modulo  pn  of  a  and its reciprocal, then :

1   =   a1 b1   mod  p               b 2n    =    ( 2 - a 2n  bn bn   mod   p2n


(2012-10-30)   Radix-g  vs.  g-adic  representation of fractions.
Rational numbers also exist as  p-adic numbers.

Let's go back to previous "coincidences" that I promised to elucidate:

    2/19   =   0.105263157894736842...
-2/19   =   ...105263157894736842
 
    3/29   =   0.1034482758620689655172413793...
-3/29   =   ...1034482758620689655172413793

In the (ordinary) realm of rational numbers, the decimal expansion of 1/q  (where q is a positive rational integer) form a periodic string whose elementary period is an integer  P  of n digits.  n is the smallest positive integer which makes  10n-1  a multiple of q.  Using Carmichael's  lambda function,  we may state that the length  n  is a divisor of  l(q)  which itself divides  f(q),  the  Euler totient  of q.  The period  P  is then given by:

P   =   (10n-1) / q     which does yield:
1 / q   =   P / (10n-1)   =   0.P...

On the other hand, in the realm of decadic integers  ...P  stands for:

P ( 1 + 10n + 102n + 103n + 104n + ... )

The decadic  metric  makes the bracketed series  converge  to  1/(1-10).

-1 / q   =   P / (10n-1)   =   ...P


(2011-09-20)   p-adic Roots of a Polynomial P
How to turn a root modulo p into a p-adic root.

Example:  Solving  x2 + 1  =  0   in p-adic integers.

That equation has a root modulo an  odd prime  p  if and only if  p  is congruent to  1  modulo 4.  One way to establish this is to partition all  p-1  nonzero elements into sets of the form  {x,-x,1/x,-1/x}.

There are k such disjoint sets with 4 distinct elements and one set consisting of the two roots  {-1,+1}  of  x2-1.  There may also be another set of two elements, formed by the roots of  x2+1.  If p-1 is 4k+4, such roots must therefore exist, otherwise  (p-1 = 4k+2)  they cannot.

In particular, the roots modulo  5  of   x2+1   are the two residues  2  and  3.  The general reasoning presented below shows that one root is the pentadic integer  i  whose residue  in  modulo 5n  is iteratively defined as follows  (the other pentadic root is, of course, -i):

i1 = 2             in+1   =   { in  +  [ (in ) 2  + 1 ] }  mod 5 n+1

i = ...00301131300030330421304240422331102414131141421404340423140223032431212
-i = ...44143313144414114023140204022113342030313303023040104021304221412013233

In base thirteen, the two roots are  ...A67B41505474036C688101550155  and  ...26518B7C7858C960644BCB77CB78.  (the letters  A, B, C  stand, respectively, for the  digits  ten, eleven, twelve).

Trivia :  The first of the above is called the "ABC" 13-adic integer, because of the somewhat unlikely fact  (a priori, one chance in 27)  that, at some precision  (here, 28 digits)  A, B and C appear only once and in alphabetical order.  The probability that this happens at a precision of 28 digits with a prescribed (nonalphabetical) rightmost digit is less than one chance in 400  (precisely,  C(27,3) 1024/1327 ).  The pattern holds for 5 more digits  (there was less than 1 chance in 892.7 for that):

ABC   =   ...6A69555A67B41505474036C688101550155

That  13-adic integer may be defined as follows:

i1 = 5             in+1   =   { in  +  9 [ (in ) 2  + 1 ] }  mod 13 n+1

To prove that this is a convergent definition of a  13-adic integer, we only need to observe that the right-hand-side of the recurrence is unchanged if we replace  in  by  in + k 13n  for any  k.  Indeed, that substitution transforms the above curly bracket into:

in+1   =   in  +  9 [ (in ) 2  + 1 ]  +  k 13n [ 1 + 18 in + k 13n ]

The second bracket is divisible by 13, since it's congruent, modulo 13, to:

1 + 18 i1   =   1 + 18 . 5   =   91   =   7 . 13   QED

More generally, if  i1  is a root modulo p of x2+1, the n-th residue of a root of that polynomial in p-adic integers can be recursively defined as follows:

in+1   =   { in  +  b [ (in ) 2  + 1 ] }  mod p n+1
where   b   =   bezout ( -2 i1 , p )

Needless to say that the p-adic integer so defined verifies the following equation, so that the bracket  (our original equation)  does vanish:

x   =   x  +  b [ x2 + 1 ]

Conversely, any  p-adic  root is obtained that way.  So, there are as many p-adic roots as there are roots modulo p  (namely 0 or 2, as discussed above).


(2012-08-18)   The real and p-adic vector spaces over the rationals.
There are no (nontrivial)  continuous  linear maps between the two.

The field  Q  of the rational numbers  (consisting of ratios of ordinary integers)  is a subfield of the field  R  of real numbers.  Q  is also a subfield of the field  Qp  of the p-adic numbers introduced above.  Both of those can also be considered vector spaces over the field  Q  (i.e., rationals are  scalars, nothing else is).  The dimension of either space is infinite.

With respect to the scaling by rationals, let's consider a linear function  f  from the p-adic numbers to the reals.  As zero is the image of zero by any linear function, continuity about zero means that:

" e > 0,  $ a > 0,  " x Î Qp ,   ( | x |p < a )   Þ   ( | f (x) | < e )

This fails with  x = y pn  for a large enough  n,  unless  f (y) = 0.  HINT:

| x |p   =   | y |p / pn       and       f (x)   =   pn f (y)   (by linearity over  Q )

Therefore,   f (y) = 0   for every p-adic number  y.

Conversely, the continuity at  0  of a linear function  g  from the reals to the p-adic numbers means that:

" e > 0,  $ a > 0,  " x Î R  ,   ( | x | < a )   Þ   ( | g (x) |p < e )

By considering  x = y / pn  for a large enough  n,  we can establish that  g (y) = 0   for every real  y.  Here is a summary of the awful truth:

Any linear map (with respect to the rationals)
between the p-adic numbers and the real numbers is
  either discontinuous everywhere or zero everywhere.  

We're using the fact that a linear map on a normed space is continuous at any prescribed point if and only if it's continuous at point zero  (the origin).


(2006-02-07)   Helmut Hasse's  Local-Global  Principle
What's true of reals numbers and of all p-adic fields is true of rationals.

A given type of equation is said to obey the  Hasse principle  when every instance has a solution over the rationals if and only if it has a real solution and a solution in p-adic numbers for any prime p.  Signature of Helmut Hasse

In October 1920,  Helmut Hasse (1898-1979) working under Kurt Hensel, the inventor of p-adic numbers,  showed that this principle holds for  quadratic  equations, not only for rational numbers and p-adic numbers but also for any "global" field related to local fields  (the Hasse-Minkowski theorem).

If something like that was true of  cubic  equations,  we could make mincemeat of the  Birch and Swinnerton-Dyer conjecture  for which the  Clay Mathematical Institute  has posted a  bounty  of one million dollars!

Hasse principle (local-global principle)   |   Hasse-Minkowski theorem


S N Roy from India (2006-05-08; e-mail)   Rotating Digits
Is there a positive integer which doubles in value when its leading digit is transferred to its right end?   [Like when 12345 becomes 23451.]

No.  Such an n-digit integer  (n>1)  would be of the form   d 10n-1 + y  where  d  would be a single-digit  nonzero  number, and  y  an (n-1)-digit number such that:

2 (d 10n-1 + y )   =   10 y  +  d
Which is to say:   [2´10n-1-1] d   =   8 y   =   23 y

Since the square bracket is an odd number,  2 must divide the other factor (d).  Being a nonzero single-digit number, d  must be equal to 8.  Therefore, y is equal to the bracket and  cannot  be an (n-1)-digit number, as required.  (The bracket has n digits; it's 19 for n=2, 199 for n=3, 1999 for n=4, etc.)  QED

Solutions may exist in  nondecimal  numeration.  The simplest example is in base 5, where  31 is twice 13  (in other words, sixteen is two times eight).

On 2006-05-08, S N Roy wrote:       [edited summary]
Great help, and what a short response time!  I am amazed and grateful for the clarity of the exposition...  [continued below]

General discussion, for any base of numeration...

Let's use this opportunity to present a complete example of the mathematical discovery process, where a regular pattern is ultimately found by studying apparent chaos and generalizing particular cases.  For educational purposes, we've left in place  all  the scaffolds that we actually used in the process, including the numerical examples...

There are no solutions in base 2, since putting a nonzero bit rightmost yields an  odd  number, which can't be the double of anything.  There are no solutions either for bases of the form 2k+2  (because of the argument given above in the decimal case, which corresponds to k=3).  As we'll see later, those bases are the only ones for which there are no solutions  (2, 3, 4, 6, 10, 18, 34, 66 ... A056469).

Now, observe that if we have a solution (like 13 in base 5) we obtain  another  solution by duplicating the digits in that solution several times consecutively:  13, 1313, 131313, etc.  Thus, beyond ordinary integers, another solution is clearly the periodic 5-adic integer ...13131313131313.  To any finite solution in base g would correspond such a periodic g-adic integer which is the solution of a  linear  equation in x, involving only one parameter, namely the "leading" digit  d  of the periodic pattern  (d = 1 in the above example)  irrespective of its length:

2 x   =   g x + d

With  g = 5,  we have only 5 possibilities for  d  (namely:  0,1,2,3,4).  Each yields a unique solution in 5-adic integers, namely:

0,  -1/3,  -2/3,  -1  and  -4/3

However, we may rule out  d = 0  if we're only interested in nonzero solutions.  Also, the larger leading digits  (3 and 4)  need not be considered at all, since they make the double of an ordinary integer have an additional digit...  Now, the case  d = 2  yields the pentadic number  -2/3 = ...31313131  for which "2" is not the leading digit of the period  (it's  nowhere  in the period).  Therefore, only the possibility  d = 1  remains, corresponding to the family of solutions already described  (a finite number of repetitions of the two digits "13")  which is thus established to include all solutions in base 5 for ordinary integers.

More generally, this g-adic approach reduces the problem in base g to the simple examination of only  (g-1)/2  g-adic cases.  Here are the results for small bases:

Integers which are doubled by rotating their digits one place to the left.
Bases are expressed in decimal.  Digits for bases beyond ten are: A=ten, B=eleven, C=twelve, etc.
BaseElementary Digit Patterns  (each may be duplicated several times)
5 13
7 1254     2541
8 25
9 125     251     376
11 124986     249861    37     498612
12 2497     4972
13 12495BA837, 2495BA8371, 3712495BA8, 495BA83712, 5BA8371249
14 49
15 124936DCA5B8, 24936DCA5B81, 36DCA5B81249
4936DCA5B812, 5B8124936DCA, 6DCA5B812493
16 249     492     6DB
17 1249     2491     36DA     4912     5B     6DA3     7FEC
19 1248HGEA, 248HGEA1, 36D7FC5B, 48HGEA12
5B36D7FC, 6D7FC5B3, 7FC5B36D, 8HGEA124
20 248HFB     48HFB2     6D     8HFB24
21 1248HE7F9JIGC36D5B, 248HE7F9JIGC36D5B1, 36D5B1248HE7F9JIGC, 48HE7F9JIGC36D5B12, 5B1248HE7F9JIGC36D, 6D5B1248HE7F9JIGC3, 7F9JIGC36D5B1248HE, 8HE7F9JIGC36D5B124, 9JIGC36D5B1248HE7F
22 48HD     8HD4
23 1248HC, 248HC1, 36D, 48HC12, 5ALKIE,
6D3, 7F, 8HC124, 9JG, ALKIE5
24 248HALJF6D, 48HALJF6D2, 6D248HALJF, 8HALJF6D24, ALJF6D248H
25 1248H9JE36D, 248H9JE36D1, 36D1248H9JE, 48H9JE36D12, 5ALIBNMKG7F, 6D1248H9JE3, 7F5ALIBNMKG, 8H9JE36D124, 9JE36D1248H, ALIBNMKG7F5, BNMKG7F5ALI
26 8H

There's a two-digit solution (namely, ug+2u+1) only for bases g of the form  3u+2.

This two-digit pattern is the  only  solution when  g = 3´2k+2  (i.e., 5, 8, 14, 26, 50, 98, 194, 386, 770, 1538, 3074, 6146, ...) because the argument given in the decimal case can be modified to prove that the leading digit  d  must be  2k.

For g = 5 u + 2, we find 2 four-digit patterns:  (u,2u,4u+1,3u+1) and (2u,4u+1,3u+1,u) which are the only solutions if  u = 2k.  (g = 7, 12, 22, 42...)

For g = 7 u + 2, there are 3 three-digit patterns:  (u,2u,4u+1),  (2u,4u+1,u) and (3u,6u+1,5u+1).  These are the only solutions if  u = 2k.  (g = 9, 16, 30...)

For g = 9 u + 2, we find the aforementioned two-digit solution  (3u,6u+1) and 3 other six-digit patterns:  (u,2u,4u,8u+1,7u+1,5u+1), (2u,4u,8u+1,7u+1,5u+1,u), (4u,8u+1,7u+1,5u+1,u,2u).  That's all there is if  u = 2k.  (g = 11, 20, 38, 74...)

With g = 11 u + 2, we have:  (u,2u,4u,8u+1,5u,10u+1,9u+1,7u+1,3u,6u+1)  and the rotations thereof which put a "multiple of u" in the lead...

Let's generalize all this to draw the complete picture:

Number of basic digit patterns whose value doubles with a left rotation  :
In base  g = (2m+1) 2k + 2,  there are  exactly  m  nonzero solutions, each corresponding to a leading digit  d = i 2k,  for i between 1 and m.

Proof :   First, we remark that an argument similar to the one we gave for the decimal case easily establishes that there cannot be any other leading digits:

We must solve   2 (d gn-1 + y )  =  g y  +  d   for an integer  y < gn-1.  This means that   [2 gn-1-1] d  =  (2m+1) 2k y   which implies  d = i 2k  (since the square bracket is odd).  As the positive integer  i  is no more than the expression   (2m+1) (gn-1-1) / [2 gn-1-1]  it's between 1 and m.

Conversely, there can only be one solution for each such i,  corresponding to  x = -i/(2m+1)  which is indeed a (periodic) g-adic integer because g and 2m+1 are coprime.  The tricky part is to check that this potential solution always has the correct "leading digit".  To do this, we'll establish an interesting  explicit  formula for the digits in a "unit" pattern  (from which all others solutions are derived)...

Without loss of generality, we may assume  i = 1, since the g-adic integers for the other cases are obtained by multiplying this basic one by  i.

Incidentally, such products may feature a shorter period, as with the case  g = 11, i = 3  (this can't happen if  2m+1  is prime, though).

Let  u  be  2k.  We have  g  =  (2m+1)u+2.  The leading digit (d) is u.  Twice the rightmost digit is thus either  u  or  g+u,  but the former is ruled out (even if k > 0) as we consider only  i = 1, which puts the  least possible power of two in the lead  (if a carry wasn't involved in the doubling of the rightmost digit, the pattern rotated right would be a solution with a smaller power of two in the leading position).  Therefore, the rightmost digit is  d0 = (m+1)u+1.  The periodic pattern is:

d = dn-1 = u + 0 ,     ...     dj = aj u + bj     ...     d0 = (m+1)u + 1

In this,  bj  is either 0 or 1   (bn-1  is zero and so is  bn-2  unless  g = 5).  The key observation is that  aj  is simply congruent to  2aj+1   modulo (2m+1)  whereas  bj  is equal to 1 if and only if  aj  is greater than m  (yeah, same subscript  j ).

Using this formula, whose validity is established below, we may remark that the length  n  of this "unit" pattern (the longest in base g) is simply the multiplicative order of  2  modulo (2m+1)  which implies (incidentally) that the period  n  is at most equal to g-3.  Note that the reciprocal of 2 modulo (2m+1)  is the coefficient (m+1)  which appears in the expression of the rightmost digit  d0.

Checking the validity of the above explicit formula :

Calling  cj  the "carry" (0 or 1) injected at rank  j  in the doubling operation, we'll have proved that the value is doubled by the proper rotation of the digits if we establish the following relation  (valid for  j = 0  if we put  d-1 = d  and c0 = 0 ).

2 dj + cj   =   dj-1 + g cj+1

Since  cj+1 = bj  this very relation results from the following case-splitting:

  • If  aj  is greater than m, then  aj-1  is not:   bj = 1 = cj+1  and  bj-1 = 0 = cj
    2 aj u + 2 bj + cj   =   (aj-1 + 2m+1 ) u + 2   =   aj-1 u + bj-1 + g cj+1
  • Otherwise, bj = 0 = cj+1  and  bj-1 = cj.  Therefore:
    2 aj u + 2 bj + cj   =   aj-1 u + bj-1   =   aj-1 u + bj-1 + g cj+1

The final check was easy, but  deriving  this simple formula was murder!   QED

On 2006-05-08, S N Roy wrote:       [continued from above]
What about decimal numbers which the same transformation cuts in half?  I believe there are only 9 such numbers. Am I right?

In  periodic  decadic integers, there are clearly 10 solutions  (9 of which are nonzero) to the corresponding set of equations (where d is a single decimal digit):

x   =   2 (10 x + d)

The solutions for  x  are equal to the (nonzero) digit  d  multiplied by :

-2/19 = ...05263157894736842105263157894736842105263157894736842105263157894736842

The periodic decimal pattern  105263157894736842  yields a solution in ordinary integers, as do its first nine nonzero multiples  (there's no "overflow" because the pattern starts with "10").

105263157894736842
210526315789473684
315789473684210526
421052631578947368
526315789473684210
631578947368421052
736842105263157894
842105263157894736
947368421052631578

For each such 18-digit solution, we have infinitely many solutions of  18 n  digits, like  105263157894736842105263157894736842.  (A217592)

Again, since any solution in ordinary integers would yield a periodic 10-adic integer satisfying a linear equation of the above type, we  know  that there are no nonzero solutions in ordinary integers outside of those 9 infinite families.

The g-adic approach does solve this type of specific puzzles very quickly.  As illustrated above, it's also a solid foundation for general discussions.

(2012-10-28)  Epilog:

In April 2009,  N.J.A. Sloane et al.  (see A146088)  considered the related problem of doubling a decimal number by rotating it to the right  (12345 would become 51234).

The solutions of that problem are clearly obtained by rotating our 9 previous patterns one place to the left,  except  when this yields a leading zero digits  (052631578947368421 is disallowed).

Therefore, there are only  eight  18-digit solutions  (and thus only 8 infinite families of solutions obtained by repeating each such decimal pattern any number of times). 

105263157894736842
157894736842105263
210526315789473684
263157894736842105
315789473684210526
368421052631578947
421052631578947368
473684210526315789

Sorting those in increasing order hides some of the regularity which we found in the "reverse" problem discussed above  (arguably, the better one).  The consecutive digits  2,3,4,5,6,7,8,9  do appear consecutively in that sorted list but they are now in the leftmost position and "1" is missing  (both remarks are trivial with the way we obtained the solutions, they might not be with a more "direct" approach).  Again, the true regularity comes from the decadic discussion.  Obtaining decimals from decadics destroys the utter simplicity.


(2012-10-29)   Integers that are divided by k by rotating their digits left.
For example 102564 becomes 025641 which is exactly one fourth of it.

For any k, the solutions have the structure, discussed above for  k = 2.  The decadic equations to solve, for any digit d from 0 to 9, are:

x   =   k (10 x + d)

Each of the 10 decadic solutions,   x  =  -d k / (10k-1)   yields solutions in rational integers  (infinitely many for the nonzero values of d).

If  P  is the decadic period of  -k/(10k-1)  (which is the decimal period of the ordinary fraction  k/(10k-1)  incidentally)  then the first 10 solutions are the first ten multiples of P  (nP for n between 0 and 9).  These form ten families of solutions:  The singleton  {0}  and 9 infinite families obtained by repeatingumber of times" may, arguably, include "zero times" which yields the empty string...  The empty string is the proper decimal representation of zero if you strictly enforce the rule that 0 cannot be a leading digit.  Needless to say that we usually use a single "0" digit when there's a need to write something down.  However, some decimal or binary computer representations of long integers may accurately reflect the fact that zero has no significant digits  (and/or zero significant bits).

For example, the numbers that are divided by 4 in a single left-rotation of their decimal digits include 0, the number 102564 multiplied into 1,2,3,4,5,6,7,8,9 and any of those multiplied into (106k-1)/(106-1)  for any positive k.  So, all the solutions are easy to derive from the smallest positive one, tabulated below:

n-digit Decimal Period  P  of   k / (10k-1)   =   P / (10n-1)
kA128857(k)   =   Decimal Period of  k/(10k-1) OEIS n
00 0
11 A010785 1
2105263157894736842A21759218
31034482758620689655172413793 28
4102564 6
5102040816326530612244897959183673469387755 42
6 101694915254237288135593220338983050847457627118644067796658
71014492753623188405797 22
81012658227848 13
910112359550561797752808988764044943820224719 44
1010 2

The table is infinite.  It goes on  (k=11)  with the 108-digit period of 11/109:

100917431192660550458715596330275229357798165137614678899082568807339449541284403669724770642201834862385321

Then we have:

12/119  =  0.100840336134453781512605042016806722689075630252...
13/129  =  0.100775193798449612403...
14/139  =  0.1007194244604316546762589928057553956834532374...
etc.  (The next one has 148 digits.)

The length  (n)  of the decimal period of  k / (10k-1)   is  A128858(k):

[a(0)=0]  1, 18, 28, 6, 42, 58, 22, 13, 44, 2, 108, 48, 21, 46, 148, 13, 78 ...

border
border
visits since February 6, 2006
 (c) Copyright 2000-2020, Gerard P. Michon, Ph.D.