Solving Linear Congruences

Theorem

The linear congruence

1. Has solution if and only ifdivides

2. Has a unique solution if

3. 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.