Find-the-greatest-common-divisor-of-1122-and-1001-and-express-the-greatest-common-divisor-d-in-the-form-d-1122x-1001y-Using-the-above-result-solve-the-congruence-equation-37x-11-mod-33-

Question Number 107594 by Rio Michael last updated on 11/Aug/20

Find the greatest common divisor of 1122 and 1001 and

express the greatest common divisor d in the form .

d = 1122 x + 1001 y

Using the above result solve the congruence equation

37 x \equiv 11 (\mod 33)

Answered by 1549442205PVT last updated on 11/Aug/20

37 x - 11 = 33 y \Leftrightarrow y = \frac{37 x - 11}{33} = x + \frac{4 x - 11}{33}

Set \frac{4 x - 11}{33} = t (t \in Z) \Rightarrow 4 x - 11 = 33 t

\Leftrightarrow x = \frac{33 t + 11}{4} = 8 t + 3 + \frac{t - 1}{4} . Set \frac{t - 1}{4} = k

\Rightarrow t = 4 k + 1 (k \in Z) we get

{\begin{cases} x = 33 k + 11 \\ y = 37 k + 12 \end{cases} (k \in Z)

Answered by Aziztisffola last updated on 11/Aug/20

we have \gcd (1122; 1001) = 11 = d

1122 x + 1001 y = 11

and 37 x \equiv 11 (\mod 33) \Leftrightarrow \exists k \in Z 37 x - 33 k = 11

\Rightarrow 37 x - 33 k = 11 = 1122 x + 1001 y

Using Gauss theorem we get

x = 33 k + 11