**Recap**

•f(x)∈O(g(x)) if ∃k∈R, ∃c∈R, ∀x∈R, x>k ⇒ 0≤|f(x)|≤c|g(x)|.

•f(x)∈Ω(g(x)) if ∃k∈R, ∃c∈R, ∀x∈R, x>k ⇒ |f(x)| ≥ c |g(x)|.

•f(x)∈θ(g(x)) if f(x)∈O(g(x)) and f(x)∈Ω(g(x)). Equivalently,

•if ∃k∈R, ∃c1,c2∈R, ∀x∈R, x>k ⇒ c1 |g(x)| ≤ |f(x)| ≤ c2 |g(x)|.

ch3.4

Integers and Division

**Division**

• Def: a (a≠0) divides b if ∃ c such that b = ac.

a | b: a divides b

• 3 | 7? 3 | 12?

• 3 | 0? 0 | 3?

• Theorem: Let a, b, c be integers. Then

a | b, a | c ⇒ a | (b + c).

a | b ⇒ a | bc ∀ c ∈ Z.

a | b, b | c ⇒ a | c.

• Let a, b, c be integers. Then

a | b, a | c ⇒ a | (b + c).

• Let a, b, c be integers. Then

a | b ⇒ a | bc ∀ integer c.

• Let a, b, c be integers. Then

a | b, b | c ⇒ a | c.

• a | b and b | c ⇒ a | (mb + nc) for all

integer m, n.

**Division Algorithm**

• Theorem: Let a be an integer and d a

positive integer. Then there exist unique q

and r, with 0≤q<r, such that a = dq + r.

• 101 = 7 • 14 + 3

• -11 = 7 • (-2) + 3

**Modular Arithmetic**

• Def: a, b: integers, m: positive integer, a is

congruent to b modulo m if m | (a - b).

• a ≡ b mod m

• a ≡ b (mod m) iff a % m = b % m.

• 17 ≡ 12 mod 5, 17 % 5 = 2, 12 % 5 = 2

• -3 ≡ 17 mod 10, -3 % 10 = 7, 17 % 10 = 7

• Theorem: Let m be a positive integer.

a ≡ b mod m iff ∃ k such that a = b + km.

**More…**

• Theorem: Let m be a positive integer. If a ≡

b mod m and c ≡ d mod m, then

a + c ≡ b + d mod m.

ac ≡ bd mod m.

• Prove or Disprove

If ac ≡ bc (mod m), where a, b, c, m ∈ Z

(with m ≥ 2), then a ≡ b (mod m).

a, b, c, d, m ∈ Z, c, d > 0, m ≥ 2,

then
a^{c} ≡ b^{d} mod m.

a = 2, b = 5, c = 4, d = 1, m = 3

**Caesar Cipher**

• Alphabet to number: a~0, b~1, … , z~1.

• Encryption: E_{K}(x) = x + K mod 26.

• Decryption:

• Caesar used K = 3.

• If you don’t know K and you have a secret

text, would you be able to find K? How?

Primes and GCD

**Prime numbers**

• Def: A positive integer p is prime if the only

positive factors of p are 1 and p

If there are other factors, it is composite

Note that 1 is not prime!

It’s not composite either – it’s in its own class

• Def: An integer n is composite if and only if

there exists an integer a such that a | n and

1 < a < n

**Fundamental theorem of arithmetic**

• Every positive integer greater than 1 can be

uniquely written as a prime or as the product of two

or more primes where the prime factors are written

in order of non-decreasing size

• Examples

100 = 2 * 2 * 5 * 5

182 = 2 * 7 * 13

29820 = 2 * 2 * 3 * 5 * 7 * 71

**Composite factors**

• If n is a composite integer, then n has a prime divisor

less than or equal to the square root of n

Showing a number is prime!

• Show that 113 is prime

• Solution

The only prime factors less than √113 = 10.63 are

2, 3, 5, and 7

Neither of these divide 113 evenly

Thus, by the fundamental theorem of arithmetic,

113 must be prime

**Primes are infinite**

• Theorem (Euclid): There are infinitely many prime

numbers

(Proof) Proof by contradiction

Assume there are a finite number of primes

List them as follows: p_{1}, p_{2} …, p_{n}.

Consider the number q = p_{1}p_{2} … p_{n} + 1

Since we have only finite number of primes and q

is not one of them, pi should divide q for some i.

Obviously p_{i}| p_{1}p_{2} … p_{n}.

Recall that a | b, a | c ⇒ a | b + c.

Therefore, pi | (q - p_{1}p_{2} … p_{n}) = 1. (*)

**The prime number theorem**

• The radio of the number of primes not exceeding x

and x/ln(x) approaches 1 as x grows without

bound

Rephrased: the number of prime numbers less than x

is approximately x/ln(x)

When x = 2^{512}, # of primes = 2^{512}/512 ∼ 2^{5}^{03}

**Greatest common divisor**

• The greatest common divisor of two integers

a and b is the largest integer d such that

d | a and d | b

Denoted by gcd(a,b)

• Examples

gcd (24, 36) = 12

gcd (17, 22) = 1

gcd (100, 17) = 1

**Relative primes**

• Two numbers are relatively prime if they

don’t have any common factors (other than

1)

Rephrased: a and b are relatively prime if

gcd (a,b) = 1

• gcd (25, 39) = 1, so 25 and 39 are relatively

prime

**Pairwise relative prime**

• A set of integers a_{1}, a_{2}, … a_{n} are pairwise relatively

prime if, for all pairs of numbers, they are relatively

prime

Formally: The integers a_{1}, a_{2}, … a_{n} are pairwise relatively

prime if gcd(a_{i}, a_{j}) = 1 whenever 1 ≤ i < j ≤ n.

• Example: are 10, 17, and 21 pairwise relatively

prime?

gcd(10,17) = 1, gcd (17, 21) = 1, and gcd (21, 10) = 1

Thus, they are pairwise relatively prime

• Example: are 10, 19, and 24 pairwise relatively

prime?

Since gcd(10,24) ≠ 1, they are not

**More on gcd’s**

• Given two numbers a and b, rewrite them

as:

**Example:** gcd (120, 500)

120 = 2^{3}*3*5 = 2^{3}*3^{1}*5^{1}

500 = 2^{2}*5^{3} = 2^{2}*3^{0}*5^{3}

• Then compute the gcd by the following

formula:

**Example:** gcd(120,500) = 2^{min(3,2)}3^{min(1,0)}5^{min(1,3)}

= 2^{2}3^{0}5^{1} = 20

**Least common multiple**

• The least common multiple of the positive

integers a and b is the smallest positive

integer that is divisible by both a and b.

Denoted by lcm (a, b)

• **Example:** lcm(10, 25) = 50

• What is lcm (95256, 432)?

**lcm and gcd theorem**

• Let a and b be positive integers. Then

a*b = gcd(a,b) * lcm (a, b)

• **Example: **gcd (10,25) = 5, lcm (10,25) = 50

10*25 = 5*50

• **Example: **gcd (95256, 432) = 216, lcm (95256,

432) = 190512

95256*432 = 216*190512

**Example Proof**

• Prove or disprove that n^{2} - 79n + 1601 is

prime, whenever n is a positive integer.

(Disprove)

When n = 1601,

n^{2} - 79n + 1601 = 1601 (1601 - 79 + 1)

• Prove or disprove that p_1p_2…p_n+1 is a

prime, whenever n is a positive integer.

2*3*5*7*11*13+1 = 30031 = 59 * 509