Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Can anyone give me a rundown on Congruence?

  1. Jul 25, 2003 #1
    I've googled for an hour now and I've found a few resources but they all assume you know the terminology. Like for example.

    a = b(mod n)

    Can anyone explain the modulus operator and congruence to me?
     
  2. jcsd
  3. Jul 26, 2003 #2
    0= 0 χ 5 + 0
    1= 0 χ 5 + 1
    2= 0 χ 5 + 2
    3= 0 χ 5 + 3
    4= 0 χ 5 + 4
    5= 1 χ 5 + 0
    6= 1 χ 5 + 1
    .
    .
    .

    We observe that the remainder left when any integer is divided by 5 is one of the five integers 0, 1, 2, 3, 4. We say that two integers a and b are "congruent modulo 5" if they leave the same remainder on division by 5. Thus 2, 7, 22, -3, -8, etc are all congurent modulo 5 since they leave the remainder 2. In general, we say that two integers a and b are congrent modulo d, where d is a fixed integer, if a and b leave the same remainder on division by d. For example, 15 and 1 are congruent modulo 7. We can write 15 ≡ 1 (mod 7)

    Defination
    Let a and b be integers and let n be a positive integer. We say a is congruent to b modulo n , written
    a ≡ b (mod n)

    In fact "a ≡ b (mod n)" and "a=b+nd (where d is an integer)" are equilvalent.


    Here are more examples
    2003 ≡ 3 (mod 1000)
    1985 ≡ 85 (mod 100)
    1985 ≡ 985 (mod 1000)
    121 ≡ 0 (mod 11)
    953 ≡ 4 (mod 13)

    Here are some properties of congruences. For all integers a, b and c, we have
    1) a ≡ a (mod n)
    2) a ≡ b (mod n) if and only if b≡ a (mod n)
    3) if a ≡ b (mod n) and b ≡ c (mod n), then a≡ c (mod n)
    4) n | a if and only of a ≡ 0 (mod n)
    5) If a ≡ b (mod n) and x is a natural number, then ax ≡ bx (mod n)
     
  4. Jul 26, 2003 #3
    Thanks alot, that really helped!
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?