# Modulus, a simple demonstration

I write this paper in order to prove an equation. Why? Because today, in a national maths contest, I received an exercise that could have been solved using this equation.

We know that a modular expression looks like this: a≡b(mod n) , and it is read: “a is congruent to b modulo n”.

I must prove the following: P(k): (∑α_{i }mod 2) mod 2=(∑α_{i) }mod 2 where 1≤i≤k

We will use mathematical induction:

First step: we choose k=2

(α_{1} mod 2+ α_{2} mod 2) mod 2=(α_{1} + α_{2}) mod 2

which is true for every integer α

Second step: we know that P(k) is true and we must prove that P(k+1) is also true

(∑α_{i }mod 2) mod 2=(∑α_{i) }mod 2 (+ α_{k+1} mod 2), α_{k+1} is binary so α_{k+1} = α_{k+1} mod 2=> (∑α_{i }mod 2) mod 2 + α_{k+1} mod 2 =(∑α_{i) }mod 2 + α_{k+1} mod 2

We apply the modulus for the first and second member:

((∑α_{i }mod 2) mod 2 + α_{k+1} mod 2) mod 2 =((∑α_{i) }mod 2 + α_{k+1} mod 2) mod 2

We consider ∑(α_{i }mod 2) = ß

so (ß mod 2 + α_{k+1} mod 2) mod 2 = (ß+α_{k+1}) mod 2 according to the first step

=> ((∑α_{i }mod 2) mod 2 + α_{k+1} mod 2) mod 2 = (∑α_{j }mod 2) mod 2 where 1≤j≤(k+1)

Also, according to the first step: ((∑α_{i) }mod 2 + α_{k+1} mod 2) mod 2 = (∑α_{j)} mod 2 where 1≤j≤(k+1)

In conclusion: P(k+1) is true P(k)=>P(k+1) => we have proved that the equation is true.

PS: A variant of this equation is used by RSA cryptosystem, but it’s a generalization mod 2 is replaced with mod n, where n is an integer, and the values are exponential.

## Leave a Reply