Solving Linear Congruences
Theorem
The linear congruence

Has solution if and only ifdivides

Has a unique solution if

Hassolutions, whereand dividesgiven by the unique solutionof the congruence
Proof: The linear Diophantine equationhas solutions if and only ifdivides from which 1. follows.
For 2. supposeIfis one solution ofthe general solution isbutsois the only solution of
For 3. ifanddividesthenbutso the last congruence has a unique solutionHence the integers satisfyingareNone of these are congruent (mod n) because none differ by n and for any integeris congruentto one of them since ifas given by the Division Algorithm, thenso these are the solutions to
Example: Solve
so the congruence has three solutions (mod 21)
Cancel 3 to giveMultiply the congruence by a number so that the coefficient ofis 1. We multiply by 2 to giveand reduce both sides (mod 7) to giveThenandare the other solutions.
Example: Solve
so the congruence is unchanged.
Multiply by three to giveand reduce (mod 26) to giveThis is the only solution.