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!

Modular Arithmetic Problem!

  1. Mar 20, 2012 #1
    I'm trying to prove something in modular arithmetic that I came upon across my studies in comp sci. Consider a set of natural numbers [itex] {n_{1},n_{2},n_{3},...n_{k}} [/itex]

    Consider two more natural numbers [itex]m[/itex] and [itex]p[/itex] such that

    [tex] (\sum^{k}_{i=1}n_{i} ) \ mod \ m = p [/tex]

    Now prove that

    [itex]((((n_{1} \ mod \ m + n_{2}) \ mod \ m + n_{3}) \ mod \ m + n_{4}) \ mod \ m + ... + n_{k}) \ mod \ m = p [/itex]

    All help would be appreciated.

  2. jcsd
  3. Mar 20, 2012 #2


    User Avatar
    Science Advisor

    Hey bipolarity.

    I'm just unsure about what the modulus term is. For example is it (a mod (m + n2)) or is it a mod m + n2 etc.
  4. Mar 20, 2012 #3


    User Avatar
    Homework Helper

    I think he means:

    [itex]mod_m( ... (mod_m( mod_m(n_{1}) + n_{2})) ... + n_{k})[/itex]
  5. Mar 20, 2012 #4
    Sorry! Thanks rcgldr for clarifying what I meant.
    I meant the divisor in the modulus operator is always 'm'.

    So basically you are adding the next number, then taking the remainder after dividing by m. Then again you are adding the next number, then taking the remainder after dividing by m. You do this until you run out of numbers, at which point you finally take the remainder after dividing by m. The final answer should be 'p'. But I'm trying to prove it.

  6. Mar 21, 2012 #5


    User Avatar
    Science Advisor

    Thanks Bipolarity.

    This looks like a good candidate for mathematical induction. The first case is trivial because n1 MOD m and n1 MOD m are the same so proven for n = 1.

    I think I know how you could do it but I'll ask you for your thoughts and any work that you have for solving the problem in your own terms (we encourage that highly here on PF).
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Similar Discussions: Modular Arithmetic Problem!
  1. Help: modular arithmetic (Replies: 17)

  2. Modular arithmetic (Replies: 5)

  3. Modular arithmetic (Replies: 7)