English | Español

Try our Free Online Math Solver!

Online Math Solver

 

 

 

 

 

 

 

 
 
 
 
 
 
 
 
 

 

 

 
 
 
 
 
 
 
 
 

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


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 | 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
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 pi 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 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

Prev Next