The Power of one Prime and an Integer

Take a prime number p and another integer x with x != p, using those two numbers you are able to reach all integers out there in ℤ. All you need is a linear combination of p and x. Why? p as a prime number does not share any divisor with x, except for the number 1. Hence the greatest common divisor gcd(p,x) is equal to 1.

Using extended euclidean algorithm, we can trace down the way to gcd(p,x) while retaining each intermediate result as a linear combination of p and x. Eventually we’ll get a linear combination of the gcd:

a*p + b*x = 1

Such a linear combination yields the power to construct all integers in ℤ; just multiply it by any imaginable k ∈ ℤ.

Image by PublicDomainPictures from Pixabay

Example

p=157 and x=28, now let’s find gcd(157,28) using the extended euclidean algorithm. The last column reprents the gcd for each step, starting with gcd(157,28). It will be reduced in each step by subtracting the smaller from the larger number as often as possible. The first two columns represent the first gcd number as a linear combination of 157 and 28 (they are the coefficients of 157 and 28 respectively.) The next two columns do the same for the second gcd number. This allows us to finally extract the linear combination for 1.

157|28 |157|28 |gcd(p, x)
---|---|---|---|-----------
1  |0  |0  |1  |gcd(157,28)
1  |-5 |0  |1  |gcd(17, 28)
1  |-5 |-1 |6  |gcd(17, 11)
2  |-11|-1 |6  |gcd(6,  11)
2  |-11|-3 |17 |gcd(6,  5)
5  |-28|-3 |17 |gcd(1,  5)

The greatest common divisor of 157 and 28 is (without surprise) 1 and can be expressed as 5*157 — 28*28 = 1. This linear combination is able to produce any integer in ℤ space, much like unit vectors are able to produce any vector in vector space. Awesome! 🎉

Euclid’s Math

Here’s the math behind euclid’s algorithm from above.

If a number d divides a, we write d|a which expresses that the result of d/a is a whole number, not a fraction. For example 2|8 means 2 divides 8, and the result 4 is still a whole number. 2|5 is wrong, because 5/2 is 2.5 which is not a whole number. If d|a then a = d*k which says nothing more than: a can be written as a multiple of d. We do not really care what k is, we just know it exists.

d|a --> a = d*k
2|8 --> 8 = 2*k (in this case k=4)

So whenever a number d divides a number a, it means that we can multiply d by some other whole number k and the result will be a. 0 is special, because all numbers divide zero, the result will just always be 0. (On the other hand, 0 does not divide any number.) That means a|0 is always true, for all a’s.

The greatest common divisor of two numbers is written as d=gcd(a,b), so d in this case represents the greatest common divisor of a and b. Gcd can be defined mathematically by saying T(n) is the set of all divisors of n. We can then say gcd(a,b) is the largest element in the intersection of T(a) and T(b):

gcd(a,b) = max(T(a) ∩ T(b))
Example:
T(26) = { 1, 2, 13, 26 }
T(39) = { 1, 3, 13, 39 }
T(a) ∩ T(b) = { 1, 13 }
max({ 1, 13 }) = 13 = gcd(26,39)

One interesting case to notice is T(0) which is simply equal to ℤ, that means all numbers in ℤ divide 0. This has some relevant implications:

T(0) = ℤ
gcd(0,b) = max(ℤ ∩ T(b)) = max(T(b)) = b

Every integer divides itself, so the largest element in T(b) is always b and whatever that is, it will certainly be contained in ℤ, hence survive the intersection and be left as the largest element. Therefore gcd(0,b)=b.

(By the way, gcd(a,b)=gcd(b,a) because interesections are commutative, hence ordering does not matter.)

Now in order to calculate the greatest common divisor d (i.e. not searching for all divisors of both numbers and find the largest in the intersection), euclid thought about the properties of d, especially in relation to a and b. There is one decisive property about d; it divides both, a and b (that’s in the definition of greatest common divisor.) The rest of the argument is easier to make in math terms:

d = gcd(a,b) 
--> d|a --> a = d*k
--> d|b --> b = d*r
a-b = d*k - d*r
a-b = d(k-r)
d|d(k-r) therefore d|a-b

Now that we know d also divides a-b we can put a-b into gcd again: gcd(a,b) = gcd(a-b,b) and that makes it recursively smaller which is the basic idea of euclid’s algorithm: Removing the smaller of the two arguments from the larger as often as possible without going below 0 and then repeat that process, until one argument becomes 0 and we reach a gcd(0,b)=b situation.

We can also stop if one number becomes 1, because it will eliminate the other number to zero in the next step, no matter what the other number is. 1 then is the greates common divisor.