Question

Find the smallest positive integer x that solves the congruence: 7x = 6 (mod 38) x= Hint: From running Euclid's algorithm forwards and backwards we get 1 = $(7) + f(38). Find s and use it to solve the congruence.

Answer 1

Answer:

x=66

Step-by-step explanation:

We are given that 7x=6(mod 38)

We have to find the smallest positive integer x that solves the congruence.

We know that Euclid's algorithm for two number whose gcd is 1

at+bs=1

Using this algorithm

where a=7 and b=38

Then substituting the values

7t+38 s=1

If t= 11 and s=-2 then 77-76=1

Hence, t=11 and s=-2 are satisfied the equation.

Therefore, 7(11)=1(mod 38)

Multiply on both sides by 6 then we get

7(11)(6)=6(mod 38)

7(66)=6 (mod 38)

Hence, 66 is the smallest positive integer that solve the congruence.