Try our Free Online Math Solver!

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]
Some Consequences
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.
Proof:
• 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  a_{i}
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  a_{i} 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
induction.
• 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 p_{i} are primes and .
• Some could be 0.
Then
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).
Suppose .
• 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)
Proof:
Example: 4 · 10 = 2 · 20 = gcd(4, 10) · lcm(4, 10).
Modular Arithmetic
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),
then
Proof: Suppose
So
• Conclusion: (mod m).
For multiplication:
• Conclusion: .
Bottom line : addition and multiplication carry over to
the modular world.
Modular arithmetic has lots of applications.
• Here are four . . .
Hashing
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 10^{10} 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
Prev  Next 