In Mathematics, modular arithmetic is a system of arithmetic for integers where numbers wrap around a certain value.

**Modular Arithmetic**

In a clock, we use the
numbers 1 to 12 to represent the time period of 24 hours. How is it possible to
represent the 24 hours of a day in a 12 number format? We use 1, 2, 3, 4, 5, 6,
7, 8, 9, 10, 11, 12 and after 12, we use 1 instead of 13 and 2 instead of 14
and so on. That is after 12 we again start from 1, 2, 3,... In this system the
numbers wrap around 1 to 12. This type of wrapping around after hitting some
value is called Modular Arithmetic.

In Mathematics,
modular arithmetic is a system of arithmetic for integers where numbers wrap
around a certain value. Unlike normal arithmetic, Modular Arithmetic process
cyclically. The ideas of Modular arithmetic was developed by great German
mathematician Carl
Friedrich Gauss, who is hailed as the “Prince of mathematicians”.

1. The day and night
change repeatedly.

2. The days of a week
occur cyclically from Sunday to Saturday.

3. The life cycle of a
plant.

4. The seasons of a
year change cyclically. (Summer, Autumn, Winter, Spring)

5. The railway and
aeroplane timings also work cyclically. The railway time starts at 00:00 and
continue. After reaching 23:59, the next minute will become 00:00 instead of
24:00

Two integers a and b
are congruence modulo *n* if they
differ by an integer multipleof *n*.
That *b* − *a* = *kn* for some integer *k*. This can also be written as a ≡ b (mod
n).

Here the number *n* is called modulus. In other words* **a *≡ *b *(mod *n*)
means *a *-*b *is divisible by *n*.

For example, 61 ≡ 5
(mod 7) because 61 – 5 = 56 is divisible by 7.

**Note**

When a positive
integer is divided by *n*, then the possible remainders are 0, 1, 2, . . .
,*n *- 1.

Thus, when we work
with modulo *n*, we replace all the numbers by their remainders upon
division by *n*, given by 0,1,2,3,..., *n *– 1

Two illustrations are
provided to understand modulo concept more clearly.

To find 8 (mod 4)

With a modulus of 4
(since the possible remainders are 0, 1, 2, 3) we make a diagram like a clock
with numbers 0,1,2,3.We start at 0 and go through 8 numbers in a clockwise
sequence 1, 2, 3, 0, 1, 2, 3, 0. After doing so cyclically, we end at 0.

Therefore, 8 ≡ 0(mod
4)

To find -5 (mod 3)

With a modulus of 3
(since the possible remainders are0, 1, 2, 3) we make a diagram like a clock
with numbers 0, 1, 2.

We start at 0 and go
through 5 numbers in anti-clockwise sequence 2, 1, 0, 2, 1. After doing so
cyclically, we end at 1.

Therefore, −5 ≡ 1 (mod
3)

Let *m *and *n *be
integers, where *m *is positive. Then by Euclid’s division lemma, we can write
*n *= *mq *+ *r *where 0 ≤ *r *< *m
*and *q *is an integer. Instead of writing *n *= *mq *+ *r *we
can use the congruence notation in the following way.

We say that *n *is
congruent to *r *modulo
*m*, if *n
*= *mq *+ *r *for some integer *q.*

*n *= *mq *+ *r*

*n*–*r *= *mq*

*n*–*r≡*0 (mod *m*)

*n≡r *(mod *m*)

Thus the equation *n
*= *mq *+ *r* through Euclid’s Division lemma can also be written *n* ≡ *r *(mod *m*).

·
Two integers *a *and *b *are congruent modulo *m*,
written as *a *≡ *b *(mod *m*), if they leave the same remainder
when divided by *m*.

Similar to basic
arithmetic operations like addition, subtraction and multiplication performed
on numbers we can think of performing same operations in modulo arithmetic. The
following theorem provides the information of doing this.

*a*, *b*, *c *and
*d *are integers and *m *is a positive integer such that if *a *≡
*b*(mod *m*) and* c *≡ *d *(mod *m*) then

(i) (*a *+ *c*)
≡ (*b *+ *d*) (mod *m*)

(ii) (*a *− *c*)
≡ (*b *− *d*) (mod *m*)

(iii) (*a *×*c*)
≡ (*b *×*d*) (mod *m*)

If 17≡4 (mod 13) and
42≡3 (mod 13) then from theorem 5,

(i) 17 + 42 ≡ 4 + 3 (mod
13)

59 7 ≡ (mod 13)

(ii) 17 - 42 ≡ 4 − 3
(mod 13)

-25 ≡ 1 (mod 13)

(iii) 17 × 42 ≡ 4 × 3
(mod 13)

714 ≡ 12 (mod 13)

**Theorem 6**

If *a≡b *(mod *m*)
then

(i) *ac *≡ *bc *(mod *m*)

(ii) * a *± *c *≡ *b *± *c*(mod *m*) for any integer *c*

**Example 2.11**

Find the remainders
when 70004 and 778 is divided by 7.

*Solution*

Since 70000 is
divisible by 7

70000 ≡ 0 (mod
7)

70000 + 4≡ 0 + 4 (mod
7)

70004 ≡ 4 (mod 7)

Therefore, the
remainder when 70004 is divided by 7 is 4

Since 777 is divisible
by 7

777 ≡ 0 (mod 7)

777 + 1 ≡ 0 + 1 (mod
7)

778 ≡ 1 (mod 7)

Therefore, the
remainder when 778 is divided by 7 is 1.

**Example 2.12**

Determine the value of
*d *such that 15 ≡ 3 (mod *d*).

*Solution*

15 ≡ 3 (mod *d*)
means 15 − 3 = *kd*, for some integer *k*.

12 = *kd*.

gives *d *divides
12.

The divisors of 12 are
1,2,3,4,6,12. But *d *should be larger than 3 and so the possible values
for *d *are 4,6,12.

**Example 2.13**

Find the least
positive value of *x *such that

(i) 67 + *x *≡ 1
(mod 4)

(ii) 98 ≡ (*x *+
4) (mod 5)

*Solution*

(i) 67 + *x *≡ 1
(mod 4)

67 + *x *– 1 = 4*n
*, for some integer *n*

66 + *x *= 4*n*

66 + *x *is a
multiple of 4.

Therefore, the least
positive value of *x *must be 2, since 68 is the nearest multiple of 4
more than 66.

(ii) 98 ≡ (*x *+
4) (mod 5)

98 − (*x *+ 4) =
5*n *, for some integer *n.*

94 - *x *= 5*n*

94 - *x *is a
multiple of 5.

Therefore, the least
positive value of *x *must be 4

Since 94 − 4 = 90 is
the nearest multiple of 5 less than 94.

While solving
congruent equations, we get infinitely many solutions compared to finite number
of solutions in solving a polynomial equation in Algebra

Solve 8*x *≡ 1
(mod 11)

8*x *≡ 1 (mod 11)
can be written as 8*x *− 1 = 11*k*, for some integer *k*.

*x *= (11k + 1) / 8

When we put *k *=
5, 13, 21, 29,... then 11*k*+1 is divisible by 8.

*x *= = (11× 5 + 1) /8= 7

= (11 × 13 + 1)/8 = 18

Therefore, the
solutions are 7,18,29,40, …

**Example 2.15**

Compute *x*, such
that 10^{4} ≡ *x *(mod 19)

*Solution*

10^{2} = 100 ≡
5 (mod 19)

10^{4} = (10^{2}
)^{2} ≡ 5^{2} (mod 19)

10^{4} ≡
25 104 ≡ 25

10^{4} ≡ 6
(mod 19) (since 25 º 6(mod 19))

Therefore, *x *=
6.

Find the number of
integer solutions of 3*x *≡ 1 (mod 15).

3*x *≡ 1 (mod 15)
can be written as

3*x *− 1 = 15*k
*for some integer *k*

3*x *= 15*k *+
1

*x *= [15k + 1] / 3

*x* = 5k + 1/3

Since 5*k *is an
integer, 5*k *+ (1/3) cannot be an integer.

So there is no integer
solution.

A man starts his
journey from Chennai to Delhi by train. He starts at 22.30 hours on Wednesday.
If it takes 32 hours of travelling time and assuming that the train is not
late, when will he reach Delhi?

Starting time 22.30,
Travelling time 32 hours. Here we use modulo 24.

The reaching time is

22.30+32 (mod 24) ≡
54.30 (mod24)

≡ 6.30 (mod24)

(Since 32 =
(1×24) + 8 Thursday Friday)

Thus, he will reach
Delhi on Friday at 6.30 hours.

Kala and Vani are
friends. Kala says, “Today is my birthday” and she asks Vani, “When will you
celebrate your birthday?” Vani replies, “Today is Monday and I celebrated my
birthday 75 days ago”. Find the day when Vani celebrated her birthday.

Let us associate the
numbers 0, 1, 2, 3, 4, 5, 6 to represent the weekdays from Sunday to Saturday
respectively.

Vani says today is
Monday. So the number for Monday is 1. Since Vani’s birthday was 75 days ago,
we have to subtract 75 from 1 and take the modulo 7, since a week contain 7
days.

–74 (mod 7) ≡ –4 (mod
7) ≡ 7–4 (mod 7) ≡ 3 (mod 7)

(Since, −74 – 3 = −77
is divisible by 7)

Thus, 1 − 75 ≡ 3 (mod
7)

The day for the number
3 is Wednesday.

Therefore, Vani’s
birthday must be on Wednesday.

Tags : Theorem, Illustration, Example, Solution | Mathematics Theorem, Illustration, Example, Solution | Mathematics

Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail

**Related Topics **

Copyright © 2018-2021 BrainKart.com; All Rights Reserved. (BS) Developed by Therithal info, Chennai.