1. Limited time only! Sign up for a free 30min personal 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!

Linear congruence

  1. May 2, 2012 #1
    I have a number with which I must use rules of congruence to find the remainder.
    rules I must apply are;
    split every 3 digits, starting from the right,
    find the remainder of each 3 digit number on division by 7
    form alternating sum of these remainders.

    Thisnumber should be congruent to a modulo 7


    the number is 2468135711201104


    number 2 468 135 711 201 104
    remain 2 6 2 4 5 6

    Alternating sum 6-5+4-2+6-2 = 7
    So a = 7 (mod 7)

    I have gone through this several times with the same result
    Would this be right?

    Dividing through by 7 only to have a remainder of 7 seems a bit odd!!!
     
  2. jcsd
  3. May 2, 2012 #2

    tiny-tim

    User Avatar
    Science Advisor
    Homework Helper

    Hi Roodles01! :smile:
    a is congruent to 7 mod 7 …

    what is odd about that? :confused:

    (btw, also works for remainders on division by 11 or 13 :wink:)
     
  4. May 2, 2012 #3

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    Not only is it "odd" to have a remainder of 7 when dividing by 7, it is impossible! What you are saying is that the remainder is 0. The calculation you have done is a test for divisibility by 7. Yes, 2468135711201104 is divisible by 7. The hard way to do that would have been to actually divide by 7: 2468135711201104 is 7 times 352590815885872!
     
  5. May 2, 2012 #4

    Curious3141

    User Avatar
    Homework Helper

    You've shown that a is divisible by 7, because a = 7 (mod 7) is equivalent to a = 0 (mod 7).

    This is one of the tests for divisibility by 7. To see how it works, consider a = 1000x + y.

    Now 1000 = 6(mod 7) = -1 (mod 7).

    Hence 1000x = -x(mod 7).

    So 1000x + y = (y - x) (mod 7).

    Therefore splitting a large number into groups of threes ("thousands"), working out the residues modulo 7 and affixing alternate signs to them before summing allows a quick way to calculate the remainder upon division by 7.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Linear congruence
  1. Linear congruence (Replies: 4)

  2. Congruence problem. (Replies: 10)

Loading...