+59 The solution to the congruence 125x = 20 (mod 405) can be written as x = k (mod n), where k is a modulo-n residue.
a) find the value of k
b) find the value of n
*pretend the equal sign is the congruence sign
thx in advance
+624 a) To find the value of k, we can use the Euclidean algorithm to find the greatest common divisor (GCD) of 125 and 405. The GCD is 25, so we can divide both sides of the congruence by 25 to get:
5x = 4 (mod 162)
We can then use the Extended Euclidean algorithm to find the modular inverse of 5 modulo 162. The modular inverse is 77, so we can multiply both sides of the congruence by 77 to get:
x = 308 (mod 162)
Reducing modulo 162, we get k = 146.
b) The value of n is the modulus of the congruence, which is 405.
Therefore, the solution to the congruence can be written as x = 146 (mod 405).
