# 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 .

## 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.