Lecture_6

Divisibility
b divides a if a=mb for some m, where a,b and m are integers
b|a
b is a divisor of a
gcd(a, b): greatest common divisor of a and b
Euclidean algorithm can find gcd
Two integers, a and b, are relatively prime if
gcd(a, b) = 1
Prime Numbers
An integer p>1 is a prime number if and only if its only divisors are ±1 and ±p
Any integer a > 1 can be factored as:

where p1 < p2 < ... < pt are prime numbers and where each ai is a positive integer

Modular Arithmetic
If a is an integer and n is a positive integer, we define a mod n to be the remainder when a is divided by n
n is called the modulus
Two integers a and b are congruent modulo n if
(a mod n) = (b mod n), which is written as

(mod n) operator maps all integers into the set of integers
Zn ={0,1,...,(n?1)}
Modular arithmetic performs arithmetic operations within confines of set Zn
Properties of Modular Arithmetic
Rules of ordinary arithmetic involving addition, subtraction, and multiplication also apply in modular arithmetic