Use Euclids algorithm to find a multiplicative inverse of 15

Use Euclid\'s algorithm to find a multiplicative inverse of 15 modulo 88, and hence solve the linear congruence 15x Strictly Equivalent to 20 (mod 88). Explain why the following linear congruence has no solutions: 24x Strictly Equivalent to 21 (mod 88). Solve the linear congruence

Solution

88=15*6-2                   , 2=15*6-88

15=2*7+1                    , 1=15-2*7=-41*15+7*88

1=-41*15+7*88

Hence, -41*15=1 mod 88

So, -41 is the multiplicative inverse

-41=88-41=47

Hence,x=47*20 =940 mod 88=60 mod 88

x=60 mod 88

ii)

gcd(8,88)=8

So there exist u,v so that

8u+88v=8

Let such x exist so tha

24x=21 mod 88

gcd(88,3)=1 so we can divide the equation by 3 giving

8x=7 mod 88

So,

8x-7=88y

8x-88y=7

And, 8u+88v=4

So, 2*(8u+88v)-(8x-88y)=1

HEnce, 8u\'+88v\'=1

which is not possible as this means gcd(8,88)=1

Hence given congruence has not solution

iii)