Cryptography: Number Theory - Divisibility

Divisibility 

•If a and b are integers with a ¹ 0, we say that
a divides b if there is an integer c so that b = ac.

•When a divides b we say that a is a factor of b and that b is a multiple of a.

•The notation a | b means that a divides b.

•We say a non-zero integer a is a divisor of another integer b provided the remainder is zero when we divide b by a. That is, when b = ma for some integer m.

•For integers a, b, and c it is true that

•If a|1, then a=±1

•if a | b and b | a, then a=±b

•if a | b and a | c, then a | (b + c)

–Example: 3 | 6 and 3 | 9, so 3 | 15.

•if a | b, then a | bc for all integers c

–Example: 5 | 10, so 5 | 20, 5 | 30, 5 | 40, …

•if a | b and b | c, then a | c

–Example: 4 | 8 and 8 | 24, so 4 | 24.