Thread: Find all solutions

Find all six solutions to 12x = 24 mod 30 (= is congruence not equality...)

Book says to use this theorem:

Suppose

d divides a, c, m. Then every solution of

(

a/d)x =(c/d) mod (m/d)

corresponds to

d distinct solutions (modulo m) of

ax = c mod m:


Not sure how to show this because it seems to me that there would be infinite solutions. How do I do this?

Originally Posted by jzellt

Find all six solutions to 12x = 24 mod 30 (= is congruence not equality...)

Book says to use this theorem:

Suppose

d divides a, c, m. Then every solution of

(

a/d)x =(c/d) mod (m/d)

corresponds to

d distinct solutions (modulo m) of

ax = c mod m:


Not sure how to show this because it seems to me that there would be infinite solutions. How do I do this?

Of course there are infinite solutions in the integers, but it is asking for solutions in

and how do I find those solutions in Z30

The theorem the book asks you to use is the Linear Congruence Theorem which is used to solve linear congruences as yours
Note that as Drexel said, the values of x "wrap around" (x = 30 is equivalent to x = 0, x = 31 is equivalent to x = 1, ...). But the LCT basically provides a general formula that gives all solutions to your congruence, so you don't have to worry about whether there are infinite solutions, since the formula gives them all