One of the most common ways to reduce large numbers is through the process of division. While this basic arithmetic operation is something we should be familiar with, its application in cryptographic algorithms is of paramount importance. In this lesson, we will outline some very basic concepts pertaining to division and the division algorithm.

b|a

The b|a notation is used to imply that given a numeric integer value a and a nonzero divisor b, b is a divisor of a. Based on this logic, we can stipulate the following:

• a = ±1, if a|1

• a = ±b, if a|b

• b|0, for any b ≠ 0

• a|c, if a|b and b|c

• b|(mg + nh), if b|g and b|h for some m and n.

The division algorithm

$$a=qn + r ∣ 0≤r<n; q=⌊a/n⌋$$

The equation represents the division theorem, which is often referred to as the division algorithm. This theorem states that given a non-negative integer a and a non-negative division n, upon performing a division operation we would option some quotient value q and some remainder of the division r.

The equation can be diagrammatically represented as shown below for any a and any n.

Next: The Euclidean algorithm