Question

Calculate gcd(77, 30) by using the Euclidean algorithm. Find also integers u and v such that 49u + 30v = 1. Furthermore, find such x ∈ Z that 30x ≡ 1 (mod 77).

Answer 1

Answer:

1. gcd(77,30)=1

$77=2*30+17\\30=1*17+13\\17=1*13+4\\13=3*4+1\\4=4*1+0$

Since 1 is the last non zero remainder appearing in these equations then, 1 is the gcd of 77 and 30.

2. u=-11, v=18

Using the Euclidean Algorithm we have that

$49=1*30+19\\30=1*19+11\\19=1*11+8\\11=1*8+3\\8=2*3+2\\3=1*2+1\\2=1*2+0$

Now, we express the remainder as linear combinations of 49 and 30.

$1&=3-2\\ &=3-(8-2*3)=3-8+2*3\\&=(11-8)-8+2(11-8)=3*11-4*8\\&=3*11-4(19-11)=7*11-4*19\\&=7(30-19)-4*19=7*30-11*19\\&=7*30-11(49-30)=\\&=18*30-11*49$

Then $1=(-11)49+18*30$

3. x=18

If $30x\equiv 1\text{mod 77}$ then

$30x=k*77+1$ for some $k\in \mathbb{Z}$.

Then, if k=7,

$30x=7*77+1=540\\x=\frac{540}{30}=18$