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)
“Certainly, young children can begin to practice making letters and numbers and solving problems, but this should be done without workbooks. Young children need to learn initiative, autonomy, industry, and competence before they learn that answers can be right or wrong.”
—David Elkind (20th century)
“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)