# Find all solutions

• Feb 28th 2010, 08:04 PM
jzellt
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?
• Feb 28th 2010, 08:56 PM
Drexel28
Quote:

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 \$\displaystyle \mathbb{Z}_{30}\$
• Feb 28th 2010, 09:11 PM
jzellt
and how do I find those solutions in Z30
• Feb 28th 2010, 09:14 PM
Bacterius
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 ;)