Divisibility, Factors and Euclid's Algorithms

An outline of the fundamentals of number theory
Cryptography is built on the foundations of algebra and number theory, which we will hopefully cover well enough here.

Divisibility

aa
is said to be divisible by
bb
if there is another integer
cc
such that
a=bca=bc
. In this case,
bb
is said to be a factor of
aa
. This is denoted by
aba \mid b
if
aa
divides
bb
, and
aba \nmid b
if it does not.

Greatest Common Divisor

Given two integers
aa
and
bb
, the greatest common divisor
gcd(a,b)gcd(a,b)
(also known as the highest common factor) is the largest integer
pp
where
pap \mid a
and
pbp \mid b
.

Euclidean Algorithm

Given
aa
and
bb
, we can write an equation linking the two:
a=bq+ra = b \cdot q + r
​Where
qq
and
rr
are integers which fit the equation with
r<br < b
. Basically,
bb
divides into
aa
a maximum of
qq
times with a remainder of
rr
. But here's where the trick lies.
Every term added together in that equation must be divisible by
gcd(a,b)gcd(a,b)
because if we treat the gcd as
gg
we can say that
a=k1g,b=k2ga=k_1g,b=k_2g
​:
k1g=k2gq+rk_1g = k_2g \cdot q + r
Meaning
rr
has to be some integer multiple of
gg
​.
But now, if we think outside the box, we realise that both
bb
and
rr
are divisible by
gcd(a,b)gcd(a,b)
... so we can just calculate
gcd(b,r)gcd(b, r)
!
This is quite a leap forward which will require a bit of thinking, but let's break it down algebraically:
a=bq0+r1b=r1q1+r2r1=r2q2+r3r2=r3q3+r4a = b \cdot q_0 + r_1 \\ b = r_1 \cdot q_1 + r_2 \\ r_1 = r_2 \cdot q_2 + r_3 \\ r_2 = r_3 \cdot q_3 + r_4 \\
And so on. But when does it stop? When do we stop taking the GCD? Well we can stop taking the GCD once
rn=0r_n = 0
, in which case
rn1rn2r_{n-1} \mid r_{n-2}
and as a result we can take
rn1r_{n-1}
as the GCD!
I highly recommend you think about this for a bit until it makes sense to you, and make sure to use other resources if it helps!

Example

Let’s say we want to find the GCD of 8075 and 16283. First, we can write it in the form
a=bq+ra= b \cdot q+r
:
16283=80752+13316283 = 8075·2 + 133
And now we attempt to calculate the GCD of 8075 and 133.
8075=13360+95133=951+3895=382+1938=192+08075 = 133 \cdot 60 + 95 \\ 133 = 95 \cdot 1 + 38 \\ 95 = 38 \cdot 2 + 19 \\ 38 = 19 \cdot 2 + 0
Therefore the GCD of 16283 and 8075 is 19.

Extended Euclidean Algorithm

We can take the Euclidean Algorithm a step further and calculate, in addition to the GCD,
u,vZu,v \in \mathbb{Z}
for
a,ba,b
which sum to the GCD, i.e.
au+bv=gcd(a,b) au + bv = gcd(a,b)
This extension of the algorithm is invaluable for calculating modular inverses of numbers and is based on using the Euclidean Algorithm to calculate the GCD then writing it in terms of other numbers, repeating the process for the smallest non-GCD number until we reach an equation with only the GCD and the two starting numbers. Let's work with the example above, writing an equation for the GCD:
19=9538219 = 95 - 38 \cdot 2
Now 38 is the smallest non-GCD number, and we can write it in terms of the larger number in the sequence of equations written in the example, then repeat for the next smallest:
19=95382=95(133951)2=95(1332+952)=953+1332=(8075+13360)3+1332=80753+133180+1332=80753+133182=80753+(16283+80752)182=80753+16283182+8075364=8075367+1628318219 = 95 - 38 \cdot 2 \\ = 95 - (133 - 95 \cdot 1) \cdot 2 \\ = 95 - (133 \cdot 2 + 95 \cdot -2) \\ = 95 \cdot 3 + 133 \cdot -2 \\ = (8075 + 133 \cdot -60) \cdot 3 + 133 \cdot -2 \\ = 8075 \cdot 3 + 133 \cdot -180 + 133 \cdot -2 \\ = 8075 \cdot 3 + 133 \cdot -182 \\ = 8075 \cdot 3 + (16283 + 8075 \cdot -2) \cdot -182 \\ = 8075 \cdot 3 + 16283 \cdot -182 + 8075 \cdot 364 \\ = 8075 \cdot 367 + 16283 \cdot -182
Therefore our equation
au+bv=gcd(a,b)au + bv = gcd(a,b)
is as follows:
16283182+8075367=1916283 \cdot -182 + 8075 \cdot 367 = 19