Greatest Common Divisor (GCD):
The GCD of two integers \(a\) and \(b\) not both zero, as the name says, is the largest of all the divisors they have in common. If the only divisor \(a\) and \(b\) have in common is \(1\) (gcd(a,b)=1), \(a\) and \(b\) are said to be relatively prime.
Finding GCD using Euclidean Algorithm:
To find \(gcd(a,b)=1\), assuming \(a>b\), we use the Euclidean Algorithm as follows:
- Divide \(a\) by \(b\) with remainder: \(a=b\times q_1+r_1\)
- Divide the previous divisor \((b)\) by the previous remainder \(\left(r_1\right)\) with remainder \(b=r_1\times q_2+r_2\)
Repeat step 2 until the remainder in the division is 0:
\(\begin{array}{c}b=r_1\cdot q_2+r_2\\\vdots\\r_{n-2}=r_{n-1}\cdot q_{n-1}+r_n\\r_{n-1}=r_n\cdot q_n+0\end{array}\)
- The most recent non-zero remainder is the GCD: \(\gcd(a,b)=r_n\)
Useful Fact: For all integers \(a, b, k\)
\(\gcd(a,b)=\gcd(a-kb,b)=\gcd(a,b-ka).\)
In words, subtracting a multiple of the second number from the first, or subtracting a multiple of the first number from the second does not change the GCD.
This can be used to simplify GCD calculations.
Example.
If \(a\) and \(b\) are relatively prime, find \(\gcd(a+7b,3a+22b).\)
Solution.
We can simplify the GCD by applying the above useful fact repeatedly. We can start by using the single \(a\) on the left side to cancel out the \(3a\) on the right.
\(\begin{aligned}
\gcd(a+7b,3a+22b)& =\gcd(a+7b,3a+22b-3(a+7b)) \\
&=\gcd(a+7b,b)
\end{aligned}\)
Then, we can remove the \(7b\) on the left with the \(b\) on the right.
\(\begin{aligned}
\mathrm{gcd}(a+7b,b)& =\gcd(a+7b-7(b),b) \\
&=\gcd(a,b)=1
\end{aligned}\)
Thus, \(\gcd(a+7b,3a+22b)=1\) and they are also relatively prime.
Example.
Calculate \(gcd(105,24)\).
Solution.
We follow the steps outlined above:
- Divide \(105\) by \(24\) with remainder: \(105=24\times4+9\)
- Divide \(24\) by \(9\) with remainder: \(24=9\times2+6\)
Keep dividing with remainder until we find a remainder of 0:
\(\begin{array}{c}9=6\times1+3\\6=3\times2+0\end{array}\)
- The remainder before we found a 0 was 3, so we have that \(gcd(105,24)=3\)
Bézout’s Identity:
Bézout’s identity says that for two integers \(a\) and \(b\) not both zero we can find \(\text{m,nL 口}\) so that \(am+bn=\gcd(a,b)\).
To find these integers \(m\) and \(n\) we perform the extended Euclidean Algorithm outlined as follows:
- Find \(gcd(a,b)\) by using the Euclidean Algorithm.
- In the divisions from the Euclidean Algorithm, solve each of the equations for the remainder:
\(\begin{gathered}
a=bq_{1}+r_{1} \Leftrightarrow r_1=a-bq_1 \\
\text{b=}r_1q_2+r_2 \Leftrightarrow r_2=b-r_1q_2 \\
\text{:} \\
r_{n-2}=r_{n-1}q_{n-1}+r_{n} \Leftrightarrow r_n=r_{n-2}-r_{n-1}q_{n-1}
\end{gathered}\) - Starting from the last remainder, substitute the remainders backwards into the equation until you have an equation with \(a\) and \(b\). When substituting, do not multiply numbers immediately. Instead, collect like-terms (this step will become clearer in the example). This process is called extended Euclidean Algorithm.
Example.
Find \(\text{m,nL 口}\) so that \(105m+24n=gcd(105,24).\)
Solution.
To do this we must follow the extended Euclidean Algorithm:
- From the previous example we know \(gcd(105,24)=3\), we also have the equations we will need for step 2.
- Solve the division equations for the remainder:
\(105=24\cdot4+9\Leftrightarrow9=105-24\cdot4\\24=9\cdot2+6\Leftrightarrow6=24-9\cdot2\\9=6\cdot1+3\Leftrightarrow3=9-6\cdot1\) - Start at the end and substitute all the remainders backwards:
\(\begin{aligned}
\text{3}& =9-6\times1 \\
\text{3}& =9-(24-9\times2)\times1 \\
\text{3}& = 9-24 +9\times 2 \\
\text{3}& =9\times3-24 \\
\text{3}& =(105-24\times4)\times3-24\\
\text{3}&=105\times3-24\times12-24 \\
\text{3}& =105\times3+24\times(-13)
\end{aligned}\)
\(\mathrm{Thus,~}105\times3+24\times(-13)=\gcd(105,24)\text{ , i.e., }m=3\mathrm{~and~}n=-13.\)