In modular arithmetic, the question of when a linear congruence can be solved is answered by the linear congruence theorem. If a and b are any integers and n is a positive integer, then the congruence
has a solution for x if and only if b is divisible by the greatest common divisor d of a and n (denoted by gcd(a,n)). When this is the case, and x0 is one solution of (1), then the set of all solutions is given by
In particular, there will be exactly d = gcd(a,n) solutions in the set of residues {0,1,2,...,n − 1}. The result is a simple consequence of Bézout's identity.
Read more about Linear Congruence Theorem: Example, Solving A Linear Congruence, System of Linear Congruences
Famous quotes containing the words congruence and/or theorem:
“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)
“To insure the adoration of a theorem for any length of time, faith is not enough, a police force is needed as well.”
—Albert Camus (1913–1960)