Related Links (Outside this Site)

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

---

(2006年02月06日) Z_p : 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 a_n modulo pⁿ
(n > 0) in which a_n+1 is congruent to a_n modulo pⁿ.

The quantity a_n 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 pⁿ.

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 a₁ is nonzero, the p-adic integer A = (a_n ) is said to be invertible because it has a reciprocal which is also a p-adic integer. (HINT: In this case, a_n has an inverse modulo pⁿ.)

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:

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:

u_n = q^pn mod (pq)ⁿ [ note that u^p = u ]
v_n = p^qn mod (pq)ⁿ [ note that v^q = 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...

x² = 0 never has any nonzero solution in g-adic integers (thus, the equation (x-a)² = 0 has only one solution). There are no (nonzero) nilpotent g-adics; a power of a nonzero g-adic integer is never 0 (HINT: g^kn | x_n^k implies gⁿ | x_n ).

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)]^k ).

---

(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 :

u₁ = 5 u_n+1 = (u_n ) ² mod 10 ⁿ⁺¹

An induction on n would show that u_n+1 is, indeed, of the form k 10ⁿ + u_n (HINT: 2ku_n 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 ² = 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 x² = 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 ³ = 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.

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

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

Each such solution verifies x⁵ = x (as it makes x(x²+1)(x²-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 v₁ is even).

v₁ = 2 v_n+1 = (v_n ) ⁵ mod 10 ⁿ⁺¹

We may remark that uv = 0 and u = 1 + v ². In the jargon of recreational mathematicians, the solutions of x ⁵ = 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 xⁿ = 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) ] ² = (a-b) ²

A 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, x² + 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)ⁿ = u/5ⁿ ) just like
1-u is divisible by any power of 2 (since ((1-u)/2)ⁿ = (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 x² = 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 ² = 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 ² - 1
= 2 x 37 ² - 1
= 2 x 937 ² - 1
= 2 x 5937 ² - 1
= 2 x 35937 ² - 1
= 2 x 335937 ² - 1
= 2 x 9335937 ² - 1
= 2 x 19335937 ² - 1
= 2 x 319335937 ² - 1
= 2 x 7319335937 ² - 1
= 2 x 77319335937 ² - 1
= 2 x 877319335937 ² - 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 ² - 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) ² - 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日) Q_p : 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^m , 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 pⁱ 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_p complete (i.e., every Cauchy sequence converges in it).

Assuming q_m 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 = pⁿ (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: | ¹²/₇ | ₂ = ¼ | ¹²/₇ | ₇ = 7 | ¹²/₇ | ₅ = 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 p^m, 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 - x₁ | _p < 1 and x_n+1 = ( 2 - a x_n ) x_n

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 x_n (the minuend cancels the subtrahend's first term).

| 1/a - x₁ | _p < 1 and x_n+1 = (1/a) - a^k-1 (1/a - x_n ) ^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 | a^k-1 |_p = 1) the quantity | 1/a - x_n |_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 a_n and b_n are the residues modulo pⁿ of a and its reciprocal, then :

1 = a₁ b₁ mod p b _2n = ( 2 - a _2n b_n ) b_n mod p²ⁿ

---

(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 10ⁿ-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 = (10ⁿ-1) / q which does yield:
1 / q = P / (10ⁿ-1) = 0.P...

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

P ( 1 + 10ⁿ + 10²ⁿ + 10³ⁿ + 10⁴ⁿ + ... )

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

-1 / q = P / (10ⁿ-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 x² + 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 x²-1. There may also be another set of two elements, formed by the roots of x²+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 x²+1 are the two residues 2 and 3. The general reasoning presented below shows that one root is the pentadic integer i whose residue i_n modulo 5ⁿ is iteratively defined as follows (the other pentadic root is, of course, -i):

i₁ = 2 i_n+1 = { i_n + [ (i_n ) ² + 1 ] } mod 5 ⁿ⁺¹

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) 10²⁴/13²⁷ ). 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:

i₁ = 5 i_n+1 = { i_n + 9 [ (i_n ) ² + 1 ] } mod 13 ⁿ⁺¹

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 i_n by i_n + k 13ⁿ for any k. Indeed, that substitution transforms the above curly bracket into:

i_n+1 = i_n + 9 [ (i_n ) ² + 1 ] + k 13ⁿ [ 1 + 18 i_n + k 13ⁿ ]

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

1 + 18 i₁ = 1 + 18 . 5 =わ 91 =わ 7 . 13 QED

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

i_n+1 = { i_n + b [ (i_n ) ² + 1 ] } mod p ⁿ⁺¹
where b = bezout (-2 i₁ , 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 [ x² + 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 Q_p 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 Î Q_p , ( | x |_p < a ) Þ ( | f (x) | < e )

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

| x |_p = | y |_p / pⁿ and f (x) = pⁿ 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 / pⁿ 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 10^n-1 + y where d would be a single-digit nonzero number, and y an (n-1)-digit number such that:

2 (d 10^n-1 + y ) = 10 y + d
Which is to say: [2´10^n-1-1] d = 8 y = 2³ 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 2^k+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:

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´2^k+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 2^k.

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 = 2^k. (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 = 2^k. (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 = 2^k. (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) 2^k + 2, there are exactly m nonzero solutions, each corresponding to a leading digit d = i 2^k, 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 g^n-1 + y ) = g y + d for an integer y < g^n-1. This means that [2 g^n-1-1] d = (2m+1) 2^k y which implies d = i 2^k (since the square bracket is odd). As the positive integer i is no more than the expression (2m+1) (g^n-1-1) / [2 g^n-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 2^k. 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 d₀ = (m+1)u+1. The periodic pattern is:

d = d_n-1 = u + 0 , ... d_j = a_j u + b_j ... d₀ = (m+1)u + 1

In this, b_j is either 0 or 1 (b_n-1 is zero and so is b_n-2 unless g = 5). The key observation is that a_j is simply congruent to 2a_j+1 modulo (2m+1) whereas b_j is equal to 1 if and only if a_j 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 d₀.

Checking the validity of the above explicit formula :

Calling c_j 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 c₀ = 0 ).

2 d_j + c_j = d_j-1 + g c_j+1

Since c_j+1 = b_j this very relation results from the following case-splitting:

• If a_j is greater than m, then a_j-1 is not: b_j = 1 = c_j+1 and b_j-1 = 0 = c_j
  2 a_j u + 2 b_j + c_j = (a_j-1 + 2m+1 ) u + 2 = a_j-1 u + b_j-1 + g c_j+1
• Otherwise, b_j = 0 = c_j+1 and b_j-1 = c_j. Therefore:
  2 a_j u + 2 b_j + c_j = a_j-1 u + b_j-1 = a_j-1 u + b_j-1 + g c_j+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 (10^6k-1)/(10⁶-1) for any positive k. So, all the solutions are easy to derive from the smallest positive one, tabulated below:

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

100917431192660550458715596330275229357798165137614678899082568807339449541284403669724770642201834862385321

Then we have:

¹²/₁₁₉ = 0.100840336134453781512605042016806722689075630252...
¹³/₁₂₉ = 0.100775193798449612403...
¹⁴/₁₃₉ = 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 ...