Scribd Logo
Upload

Welcome to Scribd!

  • 123 views

    Sma3043 Elementary Number Theory SEMESTER 2 2020/2021: The Theory of Congruence

    Uploaded by

    Dayzel
    This document discusses congruence modulo n, which defines when two integers a and b are congruent modulo n (written a ≡ b (mod n)). It means that when a and b are divided by n, they leave the same remainder. Several properties of congruence are proved, including that congruence behaves similarly to equality with respect to addition, multiplication, and taking powers. Applications include using congruence to find remainders when dividing integers, and proving divisibility statements.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd

    Sma3043 Elementary Number Theory SEMESTER 2 2020/2021: The Theory of Congruence

    Uploaded by

    Dayzel
    123 views15 pages
    This document discusses congruence modulo n, which defines when two integers a and b are congruent modulo n (written a ≡ b (mod n)). It means that when a and b are divided by n, they leave the same remainder. Several properties of congruence are proved, including that congruence behaves similarly to equality with respect to addition, multiplication, and taking powers. Applications include using congruence to find remainders when dividing integers, and proving divisibility statements.

    Original Title

    Part 1

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    This document discusses congruence modulo n, which defines when two integers a and b are congruent modulo n (written a ≡ b (mod n)). It means that when a and b are divided by n, they leave the same remainder. Several properties of congruence are proved, including that congruence behaves similarly to equality with respect to addition, multiplication, and taking powers. Applications include using congruence to find remainders when dividing integers, and proving divisibility statements.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    123 views15 pages

    Sma3043 Elementary Number Theory SEMESTER 2 2020/2021: The Theory of Congruence

    Uploaded by

    Dayzel
    This document discusses congruence modulo n, which defines when two integers a and b are congruent modulo n (written a ≡ b (mod n)). It means that when a and b are divided by n, they leave the same remainder. Several properties of congruence are proved, including that congruence behaves similarly to equality with respect to addition, multiplication, and taking powers. Applications include using congruence to find remainders when dividing integers, and proving divisibility statements.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    You are on page 1of 15

    SMA3043 ELEMENTARY NUMBER THEORY

    SEMESTER 2 2020/2021

    THE THEORY OF CONGRUENCE

    PROF. MADYA DR ROHAIDAH MASRI


    CONGRUENCE MODULO n

    Definition 1
    @ a  b(mod n)  a = kn + b
    Let n be a fixed positive integer, and let a, b  Z. We say  n | (a – b)
    “a is congruent to b modulo n “, and can be denoted by
    a  b  mod n   a  b  kn for some of k  Z

    Example.

    (i) 22 = 6(3) + 4 or 22 – 4 = 6(3)

    (ii)
    4 = 6(1) + (-2) or 4 – (-2) = 6(1)

    (iii) 4 = 2(2) or 5 = 2(2) + 1

    2
    CONGRUENCE MODULO n

    Notes:
    • Congruences are only defined for integers, and the modulo m must be a natural number.
    For example,
    a ≡ 1/2 mod 2 is not defined since 1/2 is not an integer;
    similarly, a ≡ b mod 0 is not defined since 0 is not a natural number

    3
    CONGRUENCE MODULO n

    Facts:
    • Any two integers are congruent modulo 1.

    Example: 3  2 mod 1  3 – 2 = 1(1)


    11  3 mod 1  11 – 3 = 1(8)

    • Two integers are congruent modulo 2 when they are both even
    or both odd.

    Example: 3  5 mod 2  3 – 5 = 2(-1)


    8  6 mod 2  8 – 6 = 2(1)

    4
    CONGRUENCE MODULO n
    The Division Algorithm and Congruence Modulo n
    (a)

    (b)

    (c)

    5
    Congruence Modulo n
    The Division Algorithm and Congruence Modulo n
    (d)

    (e)

    Example: Set of Integer modulo 6 , Z6 = {0, 1, 2, 3, 4, 5 }


    6, 13, 26, 51, 64, 71 will form a
    6 26 64 71 complete set of residue modulo 6

    13 51

    6
    The Division Algorithm and Congruence Modulo n
    Example.

    7
    Congruence Modulo n
    Remainder

    Next theorem gives us a useful characterization of congruence modulo n in terms of


    remainders upon division by n.

    Theorem 1

    Let a and b be any integers. Then, a  b (mod n)


    if and only if
    a and b have the same nonnegative remainder upon division by n.

    Example.

    12  5 (mod 7) and 82  5 (mod 7)

    Hence, 12  82 (mod 7)

    8
    Congruence Modulo n
    Properties of Congruence

    • Congruence can be viewed as a generalized form of equality.

    • Next theorem gives some of the elementary properties of equality that


    carry over to congruence.

    Theorem 2

    Let n be a fixed integer greater than 1, and a, b, c, d  Z. Then the


    following properties hold:

    (a) a  a (mod n)

    (b) If a  b (mod n) , then b  a (mod n)

    (c) (Chaining congruence)


    If a  b (mod n) , and b  c (mod n) , then a  c (mod n)
    (Cont. )

    9
    Congruence Modulo n
    Properties of Congruence
    Theorem 2 (cont.)

    (d) (Adding/ Multiplying Congruence)


    If a  b (mod n) , and c  d (mod n) , then
    a + c  b + d (mod n) , and ac  bd (mod n)
    (e) If a  b (mod n) , then a + c  b + c (mod n) , and
    ac  bc (mod n)

    (f) (Taking congruences to the k-th power)


    If a  b (mod n) , then ak  bk (mod n) , k  Z+.

    10
    Properties of Congruence
    Proof.
    (d)

    11
    Properties of Congruence

    Note:

    The converse of Theorem 2 (d) is not always true.


    For example, (4) (2)  (1) (2) (mod 6), but 4  1(mod 6).

    12
    Some Applications of Congruence
    Finding Remainders

    Example.

    Find the remainder when 237 is divided by 7.

    Solution.

    13
    Some Applications of Congruence
    Finding Remainders

    Example.

    Solution.

    14
    Some Applications of Congruence
    Example.
    Show that,


    7| 5 2n
     32 5 n 2

    Solution.

    15

    You might also like