(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:
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
anmodulo 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 notcountable.
(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.)
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)
2
3
5
6
7
10
11
g-adic
dyadic
triadic
pentadic
hexadic
heptadic
decadic
hendecadic
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-gonsunless 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 | xn ).
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 :
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)
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:
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:
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
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, x2 + x + 8 = 0 has no real solutions,
but four decadic ones:
Note that u is divisible by any power of 5
(since (u/5)n = u/5n )
just like 1-u is divisible by any power of 2
(since ((1-u)/2)n = (1-u)/2n ).
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:
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)
1
2
5
10
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:
= 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:
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 pm ,
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 Qp 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:
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...
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).
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 !
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 | p < 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 | p < 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 = a1b1 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:
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-10n ).
-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
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
of the rational numbers (consisting of ratios of ordinary integers)
is a subfield of the field
of real numbers.
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
(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, unlessf (y) = 0. HINT:
| x |p = | y |p/ pn
and
f (x) = pnf (y)
(by linearity over
)
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 Î
,
( | 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.
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!
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, 23
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.)
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).
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.
Base
Elementary Digit Patterns
(each may be duplicated several times)
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!
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 periodicdecadic 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 :
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").
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).
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)
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):