Example of Extended Euclidean Algorithm
Recall that gcd(84, 33) = gcd(33, 18) = gcd(18, 15) =
gcd(15, 3) = gcd(3, 0) = 3
We work backwards to write 3 as a linear combination of
84 and 33:
3 = 18 − 15
[Now 3 is a linear combination of 18 and 15]
= 18 − (33 − 18)
= 2(18) − 33
[Now 3 is a linear combination of 18 and 33]
= 2(84 − 2 × 33)) − 33
= 2 × 84 − 5 × 33
[ Now 3 is a linear combination of 84 and 33]
Corollary 2: If a and b are relatively prime, then there
exist s and t such that as + bt = 1.
Corollary 3: If gcd(a, b) = 1 and a | bc, then a | c.
• Exist s, t ∈ Z such that sa + tb = 1
• Multiply both sides by c: sac + tbc = c
• Since a | bc, a | sac + tbc, so a | c
Corollary 4: If p is prime and , then p | ai
for some 1≤ i ≤ n.
Proof: By induction on n:
• If n = 1: trivial.
Suppose the result holds for n and .
• note that .
• If we are done.
• If not, .
• By Corollary 3,
• By the IH, p | ai for some 1 ≤ i ≤ n.
The Fundamental Theorem of
Arithmetic , II
Theorem 3: Every n > 1 can be represented uniquely
as a product of primes , written in nondecreasing size.
Proof: Still need to prove uniqueness. We do it by strong
• Base case: Obvious if n = 2.
Inductive step . Suppose OK for n' < n.
• Suppose that
• , so by Corollary 4, for some j.
• But then , since both and are prime.
• But then
• Result now follows from I.H.
Characterizing the GCD and LCM
Theorem 6: Suppose and ,
where pi are primes and .
• Some could be 0.
Proof: For gcd, let .
Clearly c | a and c | b.
• Thus, c is a common divisor , so c ≤ gcd(a, b).
If | gcd(a, b),
• must have
o Otherwise q | a so q | gcd(a, b) ( likewise b )
If | gcd(a, b), must have
o E.g., if , then
• Thus, c ≥ gcd(a, b).
Conclusion: c = gcd(a, b).
For lcm , let .
• Clearly a | d, b | d, so d is a common multiple .
• Thus, d ≥ lcm(a, b).
• Must have , since | a and a | lcm(a, b).
• Similarly, must have .
• Thus, .
Conclusion: d = lcm(a, b).
Example: , and , so
Corollary 5: ab = gcd(a, b) · lcm(a, b)
Example: 4 · 10 = 2 · 20 = gcd(4, 10) · lcm(4, 10).
Remember: a ≡ b (mod m) means a and b have the same
remainder when divided by m .
• Equivalently : a ≡ b (mod m) iff m | (a − b)
• a is congruent to b mod m
Theorem 7: If (mod m) and (mod m),
• Conclusion: (mod m).
• Conclusion: .
Bottom line: addition and multiplication carry over to
the modular world.
Modular arithmetic has lots of applications.
• Here are four . . .
Problem: How can we efficiently store, retrieve, and
delete records from a large database?
• For example, students records.
Assume, each record has a unique key
• E.g. student ID, Social Security #
Do we keep an array sorted by the key?
• Easy retrieval but difficult insertion and deletion.
How about a table with an entry for every possible key?
• Often infeasible, almost always wasteful.
• There are 1010 possible social security numbers.
Solution : store the records in an array of size N, where N
is somewhat bigger than the expected number of records .
• Store record with id k in location h(k)
o h is the hash function
o Basic hash function: h(k) := k (mod N).
• A collision occurs when and .
o Choose N sufficiently large to minimize collisions
• Lots of techniques for dealing with collisions