Question

# Solve the following congruence. Make sure that the number you write is in the range [0,M−1] where M is the modulus of the congruence. If there is more than one solution, write the answer as a list separated by commas. If there is no answer, write N. 180x=276 (mod399)

Congruence
Solve the following congruence. Make sure that the number you write is in the range [0,M−1] where M is the modulus of the congruence. If there is more than one solution, write the answer as a list separated by commas. If there is no answer, write N.
180x=276 (mod399)

2020-10-19
180x =276(mod399)
It can be seen that ged (180.399) =3 and 3 divides 276, hence
180x =276(mod399) have an integer solution
This can be written as 180x+399y=276
Solve using Euclidian algorithm
$$\displaystyle{399}={180}\times{2}+{39}$$...(i)
$$\displaystyle{180}={39}\times{4}+{24}$$...(ii)
$$\displaystyle{39}={24}\times{1}+{15}$$...(iii)
$$\displaystyle{24}={15}\times{1}+{9}$$...(iv)
$$\displaystyle{15}={9}\times{1}+{6}$$...(v)
$$\displaystyle{9}={6}\times{1}+{3}$$ (Stop here $$\displaystyle\because{\gcd{=}}{3}$$)
Now
$$\displaystyle{3}={9}-{6}\times{1}$$
$$\displaystyle{3}={9}-{\left({15}-{9}\times{1}\right)}\times{1}$$ (From (v))
$$\displaystyle{3}={9}\times{\left({2}\right)}-{\left({15}\right)}\times{1}$$
$$\displaystyle{3}={\left({24}-{15}\times{1}\right)}\times{\left({2}\right)}-{\left({15}\right)}\times{1}$$ (From (iv))
$$\displaystyle{3}={\left({24}\right)}\times{\left({2}\right)}-{\left({15}\right)}\times{3}$$
$$\displaystyle{3}={\left({24}\right)}\times{\left({2}\right)}-{\left({39}-{24}\times{1}\right)}\times{3}$$ (From (iii))
$$\displaystyle{3}={\left({24}\right)}\times{\left({5}\right)}-{\left({39}\right)}\times{3}$$
$$\displaystyle{3}={\left({180}-{39}\times{4}\right)}\times{\left({5}\right)}-{\left({39}\right)}\times{3}$$ (From (ii))
$$\displaystyle{3}={\left({180}\right)}\times{\left({5}\right)}-{\left({39}\right)}\times{23}$$
$$\displaystyle{3}={\left({180}\right)}\times{\left({5}\right)}-{\left({399}-{180}\times{2}\right)}\times{23}$$ (From (i))
$$\displaystyle{3}={\left({180}\right)}\times{\left({51}\right)}-{\left({399}\right)}\times{23}$$
multiply by 92
$$\displaystyle{276}={\left({180}\right)}\times{\left({4692}\right)}+{\left({399}\right)}\times{\left(-{2116}\right)}$$
Compare it with 180x + 399y = 276
Hence x = 4692
Since $$\displaystyle{4692}\notin{\left[{0},{338}\right]}$$