Question

How many distinct solutions are there to 85x ≡ 115 (mod 210)? List all the solutions, writing each as c where 0 ≤ c < 210.

a) One solution: c = 185
b) Two solutions: c = 65 and c = 125
c) Three solutions: c = 95, c = 155, and c = 215
d) No solutions

Answer 1

To solve the congruence equation 85x ≡ 115 (mod 210), we can simplify the equation by finding the GCD of 85 and 210, then find the modular inverse and generate the solutions.

Step-by-step explanation:

To solve the congruence equation 85x ≡ 115 (mod 210), we need to find all the values of x that satisfy this equation.

We can begin by finding the greatest common divisor (GCD) of 85 and 210, which is 5. The congruence equation can be simplified by dividing both sides by the GCD, giving us 17x ≡ 23 (mod 42).

We can then find the modular inverse of 17 (mod 42), which is 5. Multiplying both sides of the equation by the modular inverse, we get x ≡ 5 * 23 (mod 42). This simplifies to x ≡ 115 (mod 42).

Now, we need to find all the values of x between 0 and 210 that satisfy this congruence. By adding multiples of 42 to 115, we can generate the following solutions:

x = 115, 157, 199