0
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$

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.