1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
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?