Skip to content
October 27, 2007 / dranaxum

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

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: