Try the Free Math Solver or Scroll down to Tutorials!

 

 

 

 

 

 

 

 
 
 
 
 
 
 
 
 

 

 

 
 
 
 
 
 
 
 
 

Please use this form if you would like
to have this math solver on your website,
free of charge.


Integers and Division

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 ac ≡ bd mod m.
a = 2, b = 5, c = 4, d = 1, m = 3

Caesar Cipher
• Alphabet to number: a~0, b~1, … , z~1.
• Encryption: EK(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?

ch 3.5
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: p1, p2 …, pn.
Consider the number q = p1p2 … pn + 1
Since we have only finite number of primes and q
is not one of them, pi should divide q for some i.
Obviously pi| p1p2 … pn.
Recall that a | b, a | c ⇒ a | b + c.
Therefore, pi | (q - p1p2 … pn) = 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 = 2512, # of primes = 2512/512 ∼ 25
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 a1, a2, … an are pairwise relatively
prime if, for all pairs of numbers, they are relatively
prime
Formally: The integers a1, a2, … an are pairwise relatively
prime if gcd(ai, aj) = 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 = 23*3*5 = 23*31*51
500 = 22*53 = 22*30*53
• Then compute the gcd by the following
formula:
Example: gcd(120,500) = 2min(3,2)3min(1,0)5min(1,3)
= 223051 = 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 n2 - 79n + 1601 is
prime, whenever n is a positive integer.
(Disprove)
When n = 1601,
n2 - 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