Solving Linear Congruences
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
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.
so the congruence is unchanged.
Multiply by three to giveand reduce (mod 26) to giveThis is the only solution.