Linear Congruences

    This topic describes how to solve a linear congruence equation, details when a solution exists, and in such case, exactly how many solutions will occur. Then inverse are covered, that is finding a multiplicative inverse of a given integer and moduli is defined and illustrated.

Definition (Linear Congruence) Given integers and a modulus a congruence equation of the form is called a linear congruence where is an unknown.

Example (Solutions of a Linear Congruence) Suppose is a solution of the congruence Then there exists an integer such that Thus, so that is a solution of the linear Diophantine equation Conversely, if the linear Diophantine equation has a solution then and so Thus, the linear congruence has as a solution if and only if there is an integer such that is a solution of the linear Diophantine equation

Proposition (Linear Congruence) Let be an unknown in the linear congruence equation and

    (i) If then there is precisely one solution.
    
    (ii) If then the congruence has no solution.
    
    (iii) If then there are exactly distinct solutions.
    
    Proof. (i) By the Euclidean algorithm there are integers and such that and then and thus we find that is a solution of the congruence. If is any other solution, then Thus, and since we have
    (ii)-(iii) Since the congruence is equivalent to in integers and the existence of solutions and requires that divide Suppose then that this requirement is satisfied and let and where and is a particular solution, be all solutions to Therefore, for any integer is a solution to
    To determine that there are incongruent solutions, we find the condition that describes when two solutions are congruent modulo Suppose we have two solutions, namely,

.

Since it follows that This show that a complete set of incongruent solutions is obtained by taking and ranges through a complete system of residues modulo one such set is given by

Example (Linear Congruence) Solve the linear congruence

    Solution. Solving the linear congruence equation is equivalent to solving the linear Diophantine equation for and There is a solution because and it is unique modulo A particular solution is and Thus all solutions to the Diophantine equations are and Suppose that



are two solutions to the congruence equation. Then clearly, This show that a complete set of incongruent solutions is obtained by taking and

Example (Linear Congruence) Solve the linear congruence

    Solution. Solving the linear congruence equation is equivalent to solving the linear Diophantine equation for and There is a solution because and and so there are exactly two solutions modulo A particular solution is and Thus all solutions for are and Suppose that



are two solutions. Since we have, This show that a complete set of incongruent solutions is obtained by taking and where Therefore, the solutions are and   
    
Example (Linear Congruence) Solve the linear congruence

    Solution. Because there are incongruent solutions modulo We use cancellation to simplify the congruence to We have Therefore, in terms of the original modulus, the solution is




Example (Linear Congruence) Solve the linear congruence

    Solution.  No solution because does not divide   
    
Example (Linear Congruence) Solve the linear congruence

    Solution. Because there is a unique solution modulo 77. We have and dividing by we have Next multiplying by we have and so Therefore,

Definition (Inverse of a Modulo n) Let be an integer with Then a solution of the linear congruence is called an inverse of

Proposition (Inverse of a Modulo n) Let be a prime. The positive integer is its own inverse modulo if and only if or

    Proof. If is its own inverse modulo then Thus, and so either or Therefore, or Conversely, if or then so that is its own inverse modulo

Example (Inverse of a Modulo n) By finding the inverse of 37 modulo solve for any integer   

    Solution. First we solve, We have



Now dividing by and simplifying, we have



Again dividing by and simplifying, we have



Therefore, Now to solve we multiply by and we have Thus is the solution.

• print this page
• pages linking here
• related pages