Greatest Common Divisors (and Their Importance) [Video]

by Dave

We discuss several simple lemmas for greatest common divisors and linear combinations. I then prove Bezout’s identity to show that the greatest common divisor of two integers is the smallest linear combination. We also work through several elementary facts concerning relatively prime integers, and I present many examples.

In this video, I teach you: what the greatest common divisor is, what a linear combination is, and what relatively prime means. Then, importantly, I will state and prove Bezout’s identity that relates these three concepts together in a beautiful, meaningful way. I will then go into much more detail about linear combinations — after exploring some applications of Bezout’s identity and some examples of relatively prime integers.

Hi everyone, welcome back to my channel, I’m Dave. In today’s episode, I cover everything necessary to know about Greatest Common Divisors (GCDs). Finally, I also discuss Euclid’s Lemma and characterize the GCD of two integers.

Before you continue, you may want to checkout the video notes Greatest Common Divisors. You may also be interested to know that this video is part of the Number Theory Series playlist.

Greatest Common Divisors (and Their Importance)

This video for anyone looking for a working knowledge of GCDs and properties of divisibility.

How-to Learn Greatest Common Divisors

In this video, you study how to work with GCDs.

Step 1: Understand what linear combinations are and Bezout’s Theorem.

Firstly, read what linear combinations are and work out some simple basic examples.

Step 2: Know the proof of Bezout’s Theorem and some of its consequences. 

After that, slowly and carefully go over the Bezout’s Theorem’s proof and some heartier examples.

Step 3: Learn the difference between relatively prime, mutually relatively prime, and pairwise relatively prime.  

After that, work through some basic examples to understand the difference between these fundamental definitions.

Step 4: Know a characterization of the GCD and learn Euclid’s Lemma and its proof.

Finally, work through these proofs, and then, after some exercises, try them again but on your own.

What is the greatest common divisor (GCD)?

We say that an integer c is a common divisor of a and b if it divides both a and b. Since every integer has one as a divisor, every two integers have at least one common divisor, namely 1. Amongst all the common divisors of a and b, the GCD is the greatest common divisor.

What are relatively prime integers?

Greatest Common Divisors Colored fraction dices on blank white paper notebook on wooden desk selective focus on dices

Integers a and b are called relatively prime if their GCD is 1, which means that the only positive integer that divides them is 1.  

What are linear combinations?

Given two integers a and b, not both zero, we can form linear combinations of a and b by finding integers s and t such that s*a+t*b. Then s*a+t*b is called a linear combination of and b. For example, linear combinations of 2 and 3 are 5=1*2+1*3, 7=2*2+1*3, 25=5*2+5*3, etc.  

What is Bezout’s identity?

Bezout’s identity expresses the GCD of integers a and b as a linear combination of a and b. Additionally, the GCD of a and b is the smallest linear combination of a and b. Using Bezout’s identity, several elementary theorems concerning divisibility in the integers are easily proven. For example, Euclid’s lemma states that if integers a and c are relatively prime and c divides a, then c and b are relatively prime. 

In conclusion, I want to turn it over to you. 

Which do you like better Euclid’s Lemma or Bezout’s Theorem for GCDs? 

So, either way, let us know what you think in the comments for this video: Greatest Common Divisors right now.