Small lemma on moving up multiplicative inverses of powers needs explanation

Question

I am reading about a lemma that shows how to lift up a multiplicative inverse. I.e. if we know that $3\cdot 3 \equiv 1 \pmod {2^3}$ then we know that $3\cdot 43 \equiv \pmod {2^6}$
To go from $\pmod {2^3}$ to $\pmod {2^6}$ we use the formula:
if $xy \equiv 1\pmod {p^e}$ then $xz \equiv 1\pmod {p^{2e}}$ where $z = y- yrp^e$ and $r$ is the from $xy = 1 + rp^e$
There are two parts I don't understand and would like some help.

1. First of all, is such a proof usually "discovered" from the result? I mean if I work backwards and replacing I can see that I can get back to $xy \equiv 1 \pmod {p^e}$.
   And I can apply the formula to solve a problem of this type. But I don't have any intuitive "feel" of that $y- yrp^e$ that we multiply $x$ instead of $y$ to move to the higher power i.e. from $p^e$ to $p^{2e}$. Is there a way to understand this better?
2. The lemma as part of the steps/proof sates that:

We need a $z \equiv y \pmod {p^e} \implies z = y + tp^e$ and we need $xz \equiv 1\pmod {p^{2e}} \implies x(y + tp^e) \equiv 1 \pmod > {p^{2e}}$. Since $xy = 1 + rp^e$ we know that $1 + rp^e + xtp^e \equiv > 1 \pmod {p^{2e}}$. Since $xy \equiv 1 \pmod p^e$ setting $t = -yr$ solves the congruence

The last sentence is what I don't understand. We want to solve $1 + rp^e + xtp^e \equiv 1 \pmod {p^{2e}} \implies 1 + (r + xt)p^e \equiv 1 \pmod {p^{2e}}$
But $xy \equiv 1$ in $\pmod p^e$ and not by $\pmod {p^{2e}}$so how can we solve it like it says using the inverse?

Answer 1

If $t=-yr$ then $$1+rp^e+xtp^e=1+rp^e+(x(-yr))p^e= 1+rp^e-rp^e$$ that's the last line explained .

Answer 2

So, the multiplicative inverses are special and unique for fields. The multiplicative inverse of $3$ in $\mathbb{Z}_{2^3}$ is $3$ since $3\cdot 3 \equiv_8 1$. 3 is it's own inverse, an idempotent.

Now when you "lift" the power $3$ is no longer it's own inverse. This is because we have "more room". $3\cdot 3 = 9$ and in $\mathbb{Z}_{2^6}$ we have $9 \not\equiv_{2^6} 1$.

So the equation $3\cdot 3 \equiv_{2^6} 1$ is false(and it is clear since it is $9$).

So you have to find the multiplicative inverse of 3. What is it in now? $3x \equiv_{2^6} 1$. Solve for $x$. What is $x$? $x = \frac{1}{3}$. But we have no fractions in $\mathbb{Z}$! Well, lets write it nicer $x = 3^{-1}$. Clearly then $3\cdot 3^{-1} = 1$.

Well, $\mathbb{Z}_{2^3}$ relates to $\mathbb{Z}_{2^6}$ and so you can use information about each to help with figuring out stuff from the other. They actually relate quite nicely.

Remember in $\mathbb{Z}_{2^3}$ we had $3^{-1} = 3$ but we also have $3^{-1} = 3 + 2^3 k$ for any $k$, clearly. I.e., $3^{-1} \equiv_{2^3} 3 + 2^3 k \equiv_{2^3} 3$

When we "lift" the exponent we end up reducing the possible $k$ values, it can't be any $k$ value any more like it was. Now we have $3^{-1} \equiv_{2^6} 3 + 2^3 k$ and this equation isn't true for all $k$ any more.

BUT we still have $3\cdot 3^{-1} = 1$ and so $3\cdot 3^{-1} = 3\cdot(3 + 2^3 k) = 9 + 3\cdot 2^3k$ and we want this to be true for $\mathbb{Z}_{2^6}$ so we have $9 + 3\cdot 2^3k \equiv_{2^6} 1$.

But this is the thing, what I've said also hold true for $\mathbb{Z}_{2^4}$ and $\mathbb{Z}_{2^5}$. They too will have $3^{-1}$ as multiplicative inverses. It is 11 in both because $3\cdot 11 = 33 \equiv_{2^{4|5}} 1$. This further limits the possibilities of $k$ all down to 1. In fact, it is always 1 possibility.

Effectively we have the equations

$3\cdot 3^{-1} = 3\cdot(3 + 2^3 k_1) \equiv_{2^3} 1$

$3\cdot 3^{-1} = 3\cdot(3 + 2^3 k_2) \equiv_{2^4} 1$

$3\cdot 3^{-1} = 3\cdot(3 + 2^3 k_3) \equiv_{2^5} 1$

$3\cdot 3^{-1} = 3\cdot(3 + 2^3 k_4) \equiv_{2^6} 1$

But all those $k_i$'s are connected since $k_{j+1} \not= 2^m k_j$ where m would make the result invalid. E.g., $k_2\not= 2k_1$ else we could have $9 \equiv_{16} 1$ which is invalid. So ultimately a system of equations results with a unique solution and this solution will ultimately give us the multiplicative inverse in the "lifted" field.

As you can easily see the inverses are $3, 11, 11, 42$ or $3, 3 + 2^3, 3 + 2^3, 3 + 2^3 + 2^5$. Those $2^m$'s are annihilated when we modulo by $2^{<m}$. Since 2^4 is missing we end up with the same inverse. As you lift up you will get a series for $3^{-1} = 3 + \sum b_k 2^k$ and this turns out to be the binary expansion of $\frac{1}{3}$. It almost could be nothing else!

So $\mathbb{Z}_{p^m}$'s inverses essentially are just truncated forms of $\mathbb{Q}$. How nice is that!

Answer 3

First, a non-constructive proof:

Given $xy \equiv_{p^e} 1$ solve for z in $xz \equiv_{p^{2e}} 1$ then

$z = y−yrp^e$ where $xy=1+rp^e$

To show this is true, multiply the first equation by $x$: $xz = xy(1 - rp^e) = (1 + rp^e)(1 - rp^e) = 1 - r^2p^{2e}$

Clearly then $xz \equiv_{p^{2e}} (1 - r^2 p^{2e}) \equiv_{p^{2e}} 1$

This at least shows the formula for $z$ is consistent with what we desire. Note that this equation specifically deals with the square of the power because it's essentially based off the fact that $1 - x^2$ can be factored in to linear factors. (but of course it will work for any $e$ so one can chain this)

This doesn't say why we must choose the specific $r$ though but that should be clear because any $r$ works for the 1st equation but it then must be consistent with the 2nd as not $r$ will work in when we "lift" to the larger module.

So how does one go about finding this?

1. Suppose you know $xy \equiv_{p^e} 1$ and you want to find the $z$ that makes $xz \equiv_{p^{2e}} 1$ true. Well, you have 2 equations with 1 unknown so it should generally have a solution(assuming the first does but we are given it so it must).

2. The first equation is just $xy = 1 + rp^e$ for any $r\in\mathbb{Z}$. Notice, this is your "you must find $r$" part of the condition to find $z$ but here it can be anything, it only gets restricted due to the next step. Note that $r$ is actually a single value once we move outside the module so it is no longer arbitrary in our problem.

3. The second equation says, similarly, $xz = 1 + sp^{2e}$. It should be clear all we have is really the first equation to work with so we must use that. It might not be all that clear why, but clearly if we multiply by $y$ then $yxz = y + ysp^{2e}$. $s$ is arbitrary because we never go outside of $\mathbb{Z}_{p^{2e}}$.

So it should be pretty easy to see that we have

$yxz = (1 + tp^{e})z = y(1 + sp^{2e})$

Notice $yxz$ and how it is special. Depending on how we associate the result we can get to use either of our original equations: $(yx)z = y(xz)$. Associativity(and commutativity) allows us to get two different representations for the same quantity and it's precisely the two representations we have available.

Now we would like to isolate $z$. This can be done quite easily by multiplying by $1 - rp^{e}$,

$(1 - rp^{2e})z = y(1 + sp^{2e})(1 - rp^{e}) = (1 - rp^{e} + sp^{2e} - srp^{3e})y$

But clearly

$z \equiv_{p^{2e}} (1 - rp^{e})y$

which solves for $z$.

So, really, I didn't do anything complex. I used the two original equations, I wrote them in terms of their equivalent expansion. I was able to connect them by simply multiplying the latter by $y$ so I could get the first. I then simply multiplied by the conjugate factor which, because I knew I was going to be in $\mathbb{Z}_{p^{2e}}$ that the factors would cancel out and leave me with a nice representation.

E.g.,

$14\cdot 9 \equiv_{5^3} 1$

$14\cdot z \equiv_{5^6} 1$

$xy = 126 = 1 + r5^3 \rightarrow r = 1$

So $z \equiv_{5^6} 9\cdot (1 - 1\cdot 5^6) \equiv_{5^6} -1116 \equiv_{5^6} 14509$

Or similarly,

$9\cdot 14 \equiv_{5^3} 1$

$9\cdot z \equiv_{5^6} 1$

$xy = 126 = 1 + r5^3 \rightarrow r = 1$

So $z \equiv_{5^6} 14\cdot (1 - 1\cdot 5^6) \equiv_{5^6} -1736\equiv_{5^6} 13889$