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. 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=18Using 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]