PRINT LINKED RELATED

Integer Arithmetic

(1) Definition (Equivalence Relation) A relation on a non-empty set is an equivalence relation on if it satisfies the following three properties:

    (i) (Reflexive) If then
    
    (ii) (Symmetric) If and then
    
    (iii) (Transitive) If and then
    

(2) Definition (Congruent Modulo n) Let be a positive integer. Integers and are congruent modulo n if is divisible by and is denoted by

(3) Example (Congruent Modulo n) We have since but   since Also we have since and since

(4) Proposition (Congruence Modulo n) Congruence modulo is an equivalence relation on the set of integers for each positive integer

    Proof. If is an integer, then since and so is reflexive. If and are integers and then since and so is symmetric. If and are integers, and then because and implies and so is transitive.

(5) Proposition (Congruence and the Integers) If and are integers, then if and only if there exists an integer such that
    
    Proof. If then and this means there exists an integer such that and so Conversely, if there is an integer such that then and so

(6) Proposition (Properties of Congruence Modulo n) Let be an integer. Then the following hold for all integers

    (i) If and then and
    
    (ii) If then
    
    (iii) If and then
    
    (iv) There exists an integer such that if and only if
    
    (v) If then
    
    Proof. (i) If and then and It follows that, and thus   It also follows that, and thus Therefore,  
    (ii) If then and so which means
    (iii) If then which means Since it follow that and so  
    (iv) If then there exists integers and such that Let then as desired. Conversely, if there is such a then for some Thus, and so
    (v) If we know that Thus there exists an integer such that and dividing both sides by we have Because it follows that Therefore,

(7) Example (Properties of Congruence Modulo n)
    (a) The remainder of when divided by 9 is the same as the remainder of the sum of its digits when divided by 9 which follows from writing where by noting that for any
    (b) The remainder of when divided by 11 is the same as the remainder of the alternating sum of its digits when divided by 11 which follows from writing in decimal form and noting that for any
    (c) If is a prime number, then which follows from the binomial theorem:  


                
because for

(8) Proposition (Equivalence Classes for the Integers) Let be a positive integer. Then a complete set of equivalence class representatives on for congruence modulo is

    Proof. Given an integer the Division Algorithm yields unique integers and such that and Then and so is congruent to at least one of In fact is unique because otherwise, say and   with for some would contradict the uniqueness of the Division Algorithm.

(9) Definition (Modular Arithmetic) Let   be a complete set of equivalence class representatives on for congruence modulo then and define the operation on by Arithmetic using this operation is often referred to as modular arithmetic.

    The operation is a well-defined binary operation; meaning, if and in then  



which follows from

(10) Proposition (Modular Arithmetic) Let be a positive integer, then is associative and commutative, each element has an inverse, and is the identity element.

    Proof. By the definition of and the use of associativity in the integers, it follows that for any   and The element is the identity because for any For every element of there is an inverse because and indeed   Commutativity follows since for

(11) Example (Modular Arithmetic) The arithmetic table for is:

(12) Proposition (Modular Exponentiation) If and then

    Proof. Because we have by definition, and since
    


we see that whence Therefore,

    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.

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

(14) 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

(15) 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

(16) 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

(17) 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   
    
(18) 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




(19) Example (Linear Congruence) Solve the linear congruence

    Solution.  No solution because does not divide   
    
(20) 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,

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

(22) 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

(23) 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.