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$.


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!

  • 2
    $\begingroup$ Have you ever heard of Bezout's theorem in number theory? $\endgroup$
    – user678090
    Jun 12, 2019 at 7:13

1 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.

  • $\begingroup$ Thank you so much for your detailed, right to the point, and easy-to-understand answer :) $\endgroup$
    – Akira
    Jun 13, 2019 at 8:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.