Introduction to Congruences

    A modern treatment of congruences was introduced by Karl Friedrich Gauss. Congruences, or modular arithmetic arises naturally in common everyday situations. For example, odometers usually work modulo 100,000 and utility meters often operate modulo 1000. In trigonometry, it is common to work in degrees, that is modulo 360 degrees, and indeed, it is common to work in minutes and seconds both of which are working modulo 60.
    In this topic we introduction the notion of an equivalence relation and show that congruence modulo n is an equivalence relation. Many basic properties of congruences are proven with examples. Also detailed are modular arithmetic, systems of residues, and modular exponentiation.

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
    

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

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

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.

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

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,

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

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.

• print this page
• pages linking here
• related pages