Solving A Linear Congruence
In general solving equations of the form:
If the greatest common divisor d = gcd(a, n) divides b, then we can find a solution x to the congruence as follows: the extended Euclidean algorithm yields integers r and s such ra + sn = d. Then x = rb/d is a solution. The other solutions are the numbers congruent to x modulo n/d.
For example, the congruence
has 4 solutions since gcd(12, 28) = 4 divides 20. The extended Euclidean algorithm gives (−2)·12 + 1·28 = 4, i.e. r = −2 and s = 1. Therefore, one solution is x = −2·20/4 = −10, and −10 = 4 modulo 7. All other solutions will also be congruent to 4 modulo 7. Since the original equation uses modulo 28, the entire solution set in the range from 0 to 27 is {4, 11, 18, 25}.
Read more about this topic: Linear Congruence Theorem
Famous quotes containing the words solving a, solving and/or congruence:
“There are horrible people who, instead of solving a problem, tangle it up and make it harder to solve for anyone who wants to deal with it. Whoever does not know how to hit the nail on the head should be asked not to hit it at all.”
—Friedrich Nietzsche (1844–1900)
“More than a decade after our fellow citizens began bedding down on the sidewalks, their problems continue to seem so intractable that we have begun to do psychologically what government has been incapable of doing programmatically. We bring the numbers down—not by solving the problem, but by deciding it’s their own damn fault.”
—Anna Quindlen (b. 1952)
“As for butterflies, I can hardly conceive
of one’s attending upon you; but to question
the congruence of the complement is vain, if it exists.”
—Marianne Moore (1887–1972)