Introduction to Modular Arithmetic and Congruence

Modular arithmetic is an arithmetic system for the integers where the numbers wrap around, like on a clock for example. The numbers start at one, they go round to twelve and then start again at one, this would be an example of modulo 12. However generally in modular arithmetic we start at 0 and go to 11, before starting at 0 again. This means that 7 o'clock would be 6 mod 12 (mod is often used to shorten modulo). In fact because the number line "wraps around" it means that 19 o'clock = 7 o'clock (as you will know if you have used a 24 hour clock), this means that 18 mod 12 = 6 mod 12; because of this a mod m is wrote where a < m.

However it does not have to be just modulo 12, it can be modulo anything (as long at is a positive integer), so let us jump straight into the definition. So that you are aware of the notation I will use a|b means b divides a (this means that b/a is an integer). Let m be a positive integer and let a, b both be integers if m|a-b then a is congruent to b modulo m, wrote mathematically this is: a ≡ b mod m. Make sure you do not think "≡" means equivalent in this case, because it does not!

You can add in modular arithmetic (provided they have the same modulo). Let m be a positive integer and let a, b,c and d be integers if a ≡ b mod m and c ≡ d mod m then a + c ≡ (b+d) mod m. So basically you add the parts preceding the modulo together and then find modulo m of that.
You may also notice that a/m has a remainder of b, this is how we can quickly work out that 19 o'clock is the same as 7 o'clock, or the same as 103 o'clock. You simple divide the number by the modulo and work out the remainder.

An example of why we would use this using our clock as an example is if it is 4 o'clock now, what will the time be in 157 hours? So what we have is 3 mod 12 and 157 mod 12, adding these together we get 160 mod 12, 160/12 = 13 remainder 4. This means that 160 mod 12 = 4 mod 12, so it will be 5 o'clock 157 hours from 4 o'clock.

This should give you an idea of how to do basic addition with congruences, if you do not understand fully read what I have wrote again and then if you still do not understand, post a comment. Now we have the basic principles in place we can begin to go further. Now we will prove that a mod m + b mod m = (a+b) mod m and also how multiplication works in modular arithmetic.

Multiplication between two congruences is just as easy as addition with congruences, I will first provide a definition to you, before proving it. Let m be a positive integer and let a, b,c and d be integers if a ≡ b mod m and c ≡ d mod m then ac ≡ (bd) mod m; this is the same sort of principle as addition. Now to prove them.

First to prove addition:

Now to prove multiplication:

These are the very basics of congruences, but the are integral to modular arithmetic (I mean, think how important addition and multiplication is normally), they are very, very powerful and I will begin to explore them more and more in my upcoming posts. I will prove just one more result as it is pretty easy and uses multiplication.

The proposition is that aⁿ ≡ bⁿ mod m is also true provided  a ≡ b mod m and n is a positive integer. We will prove this by induction. Let P(n) be be the statement of the proposition, then P(1) is obviously true as we already know that a ≡ b mod m. So let us assume that P(n) is true, then we have that aⁿ ≡ bⁿ mod m and that a ≡ b mod m, multiplying the two of them together (using our proved method) we get a × aⁿ ≡ b × bⁿ mod m, this then simplifies to: aⁿ⁺¹ ≡ bⁿ⁺¹ mod m, which is P(n+1). Hence P(n) is true for all values of n!

I hope that you like this post and that is helps you. If you did like it then please also like us on Facebook.