2
$\begingroup$

Use Euclid's algorithm to find a multiplicative inverse of 15 mod 88, hence solve the linear congruence $15x\equiv 20 \pmod{88}$

So far I have:

$88=5\cdot15+13$

$15=1\cdot13+2$

Backwards substitution gives

$15v+18w=1$

$1=15-1\cdot13$

$=15-1(88-5\cdot15)$

$=15\cdot15-1\cdot88$

now very stuck what to do from here:(

$\endgroup$
  • $\begingroup$ Where did the $18$ come frome? $\endgroup$ – Thomas Andrews Dec 4 '16 at 15:07
  • 2
    $\begingroup$ And $1\neq 15-1\cdot 13$... $\endgroup$ – Thomas Andrews Dec 4 '16 at 15:07
2
$\begingroup$

This is much simpler if you use the extended Euclidean algorithm in fraction form

$${\rm mod}\ 88\!:\ \ x\equiv \dfrac{20}{15}\equiv \dfrac{4}3\equiv \dfrac{-84}3\equiv -28\equiv 60$$


Remark $\ $ It's valid to cancel $\,5\,$ above since $\,5\,$ is coprime to $\,88\,$ so invertible, so cancellable, i.e.

$$\begin{align} \color{#c00}5\cdot 3x\equiv \color{#c00}5\cdot 4\!\! \overset{\large \ \ \,\times\ \color{#c00}{5^{\large -1}}} \iff&\ 3x\equiv 4\\[.4em] {\rm so}\quad x\equiv \dfrac{20}{15}\ \iff&\ \ x\equiv \dfrac{4}3\end{align}$$

Beware $\ $ Modular fraction arithmetic is well-defined only for fractions with denominator coprime to the modulus. See here for further discussion.

$\endgroup$
1
$\begingroup$

You have missed a few steps. Also I'm not sure where the number $18$ came from in $18w$.

Normally in the initial part you should continue until you get to 1. E.g.

$88=5\times15+13$ hence $13=88-5\times13\tag{1}$

$15=1\times13+2$ hence $2=15-1\times13\tag{2}$

$13=6\times2+1$ hence $1=13-6\times2\tag{3}$

Then work backwards from there:

$1=13-6\times2$ using $(3)$

$1=13-6\times(15-1\times13)=7\times13-6\times15$ using $(2)$

$1=7\times(88-5\times15)-6\times15=7\times88-41\times15$ using $(1)$

Hence $-41\times15\equiv1\pmod{88}$

Or written with a positive number: $47\times15\equiv1\pmod{88}$

So $20\times47\times15=940\times15\equiv20\pmod{88}$

$940=10\times88+60$ hence $60\times15\equiv20\pmod{88}$

$\endgroup$
0
$\begingroup$

To solve $15x\equiv 20\pmod{88}$, subtract consecutive equations to find $15^{-1}\bmod 88$ first:

$$88=(1)(88)+(0)(15)\\ 15=(0)(88)+(1)(15)\\ 13=(1)(88)+(-5)(15)$$

(because $88-5\cdot 15=13$)

$$2=(-1)(88)+(6)(15)$$

$$1=(7)(88)+(-41)(15)$$

Therefore $(15)(-41)\equiv 1\pmod{88}$, so $$15^{-1}\equiv -41\equiv 47\pmod{88}$$

Therefore $$x\equiv 20\cdot 15^{-1}\equiv 20\cdot 47\pmod{88}$$

$$\equiv 940\equiv 60\pmod{88}$$

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