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

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=(540)/(30)=18`