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

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?

• Google "extended euclidean algorithm" – Peter Jan 12 at 13:47
• You are on the right track. Apply the extended Euclidean algorithm to find the inverse of 39 mod 257. – Wuestenfux Jan 12 at 13:47
• @Peter thank you guys. One more question, howto insert math symbols in a right way on stackecxhange? – Vladimir Jan 12 at 13:49
• @Vladmir With this (rather long) MathJax reference. – Toby Mak Jan 12 at 13:50
• – lab bhattacharjee Jan 12 at 13:53

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.

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