Modular Arithmetic (Congruences) Of Elementary Number Theory : Lucid Explanation With Examples

The eminent mathematician Gauss, who is considered as one of the greatest in history has quoted "mathematics is the queen of sciences and number theory is the queen of mathematics."

Several important discoveries of Elementary Number Theory such as Fermat's little theorem, Euler's theorem, the Chinese remainder theorem are based on simple arithmetic of remainders.

This arithmetic of remainders is called Modular Arithmetic or Congruences.

In this article, I aim to explain "Modular Arithmetic (Congruences)" in such a simple way, that a common man with little math back ground can also understand it.

I supplement the lucid explanation with examples from everyday life.

For students, who study Elementary Number Theory, in their under graduate or graduate courses, this article will serve as a simple introduction.

Modular Arithmetic (Congruences) of Elementary Number Theory :

We know, from the knowledge of Division

Dividend = Remainder + Quotient x Divisor.

If we denote dividend by a, Remainder by b, Quotient by k and Divisor by m, we get

a = b + km

or a = b + some multiple of m

or a and b differ by some multiples of m

or if you take away some multiples of m from a, it becomes b.

Taking away some (it does n't matter, how many) multiples of a number from another number to get a new number has some practical significance.

Example 1 :

For example, look at the question

Today is Sunday. What day will it be 200 days from now ?

How do we solve the above problem ?

We take away multiples of 7 from 200. We are interested in what remains after taking away the mutiples of 7.

We know 200 ÷ 7 gives quotient of 28 and remainder of 4 (since 200 = 28 x 7 + 4)

We are not interested in how many multiples are taken away.

i. e., We are not interested in the quotient.

We only want the remainder.

We get 4 when some (28) multiples of 7 are taken away from 200.

So, The question, "What day will it be 200 days from now ?"

now, becomes, "What day will it be 4 days from now ?"

Because, today is sunday, 4 days from now will be Thursday. Ans.

The point is, when, we are interested in taking away multiples of 7,

200 and 4 are the same for us.

Mathematically, we write this as

200 a 4 (mod 7)

and read as 200 is congruent to 4 modulo 7.

The equation 200 a 4 (mod 7) is called Congruence.

Here 7 is called Modulus and the process is called Modular Arithmetic.

Let us see one more example.

Example 2 :

It is 7 O' clock in the morning.

What time will it be 80 hours from now ?

We have to take away multiples of 24 from 80.

80 ÷ 24 gives a remainder of 8.

or 80 a 8 (mod 24).

So, The time 80 hours from now is the same as the time 8 hours from now.

7 O' clock in the morning + 8 hours = 15 O' clock

= 3 O' clock in the evening [ since 15 a 3 (mod 12) ].

Let us see one last example before we formally define Congruence.

Example 3 :

A person is facing East. He rotates 1260 degree anti-clockwise. In what direction, he is facing ?

We know, rotation of 360 degrees will bring him to the same position.

So, we have to remove multiples of 360 from 1260.

The remainder, when 1260 is divided by 360, is 180.

i. e., 1260 a 180 (mod 360).

So, rotating 1260 degrees is same as rotating 180 degrees.

So, when he rotates 180 degrees anti-clockwise from east, he will face west direction. Ans.

Definition of Congruence :

Let a, b and m be any integers with m not zero, then we say a is congruent to b modulo m, if m divides (a - b) exactly without remainder.

We write this as a a b (mod m).

Other ways of defining Congruence include :

(i) a is congruent to b modulo m, if a leaves a remainder of b when divided by m.

(ii) a is congruent to b modulo m, if a and b leave the same remainder when divided by m.

(iii) a is congruent to b modulo m, if a = b + km for some integer k.

In the three examples above, we have

200 a 4 (mod 7); in example 1.

80 a 8 (mod 24); 15 a 3 (mod 12); in example 2.

1260 a 180 (mod 360); in example 3.

We started our discussion with the process of division.

In division, we dealt with whole numbers only and also, the remainder, is always less than the divisor.

In Modular Arithmetic, we deal with integers (i.e. whole numbers + negative integers).

Also, when we write a a b (mod m), b need not necessarily be less than a.

The three most important properties of congruences modulo m are:

The reflexive property :

If a is any integer, a a a (mod m).

The symmetric property :

If a a b (mod m), then b a a (mod m).

The transitive property :

If a a b (mod m) and b a c (mod m), then a a c (mod m).

Other properties :

If a, b, c and d, m, n are any integers with a a b (mod m) and c a d (mod m), then

a + c a b + d (mod m)

a - c a b - d (mod m)

ac a bd (mod m)

(a)n a bn (mod m)

If gcd(c,m) = 1 and ac a bc (mod m), then a a b (mod m)

Let us see one more (last) example, in which we apply the properties of congruences.

Example 4 :

Find the last decimal digit of 13^100.

Finding the last decimal digit of 13^100 is same as

finding the remainder when 13^100 is divided by 10.

We know 13 a 3 (mod 10)

So, 13^100 a 3^100 (mod 10) .....(i)

We know 3^2 a -1 (mod 10)

So, (3^2)^50 a (-1)^50 (mod 10)

So, 3^100 a 1 (mod 10) .....(ii)

From (i) and (ii), we can say

last decimal digit of 13^100 is 1. Ans.

For more of Elementary Number Theory, go tohttp://www.math-help-ace.com/Elementary-Number-Theory.html