How to find the inverse of a number in a congruence relation

Question

I have an equation like this : $$39x \equiv 1 \mod 257$$

To solve this I need to find $39^{-1}$ in $\mathbb{Z_{257}}$.

Or am I thinking in the wrong way?

How can I find the inverse of a number in a congruence relation?

Answer 1

With the modular multiplicative inverse of an integer $x$ you want to compute the smallest $y$ such that

$$xy\equiv1\mod(n)\iff y\equiv x^{-1}\mod(n)$$

In order to compute these values, you can either use the extended Euclidean algorithm or Euler's theorem (since I find the EEA more useful, I'll use this algorithm instead of Euler's theorem.)

---

With the extended Euclidean algorithm:

The first part of the EEA for $a,b:a>b$ is just like the standard Euclidean algorithm, which proceeds by a succession of Euclidean divisions whose quotients are not used, only the remainders are kept. More precisely, it consists in computing the following sequence $$a=q_1·b+r_1$$ $$b=q_2·r_1+r_2$$ $$r_1=q_3·r_2+r_3$$ $$.$$ $$.$$ $$r_n=q_{n+2}·r_{n+1}+0$$

Where $q_k$ are the quotients (note that $q_k=\lfloor \frac{r_{k-2}}{r_{k-1}}\rfloor$) and $r_k$ the reminders after performing the Euclidean division. The algorithm stops when $r_{n+2}=0$ and results in $gcd(a,b)=r_{n+1}$
For instance for $a=97, \;b=21$ $$97=4·21+13$$ $$21=1·13+8$$ $$13=1·8+5$$ $$8=1·5+3$$ $$5=1·3+2$$ $$3=2·1+1$$ $$2=2·1+0$$ $$\Rightarrow gcd(97,21)=1$$

Now in the EEA, you have to perform the standard EA solving for the remainders as a linear combination of $a$ and $b$ $$97=4·21+13 \iff 13=97-4·21$$ $$21=1·13+8\iff 8=21-1·13=21-1·(97-4·21)=5·21-97$$ $$13=1·8+5 \iff 5=13-8=97-4·21-(5·21-97)=2·97-9·21$$ $$8=1·5+3 \iff 3=8-5=5·21-97-(2·97-9·21)=14·21-3·97$$ $$5=1·3+2 \iff 2=5-3=2·97-9·21-(14·21-3·97)=5·97-23·21$$ $$3=2·1+1 \iff 1=3-2=14·21-3·97-(5·97-23·21)=37·21-8·97$$

This last expression is known as Bézouts identity or Bézouts Lemma, which states that for any integers $a$ and $b$ with lcd$(a,b)=d$, $\exists$ coefficients $j$ and $i$ such that $$aj+bi=d$$ The greatest common divisor of two integers $a,b$ is, by the way, the smallest linear combination of these numbers you can make, which you can compute with the EEA. Having that said, note that $$aj+bi \equiv aj\equiv d\mod(b)$$ So, if gcd$(a,b)=1$, (and only under this condition $\exists$ a multiplicative inverse) the modular multiplicative inverse of $$a\mod(b)$$ is the coefficient $j$ of $a$ in Bézout's identity.

So for your example

$$39x \equiv 1 \mod 257$$ $$257=6·39+23\iff 23=257-6·39$$ $$39=1·23+16 \iff 16=39-23=39-(257-6·39)=7·39-257$$ $$23=1·16+7 \iff 7=23-16=257-6·39-(7·39-257)=2·257-13·39$$ $$16=2·7+2 \iff 2=16-2·7=7·39-257-2·(2·257-13·39)=33·39-5·257$$ $$7=3·2+1\iff 1=7-3·2=...=17·257\mathbf{-112}·39$$ $$\therefore -112\equiv 145\equiv 39^{-1} \mod 257 \iff 145·39 \equiv 1 \mod 257$$

Answer 2

Here's the standard layout for the E.E.A.. It is based on the result that in the standard Euclidean algorithm, the remainder at each step is a linear combination of the given numbers. $$\begin{array}{rrrl} r_i&u_i&v_i&q_i\\ \hline 257& 0&1 \\ 39&1&0&6\\ \hline 23&-6&1&1\\ 16&7&-1&1 \\ 7 &-13 &2 &2 \\ 2&33&-5&3\\ 1&-112&17 \\ \hline \end{array}$$ hence we have the Bézout's identity $$-112\cdot 39+17\cdot 257=1,$$ which implies $$39^{-1}\equiv -112\equiv 145\mod 257.$$