Modular Arithmetic
Defenition, properties,theorems and more ...
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)
Addition subtraction and multiplication are applicable to modular arithmetic
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:
Computer Science
MOD is used mainly for algorithim
Chemistry
MOD is used to locate the postion of subshells in atoms
Music
MOD is used in composing music scripts