Modular Arithmetic

Tags

math

When a number \( A \) is divided by another number \( B \) we get an integer quotient \( Q \) and a remainder \( R \). Modular arithmetic is a system of arithmetic numbers concerned only with the remainder of an expression.

\begin{align} \frac{A}{B} &= Q \; \text{remainder} \; R \
A \mod B &= R \label{eq:mod-remainder} \end{align}

Modulo

The modulo operator, \( \mod \), asserts that the result of the expression is equivalent to some arbitrary multiple of the modulus \( B \) plus \( R \). For example, as shown by eq:mod-remainder, \( \frac{13}{5} = 2 \; \text{remainder} \; 3 \) meaning \( 13 \mod 5 = 3 \) (spoken as 13 mod 5 is congruent to 3). This tracks regardless of how many multiples of the modulus goes into \( A \).

• \( 3 \mod 5 = 3 \)
• \( 8 \mod 5 = 3 \)
• \( 13 \mod 5 = 3 \)
• \( 18 \mod 5 = 3 \)
• \ldots

The cyclical nature of the modulo operator, where the result wraps back around to 0 after \( A \) exceeds \( B \), can be visualised as a circle such as fig:modulo-clock. Finding the remainder is simply the process of travelling along the circle clockwise until you reach \( A \). For example finding the position of 13 (\( 13 \mod 12 \)) involves one complete revolution of 12 followed by a movement of (the remainder) 1.

The analogy of a clock also translates with negative numbers. Beginning with 0 at the top and treating clockwise rotations as a positive displacement, we can formulate negative displacements as anti-clockwise rotations. For example \( -5 \mod 3 \) is equivalent to one full rotation reducing to \( -2 \) at position 0. We then move anti-clockwise once to reach position 2 and once more to finish at position 1. This can be visualised in fig:modulo-clock-anti-clockwise.

Note: how negative modulo immediately jumps to the largest possible value of the modulus. \( (-1) \mod x \equiv x - 1 \; \forall x \geq 2 \). So \( -1 \mod 3 = 2 \).

Congruence Modulo

Is an extension of the concept of modulo in modular arithmetic where we associate all integers with the same remainder as part of the same equivalence class. This is denoted as \( X \equiv Y (\mod Z) \) and essentially states \( X \mod Z = Y \mod Z \), or equivalently \( X \) is congruent to \( Y \) modulo \( Z \). That is \( X \) divided by \( Z \) always has the same remainder as \( Y \) divided by \( Z \).

For example \( 26 \mod 5 = 1 \) and \( 11 \mod 5 = 1 \) therefore \( 26 \equiv 11 (\mod 5) \). Both 26 and 11 are part of the same equivalence class of \(1\). Warn this isn't equivalent to saying \( 26 = 11 \mod 5 \). Because \( 11 \mod 5 = 1 \) doing so would be the same as saying \( 26 = 1 \). Congruence is not simply modulo.

Equivalence Relation

Congruence modulo can be shown to be an equivalence relation.

Equivalent Statements

Suppose we have the congruence \( A \equiv B (\mod C) \). From this it follows:

\begin{align} A &\equiv B (\mod C) \
A \mod C &= B \mod C \
A &= K_1 \times C + R \
B &= K_2 \times C + R \end{align}

This implies both \( A \) and \( B \) are equal to some multiple of \( C \) plus the same remainder \( R \). Now consider what if we subtract \( A \) from \( B \).

\begin{align} A - B &= K_1 \times C + R - (K_2 \times C - R) \\

    &= K\_1 \times C - K\_2 \times C \\\\
    &= C \times (K\_1 - K\_2)
      \label{eq:congruence-equiv}

\end{align}

It can be shown that \( (A - B) \) is equal to some multiple of \( C \) meaning \( (A - B) \) is a factor of (or divides by) \( C \).

Arithmetic Operations

Addition and Subtraction proof

Addition and subtraction in modular arithmetic can be shown to follow eq:mod-addition.

\begin{align} (A + B) \mod C = (A \mod C + B \mod C) \mod C \label{eq:mod-addition} \end{align}

From the quotient remainder theorem we can redefine:

• \( A = C \times Q_1 + R_1 \) where \( 0 \leq R_1 < C \) and \( Q_1 \) is some integer. \( A \mod C = R_1 \)
• \( B = C \times Q_2 + R_2 \) where \( 0 \leq R_2 < C \) and \( Q_2 \) is some integer. \( B \mod C = R_2 \)

Firstly lets observe that \[ (A + B) = C \times (Q_1 + Q_2) + R_1 + R_2 \] Now lets expand the left and right hand sides of the addition equation above to show that both sides are equivalent.

\begin{align} \label{eq:mod-add-lhs} \text{LHS} &= (A + B) \mod C \\

         &= (C \times (Q\_1 + Q\_2) + R\_1 + R\_2) \mod C \\\\
         &= (R\_1 + R\_2) \mod C

\end{align}

\begin{align} \label{eq:mod-add-rhs} \text{RHS} &= (A \mod C + B \mod C) \mod C \\

         &= (R\_1 + R\_2) \mod C

\end{align}

eq:mod-add-lhs shows the expansion of the left hand side eq:mod-add-rhs shows the expansion of the right hand side. Note: In the first-case we can eliminate multiples of \( C \) when taking \( \mod C \). Both expansions are equivalent, \( \text{LHS} = \text{RHS} = (R_1+R_2) \mod C \), meaning eq:mod-addition holds for any \(A\), \(B\) and \(C\).

Example of Modular Addition

Consider \( A=14, B=17, C=5 \).

\begin{align} \label{eq:mod-add-eg-lhs} (A + B) \mod C &= (14 + 17) \mod 5 \\

             &= 31 \mod 5 \\\\
             &= 1

\end{align}

\begin{align} \label{eq:mod-add-eg-rhs} (A \mod C + B \mod C) \mod C &= (14 \mod 5 + 17 \mod 5) \mod 5 \\

                           &= (4 + 2) \mod 5 \\\\
                           &= 1

\end{align}

Multiplication proof

Multiplication in modular arithmetic can be shown to follow eq:mod-multiplication.

\begin{align} (A \times B) \mod C &= (A \mod C \times B \mod C) \mod C \label{eq:mod-multiplication} \end{align}

From the quotient remainder theorem we can redefine:

• \( A = C \times Q_1 + R_1 \) where \( 0 \leq R_1 < C \) and \( Q_1 \) is some integer. \( A \mod C = R_1 \)
• \( B = C \times Q_2 + R_2 \) where \( 0 \leq R_2 < C \) and \( Q_2 \) is some integer. \( B \mod C = R_2 \)

\begin{align} \label{eq:mod-mul-lhs} \text{LHS} &= (A \times B) \mod C \\

         &= ((C \times Q\_1 + R\_1) \times (C \times Q\_2 + R\_2)) \mod C \\\\
         &= (C \times Q\_1 \times C \times Q\_2 + C \times Q\_1 \times R\_2 + C \times Q\_2 \times R\_1 + R\_1 \times R\_2) \mod C \\\\
         &= (R\_1 \times R\_2) \mod C

\end{align}

\begin{align} \label{eq:mod-mul-lhs} \text{RHS} &= (A \mod C \times B \mod C) \mod C \\

         &= ((C \times Q\_1 + R\_1) \mod C \times (C \times Q\_2 + R\_2) \mod C) \mod C
         &= (R\_1 \times R\_2) \mod C

\end{align}

Just like the proof for addition we can show that the left hand side and right hand side of eq:mod-multiplication are equivalent and therefore the equation holds for all values of \( A \), \( B \) and \( C \).

Example of Modular Multiplication

Consider \( A=4, B=7, C=6 \).

\begin{align} \label{eq:mod-mul-eg-lhs} (A \times B) \mod C &= (4 \times 7) \mod 6 \\

             &= 28 \mod 6 \\\\
             &= 4 \mod 6
             &= 4

\end{align}

\begin{align} \label{eq:mod-mul-eg-rhs} (A \mod C \times B \mod C) \mod C &= (4 \mod 6 \times 7 \mod 6) \mod 6 \\

                           &= (4 \* 1) \mod 6 \\\\
                           &= 4

\end{align}

Exponentiation proof

Exponentiation in modular arithmetic can be shown to follow eq:mod-exp.

\begin{align} A^B \mod C = ({(A \mod C)}^B) \mod C \label{eq:mod-exp} \end{align}

The proof for this property is just repeated applications of the proof for multiplication.

\begin{align*} A^B \mod C &= (A^{B-1} \times A) \mod C \\

         &= (A^{B-1} \mod C \times A \mod C) \mod C \\\\
         &= ((A^{B-2} \times A) \mod C \times A \mod C) \mod C \\\\
         &= ((A^{B-2} \mod C \times A \mod C) \mod C \times A \mod C) \mod C \\\\
         &= (A^{B-2} \mod C \times A \mod C \times A \mod C) \mod C \\\\
         &= \dots \\\\
         &= (A \mod C \times A \mod C \times \dots \times A \mod C) \mod C \\\\
         &= ({(A \mod C)}^B) \mod C

\end{align*}

Fast Modular Exponention

Is a way to quickly calculate the exponent of a modular equation by exploiting the nature of squared terms.

For example consider \[ 7^{256} \mod 13 \] First we can calculate \( 7^{2} \mod 13 \).

\begin{align*} 7^2 \mod 13 &= (7^1 \times 7^1) \mod 13 \\

          &= 49 \mod 13 \\\\
          &= 10

\end{align*}

Then we consider \( 7^{4} \mod 13 \).

\begin{align*} 7^4 \mod 13 &= (7^2 7^2) \mod 13 \\

          &= (10 \times 10) \mod 13 \\\\
          &= 9

\end{align*}

This process can be repeated 5 times to get \( 7^{256} \mod 13 \).

• Non-Binary Fast Modular Exponention

  We can do this for none powers-of-2 exponents by writing out the exponent in binary and then calculating the modulo of the summation of the base-2 exponents.

  To simplify this description consider \[ 5^{17} \mod 19 \] We can rewrite 117 in binary as \( 1110101 \) which can be interpreted as \( 2^0 + 2^2 + 2^4 + 2^5 + 2^6 = 1 + 4 + 16 + 32 + 64 = 117 \). This can then be further expanded in the original modulo equation to give us a bunch of smaller products to the same modulus.

  \begin{align*} 5^{117} \mod 19 &= 5^{1 + 4 + 16 + 32 + 64} \mod 19 \\

                &= (5^1 \times 5^4 \times 5^{16} \times 5^{32} \times 5^{64}) \mod 19
                &= (5^1 \mod 19 \times 5^4 \mod 19 \times 5^{16} \mod 19 \times 5^{32} \mod 19 \times 5^{64} \mod 19) \mod 19

  \end{align*}

  Furthermore the calculation is simplified because each smaller equation is useful in calculating the larger one. Knowing \( 5^{16} \mod 19 \) helps when calculating \( 5^{32} \mod 19 \) by the same property as regular fast modular exponention.

Modular Inverse

Modular arithmetic lacks a division operator but it supports the concept of modular inverses. The modular inverse of \( A (\mod C) \) is \( A^{-1} \). \( (A \times A^{-1}) \equiv 1 (\mod C) \) or equivalently \( (A \times A^{-1}) \mod C = 1 \).

Note: Only numbers coprime to \( C \), numbers that share no prime factors with \( C \), have a modular inverse \( (\mod C) \).

A naive method to find the modular inverse, of \( A \mod C \), has us:

1. Calculate \( A \times B \mod C \) for \( B \) values in the range \( [0, C) \).
2. Find the value of \( B \) that makes \( A \times B \mod C = 1 \).