Answer to Question #267936 in Discrete Mathematics for malpha

Question

Solve the linear congruence 34x ≡ 53(mod 89).

Answer 1

We shall use the following well-known properties of congruences:

1) if $a≡b (\mod m),$ then $a≡b+m\cdot k (\mod m);$

2) if $ad≡bd (\mod m)$ and $gcd(d,m)=1,$ then $a≡b (\mod m).$

Let us solve the linear congruence $34x ≡ 53(\mod 89).$ This congruence is equivalent to $34x ≡ (53+89)(\mod 89),$ that is $34x ≡ 142(\mod 89).$ Since $gcd(2,89)=1,$ we conclude that after dividing both parts by 2 the last congruence is equivalent to $17x ≡ 71(\mod 89).$ Then we have $17x ≡ (71-5\cdot 89)(\mod 89),$ and hence $17x ≡ -374(\mod 89).$ Taking into account that $gcd(17,89)=1,$ we conclude that that after dividing both parts by $17$ the solution of the congruence is $x ≡ -22(\mod 89)≡67(\mod 89).$