How can mathematical induction be used to prove a modular arithmetic problem?

[Bipolarity]

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 {n_{1},n_{2},n_{3},...n_{k}}

Consider two more natural numbers m and p such that

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

Now prove that

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

All help would be appreciated.

BiP

 

[chiro]

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.

 

[rcgldr]

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.

I think he means:

mod_m( ... (mod_m( mod_m(n_{1}) + n_{2})) ... + n_{k})

 

[Bipolarity]

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.

BiP

 

[chiro]

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.

BiP

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).