A puzzle involving $10$-adic numbers

Solution 1:

I saw this observation in a math book once when I was 16 or so and was totally baffled at the time. It's nice to know I understand it now!

As you say, the starting point is to use CRT, which allows us to write $\mathbb{Z}_{10} \cong \mathbb{Z}_2 \times \mathbb{Z}_5$, so we can work in the $2$-adics and $5$-adics separately. It's easy to understand what happens to the powers of $5$ in $\mathbb{Z}_5$: they converge to zero. Similarly for the powers of $2$ in $\mathbb{Z}_2$. The tricky question is about the powers of $5$ in $\mathbb{Z}_2$ and the powers of $2$ in $\mathbb{Z}_5$.

Here, as you also say, the starting point is that by Fermat's little theorem we have $x^p \equiv x \bmod p$. So at least the first digit $\bmod p$ stabilizes. What can we say about taking further iterations $\bmod p^2, p^3$, etc.?

Theorem (existence of the Teichmuller character): Let $p$ be a prime and let $x \in \mathbb{Z}_p$. The sequence $x, x^p, x^{p^2}, \dots$ converges and its limit $\omega(x)$, the Teichmuller character of $x$, is the unique solution to $\omega(x)^p = \omega(x)$ which is congruent to $x \bmod p$.

Proof. This sequence always lies in the subspace $S_x$ of $\mathbb{Z}_p$ consisting of elements congruent to $x \bmod p$. It suffices to show that on this subspace, the Frobenius map $F(x) = x^p$ is a contraction in the $p$-adic metric so we can apply the Banach fixed point theorem. In other words, we want to show that there exists some constant $c < 1$ such that for all $a, b \in S_x$ we have

$$|a^p - b^p|_p \le c |a - b|_p.$$

This follows from a contest math result called lifting the exponent although we won't need its full strength so we can settle for only part of the proof. Since by assumption $a \equiv b \bmod p$, we can argue as follows: write

$$\frac{a^p - b^p}{a - b} = a^{p-1} + a^{p-2} b + \dots + b^{p-1}.$$

This sequence has $p$ terms and each term is congruent to $a^{p-1} \equiv b^{p-1} \bmod p$, so their sum is congruent to $0 \bmod p$. So $a^p - b^p$ is divisible by at least one more power of $p$ than $a - b$ is, which means the Frobenius map is a contraction with $c = p^{-1}$.

Applying the Banach fixed point theorem we conclude that the sequence $x, F(x), F^2(x), \dots $ converges to a unique fixed point $\omega(x)$ in $S_x$: this means precisely that $\omega(x) \equiv x \bmod p$ and $\omega(x)^p = \omega(x)$ and that $\omega(x)$ is unique with respect to these two properties. (Alternatively this existence and uniqueness result can also be deduced from Hensel's lemma.) $\Box$

This means that the Teichmuller character provides a canonical splitting of the map $\mathbb{Z}_p^{\times} \to \mathbb{F}_p^{\times}$ on groups of units, allowing us to construct the $(p-1)^{th}$ roots of unity in $\mathbb{Z}_p$ surprisingly explicitly.

Applying the theorem, we get:

• The sequence $5, 5^2, 5^4, \dots $ converges in $\mathbb{Z}_2$ to the unique solution to $\omega(5)^2 = \omega(5)$ congruent to $1 \bmod 2$, which is $1$. In other words, the sequence converges in $\mathbb{Z}_{10} \cong \mathbb{Z}_2 \times \mathbb{Z}_5$ to $(1, 0)$, which is precisely the idempotent projecting from $\mathbb{Z}_{10}$ down to $\mathbb{Z}_2$.
• The sequence $2, 2^5, 2^{25}, \dots$ converges in $\mathbb{Z}_5$ to the unique solution to $\omega(2)^5 = \omega(2)$ congruent to $2 \bmod 5$, which is one of the two primitive $4^{th}$ roots of unity. In other words, the sequence converges in $\mathbb{Z}_{10} \cong \mathbb{Z}_2 \times \mathbb{Z}_5$ to an element you might call $(0, i)$.

Now we of course have $(1, 0) \cdot (0, i) = (0, 0)$. The fun part is that if we take the fourth power of $(0, i)$, getting the limit of the sequence $16, 16^5, \dots$, we get $(0, 1)$, which is the idempotent projecting from $\mathbb{Z}_{10}$ down to $\mathbb{Z}_5$, and it satisfies $(0, 1)^2 = (0, 1)$ and $(0, 1) + (1, 0) = (1, 1)$; in other words, if we know the digits of $(1, 0) = \dots 90625$ we can compute the digits of $(0, 1)$ by just subtracting from $1$, which gives

$$\lim_{n \to \infty} 16^{5^n} = \dots 09376 = 1 - \lim_{n \to \infty} 5^{2^n}$$

and you can check this on a calculator!

What this says in other words is that these two limits, which somewhat abusing notation I'll call $\omega(5)$ and $\omega(16)$, give a canonical decomposition of any $10$-adic number into two components

$$x = \omega(5) x + \omega(16) x$$

where the first component is $5$-adically zero and gives the $2$-adic component of $x$ and the second component is $2$-adically zero and gives the $5$-adic component of $x$.

(You may be familiar with a certain explicit proof of CRT that constructs idempotents like these to show, for example, that $5x + 6y$ is an explicit number congruent to $x \bmod 2$ and $y \bmod 5$; this construction gives a compatible family of such idempotents $\bmod 10^n$ for all $n$.)

Solution 2:

This is fun stuff. Let me try to contribute something without getting egg on my face.

The fact is, that if you write $\Bbb Z_{10}$ for the ten-adic numbers, then $\Bbb Z_{10}\cong\Bbb Z_2\oplus\Bbb Z_5$. In the direct sum on the right, you have both addition and multiplication coordinatewise, i.e. for $a,a'\in\Bbb Z_2$, two-adic integers and $b,b'\in\Bbb Z_5$, five-adic integers, the two rules $(a,b)+(a',b')=(a+a',b+b')$ and $(a,b)(a',b')=(aa',bb')$.

Best way to show this is to find a pair of orthogonal idempotents in $\Bbb Z_{10}$ adding up the the multiplicative identity of the direct sum. More precisely, you want $e_2,e_5\in\Bbb Z_{10}$ satisfying $e_i^2=e_i$ for $i=2,5$ and also $e_2+e5=1$, $e_2e_5=0$. And then you show that $e_2\Bbb Z_{10}\cong\Bbb Z_2$, $e_5\Bbb Z_{10}\cong\Bbb Z_5$, and the isomorphism is $z\mapsto(e_2z,e_5z)$.

You can get successive approximations to $e_2$ by using Chinese Remainder to find solutions to $e_{2,n}\equiv1\pmod{2^n}$, $e_{2,n}\equiv0\pmod{5^n}$. Then automatically, the corresponding $e_{5,n}$ will be $10^n+1-e_{2,n}$.

To four ten-adic places, these seem to be $e_2=\dots625$, $e_5=\dots9376$.

Now: how does this relate to what you found? There’s a theorem for the $p$-adic numbers that if $v_p(z-1)=m$, then $v_p(z^p-1)=m+1$. Here, $v_p(z)=k$ means that $p^k$ is the highest power of $p$ dividing $z$. That is, taking the $p$-th power of something ($p$-adically) close to $1$ gets you closer, but by only one step. You started with $5$, which has $v_2(5-1)=2$, and squared, to get $v_2(25-1)=3$. Squaring $25$, you got $v_5(625-1)=4$. For $z=2$, you recognized that you needed to take successive $5$-th powers. But you started with something incongruent to $1$ mod $5$, so the Theorem didn’t quite apply. If you had started with $16$ instead, then $v_5(16-1)=1$, $v_5(16^5-1)=v_5(1048576-1)=2$, etc. As I said in my comment above, this is not as it stands an efficient way of getting successive approximations to $e_2$ and $e_5$.

The way to make the above process more efficient is to throw away digits too far to the left. Working with successive squaring of $5$, once you square $625$, square it and throw away everything to the left of the $9$: $90625^2=\dots890625$. Square $890625$ and again throw away some, getting $\dots2890625$, etc. You’re not putting excess strain on your calculator (or your eyes), and you give up when you get to $e_2=\dots259918212890625$. Now just take the nines complement of that and add two to get $\dots740081787109376$ for your $e_5$. Of course these are complementary, i.e. add to $1$ modulo the proper power of $10$, and you might want to check that this approximation to $e_5\equiv e_5^2$ modulo that power of $10$ too, and that $e_2e_5\equiv0$. I did, and they’re all right.