# Modular Arithmetic Problem!

1. Mar 20, 2012

### 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

2. Mar 20, 2012

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

3. Mar 20, 2012

### rcgldr

I think he means:

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

4. Mar 20, 2012

### 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

5. Mar 21, 2012

### chiro

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