# Modular Arithmetic

## what is modular arithmetic ?

Modular arithmetic is the arithmetic of congruences, sometimes known informally as "clock arithmetic." In modular arithmetic, numbers "wrap around" upon reaching a given fixed quantity, which is known as the modulus denoted by n (which would be 12 in the case of hours on a clock, or 60 in the case of minutes or seconds on a clock).A familiar use of modular arithmetic is in the 12 hour clock, in which the day is divided into two 12-hour periods.

## Example:

If the time is 7:00 now, then 8 hours later it will be 3:00. Usual addition would suggest that the later time should be 7 + 8 = 15, but this is not the answer because clock time "wraps around" every 12 hours; in 12-hour time, there is no "15 o'clock". So the real time would be 3:00. Since the arithmetic representation of the clock is mod 12 .

## Congruence Relation:

Modular arithmetic can be handled mathematically by introducing a congruence relation such that a and b are integers and n is the congruent modulo, written: a=b (mod n) In other words, (a – b) is divisible by n

For example, 38=14 (mod 12) 38 -14 = 24 (divisible by 12)

## Fermat's Theorem

Let P be a prime number and N co-prime (having 1 as GCD) with P:

NP-1 = 1 (mod p)

Then, NP-1 – 1 is divisible by p

Example: p =3 ; n=5 NP-1 – 1= 53-1 – 1=25 -1=24 which is divisible by p=3

Advantage: to determine if 2 integers are co-prime.

## Wilson's Theorem:

If and only if P is prime (p-1)! = -l mod p

Then (p-1)! + 1 is divisible by p

Example: let P=5 then, (5-1)! + 1 = 4! +1 = 24 + 1 = 25 which is divisible by 5

Advantage: to check if a number is prime.

## Application:

Modular arithmetic 4
Modular arithmetic 5