TAOCP 3.2.1.3 Exercise 7
Since $a \equiv 1 + b \pmod{m}$, we have $aa' \equiv (1 + b)a' \equiv 1 \pmod{m}.$ Solving for $a'$, we obtain $(1 + b)a' \equiv 1 \pmod{m} \implies a' \equiv \frac{1}{1 + b} \pmod{m}.$ We can expand...
Exercise 7. [**] [M20] When $a$ satisfies the conditions of Theorem 3.2.1.2A, it is relatively prime to $m$; hence there is a number $a'$ such that $aa' \equiv 1 \pmod{m}$. Show that $a'$ can be expressed simply in terms of $b$.
Verified: yes
Solve time: 1m07s
Since $a \equiv 1 + b \pmod{m}$, we have
$aa' \equiv (1 + b)a' \equiv 1 \pmod{m}.$
Solving for $a'$, we obtain
$(1 + b)a' \equiv 1 \pmod{m} \implies a' \equiv \frac{1}{1 + b} \pmod{m}.$
We can expand this using the geometric series formula modulo $m$, which terminates because $b^s \equiv 0 \pmod{m}$ for some potency $s$:
$a' \equiv 1 - b + b^2 - b^3 + \cdots + (-1)^{s-1} b^{s-1} \pmod{m}.$
This series gives an explicit expression for $a'$ in terms of $b$. Each term is computed modulo $m$, and the number of replacement operations equals $s-1$.
This completes the proof.
∎