Congruence in the Integers

This topic begins by exploring the notion of divisibility in the integers. First, the Well-Ordering Axiom and the Division Algorithm for the integers is given. The fact that exact division is not always possible within the set of integers should not be regarded as a shortcoming; rather, it is one of the profoundly interesting properties of the integers. Properties of divisibility and of greatest common divisors are detailed and then congruence modulo n is proven to be an equivalence relation on the integers. Solving linear congruence equations (including the Chinese remainder theorem), modular arithmetic, and the Euclidean Algorithm are also detailed with many examples.

Axiom (Well-Ordering) Every nonempty set of positive integers contains a least element.

Proposition (Division Algorithm) If and are integers with then there exist unique integers and such that with

Proof. By the Well-Ordering axiom, the set has a least element, say because is nonempty by By definition of If then and so with which contradicts the definition of Therefore, To show uniqueness, suppose that and satisfy the assumption. By definition of and there is some and such that and with and Thus and so Since it follows that as desired.

Definition (Divisor) An integer is called a multiple of an integer if for some integer In this case we also say, is a divisor of or is divisble by or even divides and we use the notation

Definition (Greatest Common Divisor) A positive integer is called the greatest common divisor of the nonzero integers and if

    (i) is a divisor of both and ,

    (ii) any divisor of both and is also a divisor of

and is denoted by Further, if then and are said to be relatively prime.

Proposition (Greatest Common Divisor)

    (i) Any two nonzero integers and have a greatest common divisor, which can be expressed as the smallest positive linear combination of and

    (ii) An integer is a linear cominbation of and if and only if it is a multiple of their greatest common divisor.

    (iii) There exists integers and such that if and only if

    (iv) If and then

    (v) If and then

    (vi) if and only if and

    (vii) If and is a common divisor of and then if and only if

    (viii) If and then

    (ix) If then

    Proof. (i) For every positive integer there are only a finite number of divisors and thus given two integers there are only a finite number of common divisors. Therefore, the greast common divisor of every pair of integers must exist and be unique. The fact that is the smallest linear combination of and follows from the Euclidean Algorithm.
    (ii) Let then since the Well-Ordering Axiom yields a smallest positive integer, say Then for some integers and By the Division Algorithm with and so Whence Therefore, and similiarily, So is a common divisor of and Let be a common divisor of and Then for some integers and Then as desired.
    (iii)  Apply (ii).
    (iv)  If then there exist integers and such that Thus for some since Therefore,
    (v)   If then there exist integers and such that Thus for some and since and   Therefore,
    (vi)  If then there exist integers and such that Thus, and so Also,    and so Conversely, if then there exists integers and such that If then there exists integers and such that Thus,   for some integers and Therefore, as desired.
    (vii) If then there exist integers and such that and so since and Thus, Conversely, if and then there exists integers and such that Therefore, for some and Thus and so
        (viii) If then there exist integers and such that If then for some integer Thus, and so as desired.
    (ix) Suppose and let be the set of common divisors of and and let be the set of common divisors of and . We will first show that If then and for some and Thus, Hence, so that Conversely, suppose is a common divisor of and so that and Thus, Thus so that Therefore, Hence the largest element in namely is the same as the largest element in namely

Proposition (Euclidean Algorithm) Let and be positive integers with If then If then apply the division algorithm repeatedly as follows:

This process ends when a remainder of 0 is obtained. This must occur after a finite number of steps; that is, for some

Then the last nonzero remainder, is the greatest common divisor of and

Proof. The proof follows from the property: if then Thus, if then and so Also, as in the statement of the proposition,

Example (Euclidean Algorithm) Use the Euclidean Algorithm to find By the Division Algorithm,

Thus,

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

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 (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) The congruence has a solution if and only if where


    Proof. (i) If and then and It follows that, and thus   It also follows that, and 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) The  equation has a solution if and only if for some The linear combination of and are precisely the multiples of so there is a solution if and only if

Example (Properties of Congruence Modulo n)

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

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

    (iii) If is a prime number, then which follows from the binomial theorem:

congruence in the integers _gr_351.gif]

because for

Proposition (Chinese Remainder Theorem) Let and be positive integers, with Then the system of congruences and has a solution. Moreover, any two solutions are congruent modulo

Proof. Since there exist integers and such that Let then satisfies the system. Further, for any integer is also a solution. Conversely, if and are solutions then and It follows from, and that and so as desired.

Example (Chinese Remainder Theorem)

    (i) To solve the system and we first find integers and such that namely Then the solution is found by computing Thus is the solution.

    (ii) To solve the system of congruences and we first solve the system and But since   is equivalent to by using we start by solving the system,   and which has solution via, and Next we solve the system and by using is equivalent to Since and we have the solution which is the solution to the original system as desired.

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.

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

Proposition (Modular Arithmetic) Let be a positive integer, then is an Abelian group of order .

Proof. By the definition of and the use of associavity 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