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.
