Sample Problem 1. What is the greatest common divisor of 388899 and 388877 (find it without a calculator)?
We want just go ahead and factor both numbers and compare factorization, but clearly that won't work. Who would want to factor those huge numbers? There must be a better way. Well, these two numbers do appear to be fairly close together, so maybe we would do something wit their difference, or some other smaller quantity. Well, if \(\gcd(388899,388877)=a\), then we get that \(388899=a\cdot q\) and \(3888877=a\cdot t\) for integers \(a, q\), and \(t\).
But this gives us exactly what we wanted! This lets us realize the \(gcd(a\cdot q, a\cdot t)=\gcd(a\cdot q- a\cdot t, a\cdot t)=a\) because \(a\cdot q- a\cdot t = a(q-t)\). Thus, we have \(\gcd(388899,388877)=\gcd(388899-388877, 388877)=\gcd(3888777,22)\). Now, we simply can check to see if 388877 is divisible by 2 or 11. It is clearly not even, and using the trick to see if a number is a multiple of 11 we find that 3+8+7-8-8-7=-5, so 388877 is not a multiple of 11. Thus, these two numbers are relatively prime or, in other words, have a greatest common divisor of 1.
But this gives us exactly what we wanted! This lets us realize the \(gcd(a\cdot q, a\cdot t)=\gcd(a\cdot q- a\cdot t, a\cdot t)=a\) because \(a\cdot q- a\cdot t = a(q-t)\). Thus, we have \(\gcd(388899,388877)=\gcd(388899-388877, 388877)=\gcd(3888777,22)\). Now, we simply can check to see if 388877 is divisible by 2 or 11. It is clearly not even, and using the trick to see if a number is a multiple of 11 we find that 3+8+7-8-8-7=-5, so 388877 is not a multiple of 11. Thus, these two numbers are relatively prime or, in other words, have a greatest common divisor of 1.
This method that we just saw seems pretty useful in helping us find the greatest common divisor of two large numbers. But, what if our numbers don't have as small or easy to test out of a difference? Let's try, for example, finding the greatest common divisor of 71 and 193. Now, these numbers are smaller and we probably could factor them, but the point here is to explore our previous method and to see if we can take it all the way to the answer that we want. We will start the same as we did last time. \(gcd(71,193)=gcd(122,73)\). However, the first number is still bigger than the second number. This brings us to an important concept: using the exact same reasoning as for one subtraction, we don't just have to subtract once; we can subtract one number from the other until our first number is smaller than the second! In other words, we can replace a number with its remainder when divided by the other number (note that this just repeated subtraction, and sometimes repeated subtraction is easier than actually trying to divide the number). Therefore, we have \(\gcd(71,193)=\gcd(71,51)\).
We could again easily factor here, but we still wan't to try to discover a whole process to try to get us to the end (we are experimenting with smaller numbers because they are easier to think about, but we want to make a process that will work for larger numbers as well). Well, now we are just back where we started, but with slightly smaller numbers. However, this is exactly what we wanted! We can just repeat what we just did over and over again to get to smaller and smaller numbers. Lets use this to finish out our problem: \(\gcd(71,51)=\gcd(51,20)=\gcd(11,20)=\gcd(9,11)=\gcd(2,9)=\gcd(1,2)=\gcd(1,0)=1\).
Now, we could stopped this process much earlier and easily seen our answer, but we continued it on until we had a 0 to show something: we did end up being able to get a 0. In fact, if \(\gcd(a,b)=d\), then we can get use our method to get \(\gcd(a,b)\) to \(\gcd(0,d)\) (remember that 0 is a multiple of every number because any number times 0 equals 0). Now, you might be thinking, that's nice and all, but why do I need to know that we can always reach a zero to find the greatest common divisor of two numbers? Couldn't I have stopped much earlier, have done less work, and have gotten answer just as easily? The answers to these questions are that you don't need to know this to find the greatest common divisor, yes you could have stopped earlier, yes you could have could have done less work, and yes, if you wanted to find the greatest common divisor, you probably should have stopped earlier. But, isn't finding the greatest common divisor exactly what this algorithm was designed to do? The answer, again, is yes, that is what we designed it to do, but just because we designed an algorithm to do one thing doesn't mean it can't do another (now this isn't to say that you shouldn't use this algorithm to find the greatest common divisor of large numbers; you should, as this algorithm makes it much easier). We will see another way to use this algorithm we just discovered, which is called the Euclidean Algorithm as you may have guessed. in the Diophantine equations lesson.
Just to make sure you understand the Euclidean Algorithm fully, we will go through another full example of it.
We could again easily factor here, but we still wan't to try to discover a whole process to try to get us to the end (we are experimenting with smaller numbers because they are easier to think about, but we want to make a process that will work for larger numbers as well). Well, now we are just back where we started, but with slightly smaller numbers. However, this is exactly what we wanted! We can just repeat what we just did over and over again to get to smaller and smaller numbers. Lets use this to finish out our problem: \(\gcd(71,51)=\gcd(51,20)=\gcd(11,20)=\gcd(9,11)=\gcd(2,9)=\gcd(1,2)=\gcd(1,0)=1\).
Now, we could stopped this process much earlier and easily seen our answer, but we continued it on until we had a 0 to show something: we did end up being able to get a 0. In fact, if \(\gcd(a,b)=d\), then we can get use our method to get \(\gcd(a,b)\) to \(\gcd(0,d)\) (remember that 0 is a multiple of every number because any number times 0 equals 0). Now, you might be thinking, that's nice and all, but why do I need to know that we can always reach a zero to find the greatest common divisor of two numbers? Couldn't I have stopped much earlier, have done less work, and have gotten answer just as easily? The answers to these questions are that you don't need to know this to find the greatest common divisor, yes you could have stopped earlier, yes you could have could have done less work, and yes, if you wanted to find the greatest common divisor, you probably should have stopped earlier. But, isn't finding the greatest common divisor exactly what this algorithm was designed to do? The answer, again, is yes, that is what we designed it to do, but just because we designed an algorithm to do one thing doesn't mean it can't do another (now this isn't to say that you shouldn't use this algorithm to find the greatest common divisor of large numbers; you should, as this algorithm makes it much easier). We will see another way to use this algorithm we just discovered, which is called the Euclidean Algorithm as you may have guessed. in the Diophantine equations lesson.
Just to make sure you understand the Euclidean Algorithm fully, we will go through another full example of it.
Sample Problem 2. Find \(\gcd(976,522)\).
Using the Euclidean Algorithm, we get \(\gcd(976, 522)=\gcd(522,454)=\gcd(454, 68)=\gcd(68,46)=\gcd(46,22)\). Now, we could stop here and just see that their greatest common divisor is 2, and for this problem, that would be perfectly correct. However, just to make sure you understand, we will finish off this example. \(\gcd(46,22)=\gcd(2,22)=\gcd(0,2)=2\). Notice that, as expected, we do end up getting to a 0 and a 2 in the end.
Exercises
- Prove that if \(\gcd(a,b)=d\), then we must be able to use the Euclidean Algorithm to get our \(\gcd\) down to \(\gcd(d,0)\).
- Using the Euclidean Algorithm, express 1 in the form \(x\cdot 13 + y\cdot 28\) for integral (not necessarily positive) \(x\) and \(y\) (do not guess and check; use the Euclidean Algorithm in a way that you are guaranteed to find a solution).
Solution 1
We will prove this by showing that applying the Euclidean Algorithm to \(\gcd(a,b)\) is bound to eventually yield \(\gcd(d,0)\). To start, we already know that if we ever get down to \(\gcd(g,0)\), then g=d because we already proved that the Euclidean Algorithm will yield the correct greatest common divisor. Next, if at any point \(\gcd(a,b)\) is reduced to \(\gcd(r,r)\), then we apply the Euclidean Algorithm again to get to \(\gcd(r,0)\), meaning r=d, and we have achieved the desired outcome.
We will then assume for the sake of contradiction that we can go without ever reaching two equal numbers. Thus, if repeatedly applying the Euclidean Algorithm doesn't reduce us to a case with two equal numbers, one number will always be greater than the other. Thus, if one number is always greater, we can continually take the lesser number and subtract it from the greater. This process will clearly never make one of the two numbers negative because or non-integral because we are taking one integer minus a smaller integer. However, both numbers are finite, so if we repeat this process an arbitrarily large number of times we will be subtract at least one from one of the numbers each time, so we will be subtracting an arbitrarily large amount from their finite sum. However, this is a contradiction because this would make at least one number negative, but we said earlier that they must both be positive.
Therefore, we will eventually reach \(\gcd(d,d)=\gcd(d,0)\), as desired.
We will then assume for the sake of contradiction that we can go without ever reaching two equal numbers. Thus, if repeatedly applying the Euclidean Algorithm doesn't reduce us to a case with two equal numbers, one number will always be greater than the other. Thus, if one number is always greater, we can continually take the lesser number and subtract it from the greater. This process will clearly never make one of the two numbers negative because or non-integral because we are taking one integer minus a smaller integer. However, both numbers are finite, so if we repeat this process an arbitrarily large number of times we will be subtract at least one from one of the numbers each time, so we will be subtracting an arbitrarily large amount from their finite sum. However, this is a contradiction because this would make at least one number negative, but we said earlier that they must both be positive.
Therefore, we will eventually reach \(\gcd(d,d)=\gcd(d,0)\), as desired.
Solution 2
First, note that 13 and 28 are clearly relatively prime. Thus, using the Euclidean Algorithm will eventually get us to \(\gcd(0,1)\). In other words, we created the 1 by subtracting two numbers, both of which were formed by subtracting two larger numbers, and so on until each number was formed from our original two numbers. Thus, we will essentially start from the bottom of the euclidean algorithm and use substitutions to get us back to only using the first two numbers. We will start by computing \(\gcd(13,28)\) and showing each step.
\(\begin{align*}
&\gcd(13,28)\\
&=\gcd(2,13)\ 28-2\cdot 13 =2\\
&=\gcd(1,2)\ 1=13-2\cdot 6
\end{align*}\)
Now, we could have gone one step further, but we only needed to prove that we reached a 0 because it helped us prove we would reach the greatest common divisor as one of the two numbers as well. This is because now that we have a 1, we have all of the substitutions we need (we aren't trying to find solutions to \(x\cdot 13 + y\cdot 28=0\)). Continuing on to do the problem, we just substitute as we described before.
\[1\]
\[=13-6\cdot 2\]
\[=13-6\cdot (28-2\cdot 13)\]
\[=13+12\cdot 13 -6\cdot 28\]
\[=13\cdot 13+(-6)\cdot 12\]
Thus, we get x=13, y=-6 as a solution using the euclidean algorithm. You'll see this more in the Diophantine Equations lesson and you'll how this is useful after the Modular Arithmetic lessons.
\(\begin{align*}
&\gcd(13,28)\\
&=\gcd(2,13)\ 28-2\cdot 13 =2\\
&=\gcd(1,2)\ 1=13-2\cdot 6
\end{align*}\)
Now, we could have gone one step further, but we only needed to prove that we reached a 0 because it helped us prove we would reach the greatest common divisor as one of the two numbers as well. This is because now that we have a 1, we have all of the substitutions we need (we aren't trying to find solutions to \(x\cdot 13 + y\cdot 28=0\)). Continuing on to do the problem, we just substitute as we described before.
\[1\]
\[=13-6\cdot 2\]
\[=13-6\cdot (28-2\cdot 13)\]
\[=13+12\cdot 13 -6\cdot 28\]
\[=13\cdot 13+(-6)\cdot 12\]
Thus, we get x=13, y=-6 as a solution using the euclidean algorithm. You'll see this more in the Diophantine Equations lesson and you'll how this is useful after the Modular Arithmetic lessons.