Skip to content

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.

Advertisements