Answer:
1. gcd(77,30)=1
[tex]77=2*30+17\\30=1*17+13\\17=1*13+4\\13=3*4+1\\4=4*1+0[/tex]
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
[tex]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[/tex]
Now, we express the remainder as linear combinations of 49 and 30.
[tex]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[/tex]
Then [tex]1=(-11)49+18*30[/tex]
3. x=18
If [tex]30x\equiv 1\text{mod 77}[/tex] then
[tex]30x=k*77+1[/tex] for some [tex]k\in \mathbb{Z}[/tex].
Then, if k=7,
[tex]30x=7*77+1=540\\x=\frac{540}{30}=18[/tex]
