Solve-the-linear-congruence-19x-4-mod-141-

Question Number 133761 by liberty last updated on 24/Feb/21

Solve the linear congruence

19 x \equiv 4 (\mod 141)

Answered by bobhans last updated on 24/Feb/21

U s i n g E u c l i d e a n a l g o r i t h m

141 = 7 \times 19 + 8

19 = 2 \times 8 + 3

8 = 2 \times 3 + 2

3 = 1 \times 2 + 1

n o w w e g e t 1 = 3 - 1 \times 2

1 = 3 - 1 \times (8 - 2 \times 3)

1 = 3 \times 3 - 1 \times 8

1 = 3 \times (19 - 2 \times 8) - 1 \times 8

1 = 3 \times 19 - 7 \times 8

1 = 3 \times 19 - 7 (141 - 7 \times 19)

1 = 52 \times 19 - 7 \times 141

T h i s s h o w t h a t 52 i s a n i n v e r s e o f

19 (m o d 141)

T h e n 19 x \equiv 4 (m o d 141)

\Rightarrow 52 \times 19 x \equiv 4 \times 52 (m o d 141)

\Rightarrow (1 + 7 \times 141) x \equiv 208 (m o d 141)

∴ x \equiv 67 (m o d 141)

Facebook Tweet Pin