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$

Question

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' <p$, 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' <p$, there exists $m \in \mathbb Z$ such that $mr = r' + pn$ for some $n \in \mathbb Z$.

Thank you for your help!

Answer 1

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.