English | Español

# Try our Free Online Math Solver!

Online Math Solver

 Depdendent Variable

 Number of equations to solve: 23456789
 Equ. #1:
 Equ. #2:

 Equ. #3:

 Equ. #4:

 Equ. #5:

 Equ. #6:

 Equ. #7:

 Equ. #8:

 Equ. #9:

 Solve for:

 Dependent Variable

 Number of inequalities to solve: 23456789
 Ineq. #1:
 Ineq. #2:

 Ineq. #3:

 Ineq. #4:

 Ineq. #5:

 Ineq. #6:

 Ineq. #7:

 Ineq. #8:

 Ineq. #9:

 Solve for:

 Please use this form if you would like to have this math solver on your website, free of charge. Name: Email: Your Website: Msg:

# 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