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).

1. gcd(77,30)=1

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

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

Then

3. x=18

If then

for some .

Then, if k=7,

the answer is b i just did that

step-by-step explanation: