# For each $r \in \mathbb Z$ with $0 < r < p$, there exists $m \in \mathbb Z$ such that $mr = 1 + pn$ for some $n \in \mathbb Z$

This is a lemma from my textbook Analysis I by Amann/Escher:

Let $$p$$ be a prime number. Then, for each $$r \in \mathbb Z$$ with $$0 < r < p$$, there exists $$m \in \mathbb Z$$ such that $$mr = 1 + pn$$ for some $$n \in \mathbb Z$$.

My attempt:

By repeated use of Euclidean algorithm, there exist positive numbers $$r_{0}, \ldots, r_{k}$$ and $$q, q_{0}, \ldots, q_{k}$$ such that $$r>r_{0}>r_{1}>\cdots>r_{k} \ge 0$$ and

\begin{aligned} p &= q r &&+ r_0 \\ r &= q_0 r_0 &&+ r_1 \\ r_0 &= q_1 r_1 &&+ r_2 \\ r_k &= q_{k+1} r_{k+1} &&+ r_{k+2} \\ &\mathrel{\vdots} \\ r_{k+1} &= q_{k+2} r_{k+2} \end{aligned}

It follows that $$r_{j}=m_{j} r+n_{j} p$$ for $$j=0, \ldots, k+2$$ with $$m_{j}, n_{j} \in \mathbb{Z}$$.

We prove that $$r_{k+2} = 1$$. If not, $$\overline p \mid r_{k+2}$$ for some prime number $$\overline p$$. Then $$\overline p \mid r_{k+1}$$ and thus $$\overline p \mid r_k$$. By induction, $$\overline p \mid r_0$$ and $$\overline p \mid r$$. As a result, $$\overline p \mid p$$, which is a contradiction.

So $$r_{k+2} = 1 = m_{k+2} r + n_{k+2} p$$ or $$m_{k+2} r = 1 + p(-n_{k+2})$$.

My questions:

1. Does my attempt look fine or contain any logical gaps?

2. Is it possible to generalize this lemma to

Ver1: Let $$p$$ be a prime number. Then, for $$r,r' \in \mathbb Z$$ with $$0 < r,r' , there exists $$m \in \mathbb Z$$ such that $$mr = r' + pn$$ for some $$n \in \mathbb Z$$.

and

Ver2: Let $$p$$ be a positive integer. Then, for $$r,r' \in \mathbb Z$$ with $$0 < r,r' , there exists $$m \in \mathbb Z$$ such that $$mr = r' + pn$$ for some $$n \in \mathbb Z$$.

• Have you ever heard of Bezout's theorem in number theory? – Tom Jun 12 '19 at 7:13

Your lemma is basically fine except for a few small points. Your initial conditions are only for indices up to $$k$$, but you use up to $$k + 2$$. Also, your $$3$$ vertical dots should be up one row. As Fergns indicates, your lemma is related to Bézout's identity.
FYI, what you're basically trying to prove is that, modulo each prime $$p$$, each non-zero integer has a multiplicative inverse. This fairly easy to verify by noting for any $$0 \lt r \lt p$$ that each residue of $$mr$$ among $$0 \lt m \lt p$$ are unique (if not, then if $$m_1r$$ and $$m_2r$$ have the same residue, $$(m_1 - m_2)r$$ must be a multiple of $$p$$, which is not possible). Since there are $$p - 1$$ values of $$m$$ and $$p - 1$$ non-zero residues, then one of them must be $$1$$. For this $$m$$, $$mr \equiv 1 \pmod p$$ means there exists an $$n \in \mathbb{Z}$$ such that $$mr = 1 + pn$$.
As for your first generalization, Ver1, I don't see any way to directly use your lemma to prove what you're asking for. The problem is that you can't generally assume that any of the $$r_j$$ will be the same, or in any way connected, to $$r'$$. However, note that the lemma says that $$mr = 1 + pn$$, so multiplying by $$r'$$ gives $$(mr')r = r' + p(nr')$$, so you can use $$m' = mr' \in \mathbb{Z}$$ and $$n' = nr' \in \mathbb{Z}$$.
With your second generalization, Ver2, the result is not always true. Since $$mr - pn = r'$$, as $$\gcd(r,n)$$ divides the left side, it must divide the right side, i.e., $$\gcd(r,n) \mid r'$$. The condition that $$n$$ is a prime is important to ensure that $$\gcd(r,n) = 1$$ so it'll divide all $$r'$$. Otherwise, for example, if $$n = 4, r = 2, r' = 3$$, then $$\gcd(2,4) = 2 \nmid 3$$, with this resulting in $$2m = 3 + 4n$$ not being solvable due to the left side being an even integer and the right side being an odd one.