How to Solve $ax\equiv 1\pmod{n}$

Suppose $a, n\in\mathbb{N}$ with $\gcd(a,n)=1$ . Then by Proposition 2.1.12 the equation $ax\equiv 1\pmod{n}$ has a unique solution. How can we find it?

Proposition 2.3 (Extended Euclidean representation)   Suppose $a, b\in \mathbb {Z}$ and let $g=\gcd(a,b)$ . Then there exists $x,y\in\mathbb{Z}$ such that

$$ax + by = g.$$

Remark 2.3   If $e=cg$ is a multiple of $g$ , then $cax + cby = cg = e,$ so $e = (cx)a+(cy)b$ can also be written in terms of $a$ and $b$ .

Proof. [Proof of Proposition 2.3.1] Let $g=\gcd(a,b)$ . Then $\gcd(a/g,b/g)=1$ , so by Proposition 2.1.14 the equation

$$\frac{a}{g}\cdot x\equiv 1\left({\rm mod} \hspace{1ex}\frac{b}{g}\right)$$ (2.3.1)

has a solution $x\in\mathbb{Z}$ . Multiplying (2.3.1) through by $g$ yields $ax \equiv g \pmod{b}$ , so there exists $y$ such that $b\cdot (-y) = ax-g$ . Then $ax+by = g$ , as required. $\qedsymbol$

Given $a, b$ and $g=\gcd(a,b)$ , our proof of Proposition 2.3.1 gives a way to explicitly find $x,y$ such that $ax+by = g$ , assuming one knows an algorithm to solve linear equations modulo $n$ . Since we do not know such an algorithm, we now discuss a way to explicitly find $x$ and $y$ . This algorithm will in fact enable us to solve linear equations modulo $n$ --to solve $ax\equiv 1\pmod{n}$ when $\gcd(a,n)=1$ , use the algorithm below to find $x$ and $y$ such that $ax+ny = 1$ . Then $ax\equiv 1\pmod{n}.$

Example 2.3   Suppose $a=5$ and $b=7$ . The steps of Algorithm 1.1.13 to compute $\gcd(5,7)$ are, as follows. Here we underline certain numbers, because it clarifies the subsequent back substitution we will use to find $x$ and $y$ .

$$\underline{7} =1\cdot \underline{5} + \underline{2} \underline{2} = \underline{7} - \underline{5}\hfill$$

$$\underline{5} =2\cdot \underline{2} + \underline{1} \underline{1} = \underline{5} - 2\cdot \underline{2} = \underline{5} - 2(\underline{7}-\underline{5}) = 3\cdot\underline{5}-2\cdot\underline{7}\hfill$$

On the right, we have back-substituted in order to write each partial remainder as a linear combination of $a$ and $b$ . In the last step, we obtain $\gcd(a,b)$ as a linear combination of $a$ and $b$ , as desired.

Example 2.3   That example was not too complicated, so we try another one. Let $a=130$ and $b=61$ . We have

$$\underline{130} = 2\cdot \underline{61} + \underline{8} \underline{8} = \underline{130}-2\cdot\underline{61}$$

$$\underline{61} = 7\cdot \underline{8} + \underline{5} \underline{5} = -7\cdot\underline{130}+15\cdot\underline{61}$$

$$\underline{8} = 1\cdot \underline{5} + \underline{3} \underline{3} = 8\cdot\underline{130}-17\cdot\underline{61}$$

$$\underline{5} = 1\cdot \underline{3} + \underline{2} \underline{2} =-15\cdot\underline{130}+32\cdot\underline{61}$$

$$\underline{3} = 1\cdot \underline{2} + \underline{1} \underline{1} = 23\cdot\underline{130}-49\cdot\underline{61}$$

Thus $x=23$ and $y=-49$ is a solution to $130 x + 61 y = 1$ .

Example 2.3   This example is just like Example 2.3.4 above, except we make the notation on the right more compact.

$$\underline{130} = 2\cdot \underline{61} + \underline{8} \underline{8} = (1,-2)$$

$$\underline{61} = 7\cdot \underline{8} + \underline{5} \underline{5} = (-7,15) = (0,1) - 7(1,-2)$$

$$\underline{8} = 1\cdot \underline{5} + \underline{3} \underline{3} = (8,-17) = (1,-2) - (-7,15)$$

$$\underline{5} = 1\cdot \underline{3} + \underline{2} \underline{2} = (-15,32) = (-7,15) - (8,-17)$$

$$\underline{3} = 1\cdot \underline{2} + \underline{1} \underline{1} = (23,-49) = (8,-17) - (-15,32)$$

Notice at each step that the vector on the right is just the vector from two steps ago minus a multiple of the vector from one step ago, where the multiple is the cofficient of what we divide by.

SAGE Example 2.3   The SAGE command xgcd(a,b) computes the greatest common divisor $g$ of $a$ and $b$ along with $x,y$ such that $ax+by = g$ .

sage: xgcd(5,7)
(1, 3, -2)
sage: xgcd(130,61)
(1, 23, -49)

Algorithm 2.3 (Extended Euclidean Algorithm)   Suppose $a$ and $b$ are integers and let $g=\gcd(a,b)$ . This algorithm finds $g$ , $x$ and $y$ such that $ax+by = g$ . We describe only the steps when $a>b\geq 0$ , since one can easily reduce to this case.

1. [Initialize] Set $x=1$ , $y=0$ , $r=0$ , $s =1$ .
2. [Finished?] If $b=0$ , set $g=a$ and terminate.
3. [Quotient and Remainder] Use Algorithm 1.1.12 to write $a = qb + c$ with $0\leq c<b$ .
4. [Shift] Set $(a, b, r, s, x, y) =(b, c, x-qr, y-qs, r, s)$ and go to step 2. (This shift step is nicely illustrated in Example 2.3.5.)

Proof. This algorithm is the same as Algorithm 1.1.13, except that we keep track of extra variables $x,y,r,s$ , so it terminates and when it terminates $d=\gcd(a,b)$ . We omit the rest of the inductive proof that the algorithm is correct, and instead refer the reader to [#!knuth1!#, §1.2.1] which contains a detailed proof in the context of a discussion of how one writes mathematical proofs. $\qedsymbol$

Algorithm 2.3 (Inverse Modulo $n$ )   Suppose $a$ and $n$ are integers and $\gcd(a,n)=1$ . This algorithm finds an $x$ such that $ax\equiv 1\pmod{n}$ .

1. [Compute Extended GCD] Use Algorithm 2.3.7 to compute integers $x,y$ such that $ax+ny=\gcd(a,n)=1$ .
2. [Finished] Output $x$ .

Proof. Reduce $ax+ny = 1$ modulo $n$ to see that $x$ satisfies $ax\equiv 1\pmod{n}$ . $\qedsymbol$

Example 2.3   Solve $17x \equiv 1\pmod{61}$ . First, we use Algorithm 2.3.7 to find $x,y$ such that $17x+61y=1$ :

$$\underline{61} =3\cdot\underline{17}+\underline{10} \underline{10} =\underline{61} - 3\cdot\underline{17}$$

$$\underline{17} =1\cdot\underline{10}+\underline{7} \underline{7} =-\underline{61} + 4\cdot\underline{17}$$

$$\underline{10} =1\cdot \underline{7}+\underline{3} \underline{3} =2\cdot\underline{61} - 7\cdot\underline{17}$$

$$\underline{3} =2\cdot\underline{3} +\underline{1} \underline{1} =-5\cdot\underline{61}+18\cdot\underline{17}$$

Thus $17\cdot 18 + 61\cdot (-5) = 1$ so $x=18$ is a solution to $17x \equiv 1\pmod{61}$ .

SAGE Example 2.3   SAGE implements the above algorithm for quickly computing inverses modulo $n$ . For example,

sage: a = Mod(17, 61)
sage: a^(-1)
18