Mathematics: Solve the congruence 169x 25 (mod 330)

Solve the congruence 169x 25 (mod 330) - id16925330861690, michellen2020

lorie76

12.03.2022

First solve the congruence $13y\equiv1\pmod{330}$ . Euclid's algorithm shows

330 = 25 * 13 + 5

13 = 2 * 5 + 3

5 = 1 * 3 + 2

3 = 1 * 2 + 1

=> 1 = 127 * 13 - 5 * 330

=> 127 * 13 = 1 mod 330

so that y=127 is the inverse of 13 modulo 330. Then in the original congruence, multiplying both sides by 127 twice gives

$127^2\cdot13^2x\equiv127^2\cdot5^2\pmod{330}\implies x\equiv127^2\cdot5^2\equiv403,225\equiv295\pmod{330}$

Then any integer of the form x=295+330n is a solution to the congruence, where is any integer.

0,0(0 оценок)