Common Divisors
and Euclid’s Algorithm
By David Phillips
Areas of cryptography deal with the notion of factoring very large integers. Today I am going to write about one such topic, Common Divisors, which have applications to the field of cryptography.
What
is Division?
Of course you know what division is. When I say “What is 9 / 3?” You instinctively know that the answer is 3 because 3 divides 9 three times. Mathematically, we define the division of two numbers ‘a’ and ‘b’ in terms of multiplication as follows:
a = (k)(b) + r
where k is the ‘quotient’ and r is the remainder.
For example, we can express 9 / 3 in terms of multiplication as:
9 = (3)(3) + 0
where a = 9, b = 3, k = 3, and r = 0
If we wanted to express 9 / 5 we would have
9 = (1)(5) + 4
where a = 9, b = 5, k = 1, and r = 4
Modular
Arithmetic
Modular arithmetic simply involves calculating the remainder (or ‘residual’) value that is left over from a division operation.
For example, when I try to divide 9 / 5, the result is 1 with a remainder of 4 left over. We define the modulo operator which yields the remainder of a division operation. This operation is typically expressed as ‘a mod b’ or ‘a % b’. I shall use the first form for the remainder of this article. The operation ‘a mod b’ is read as ‘the remainder from dividing a by b’.
For example,
9 / 5 = 1
9 mod 5 = 4
9 / 3 = 3
9 mod 3 = 0
So going back to our division equation in the paragraph above:
a = (k)(b) + r
We can interchange r with (a mod b) since they both mean the same thing:
a = (k)(b) + (a mod b)
What
is a Divisor?
A divisor is an integer that divides another integer without yielding a remainder. For example, the divisors of the number 12 are {1, 2, 3, 4, 6, 12} because
12 / 1 = 12
12 / 2 = 6
12 / 3 = 4
12 / 4 = 3
12 / 6 = 2
12 / 12 = 1
Notice that 5 is not a divisor of 12 because 5 only goes into 12 twice (to make 10) and then leaves a remainder of 2. A divisor strictly implies a 0 remainder.
To phrase it another way by referring back to our division equation a = (k)(b) + r
We would say that if b is a divisor of a then the following is satisfied:
a = (k)(b) + 0
If I gave you the set of integers {15, 10} and asked you for the set of common divisors, I would be asking you to tell me what the integers are that divide both 10 and 15 without any remainder left over. We could answer this by constructing a set of the divisors for each number and then keep the values that intersect both sets.
Divisors of 15 are {1, 3, 5, 15}
Divisors of 10 are {1, 2, 5, 10}
The values that intersect both sets are {1, 5}, thus we would conclude that the common divisors of {15, 10} are {1, 5}. We would say that the Greatest Common Divisor (gcd) of {15, 10} is 5 because 5 is the greatest element in the set of common divisors {1, 5}.
I want to mention some notation here. We shall use the bar character ‘|’ which is read as ‘divides’. When we say that an integer ‘divides’ another integer, we are implying that it divides the integer with no remainder. Thus, we say:
1|15 which means 1 divides 15 with no remainder: 15 = (15)(1) + 0
3|15 which means 3 divides 15 with no remainder: 15 = (5)(3) + 0
5|15 …. : 15 = (3)(5) + 0
15|15 …. : 15 = (1)(15) + 0
The preceding example was very trivial and should be very intuitive to us humans who have memorized basic math and are able to just look at the example and immediately figure out the solution. However, what if I asked you:
What is the greatest common divisor of {1234567890, 987654321}? Furthermore, how could a machine like a computer derive the solution?
Your first guess might to be to try dividing integers one by one in the following fashion until you found a result with no remainder:
1234567890 / 987654321 = 1.249…
1234567890 / 987654320 = 1.249…
1234567890 / 987654319 = 1.249…
1234567890 / 987654318 = 1.249…
1234567890 / 987654317 = 1.249…
1234567890 / 987654316 = 1.249…
1234567890 / 987654315 = 1.249…
1234567890 / 987654314 = 1.249…
As you can probably imagine, this is going to take an extremely long time to figure out if we try to solve the problem this way.
The actual answer gcd(1234567890, 987654321) = 9 can actually be solved in 5 steps using Euclid’s Algorithm.
What
Is
Ok, now we get to have some fun. Rather than just hand you some equation that fell out the sky from god that makes no sense, we are going to start from the beginning and derive it ourselves.
Let’s just experiment with some ideas and see where it leads us.
We are given two integers ‘a’ and ‘b’ where a > b (just like in our example above)
Let the integer ‘d’ be a common divisor of {a, b}
So we first observe that d|a and
d|b since d is assumed to be
a common divisor of a and
b.
So let’s re-write a and b in terms of d using our division equation.
a = (k1)(d) +
r1
b = (k2)(d) +
r2
Ok great, we are getting somewhere. We now have a and b both in terms of d so let’s solve one of them for d and then substitute the result into the other in order to obtain a single equation.
We’ll solve d in terms of b. We have:
b = (k2)(d) +
r2
Therefore,
(k2)(d) = b – r2 (using simple Algebra)
(d) = (b – r2) / (k2) (using simple Algebra)
Great, so we now have d in terms of
b.
So lets substitute it into our equation for
a.
We have
a = (k1)(d) +
r1
Therefore,
a = (k1)( (b – r2) / (k2)) + r1 (using Substitution)
Let k3 = k1 / k2 then
a = (k3)(b – r2) + r1 (using Substitution)
= (k3)(b) – (k3)(r2) + r1 (using Multiplication)
= (k3)(b) + r1 – (k3)(r2) (just re-arranging)
Let r3 = r1 – (k3)(r2) then
a = (k3)(b) + r3 (using Substitution)
Cool, so we have just shown that if d|a
and d|b then we can express
a and b in the form of a single
divison equation: a = (k)(b) + r
So let’s continue to examine this.
Since d|a, it must be true that d|((k)(b) + r) (because of the equality ‘=’)
Since d|b, it is trivially obvious that
d|(k)(b)
Since d|a and
d|(k)(b), it must be true that d|r
(because otherwise d could not divide
a which would contradict our assumption
that d is a divisor of
a)
Since d|r and
r = (a mod b), it must be true that d|(a
mod b)
Now this is very interesting. We have just shown that if d is a common divisor of a and b, it is also a common divisor of (a mod b). This means that the set {a, b, (a mod b)} all have the same common divisors.
So what? What is the big deal? Well let’s suppose that we are asked to find the greatest common divisor of integers a and b where a > b.
Let g = gcd(a,b)
Then g is a common divisor of a and b (by definition of gcd)
Since {a, b, (a mod b)} all have the same common divisors,
g = gcd(a,b) = gcd(b, (a mod b))
Now we have what we need to solve our example problem from before!
Previous
Example Now Solvable
What is the greatest common divisor of {1234567890, 987654321}?
Here we go. Now that we know gcd(a,b) = gcd(b, a mod b) we can recursively reduce the factors until we get to our result:
gcd(1234567890, 987654321)
= gcd(987654321, 1234567890 mod 987654321) = gcd(987654321, 246913569)
= gcd(246913569, 987654321 mod 246913569) = gcd(246913569, 45)
= gcd(45, 246913569 mod 45) = gcd(45, 9)
= gcd(9, 45 mod 9) = gcd(9, 0)
= 9
We have just solved the greatest common divisor for two large integers in 5 steps using what is known as Euclid’s Algorithm.