Modular Arithmetic Complete

Modular Arithmetic Complete#

Modular arithmetic is a system of arithmetic for integers, where numbers “wrap around” upon reaching a certain value, called the modulus. This means that after reaching the modulus, numbers start back at zero.

The basic operation in modular arithmetic is to find the remainder when one integer is divided by another (the modulus).

For a given modulus \(m\), any integer \(a\) can be expressed in modular arithmetic as:

\[ a \mod m \]

This represents the remainder when \(a\) is divided by \(m\).

For example:

\(7 \mod 5 = 2\) because \(7\) divided by \(5\) gives a quotient of \(1\) and a remainder of \(2\).
\(12 \mod 4 = 0\) because \(12\) divided by \(4\) gives a quotient of \(3\) and a remainder of \(0\).

In general:

\[ a \equiv b \mod m \]

means that \(a\) and \(b\) have the same remainder when divided by \(m\).

Functions#

def modular_arithmetic(number, modulus):
    result = number % modulus
    print(f"{number} ≡ {result} (mod {modulus})")
    return

Examples#

Finding the Remainder of \(17\) mod \(5\)#

number = 17
modulus = 5
modular_arithmetic(number, modulus)

17 ≡ 2 (mod 5)

Explanation

To find the remainder when \(17\) is divided by \(5\), follow these steps:

Divide \(17\) by \(5\): Compute the quotient and remainder.

\[ 17 \div 5 = 3 \text{ remainder } 2 \]

Express the division:

\[ 17 = 5 \times 3 + 2 \]

The remainder is the result of the modulo operation:

\[ 17 \mod 5 = 2 \]

Therefore:

\[ 17 \equiv 2 \mod 5 \]

Finding the Remainder of \(170\) mod \(16\)#

number = 170
modulus = 16
modular_arithmetic(number, modulus)

170 ≡ 10 (mod 16)

Explanation

To find the remainder when \(170\) is divided by \(16\), follow these steps:

Divide \(170\) by \(16\): Compute the quotient and remainder.

\[ 170 \div 16 = 10 \text{ remainder } 10 \]

Express the division:

\[ 170 = 16 \times 10 + 10 \]

The remainder is the result of the modulo operation:

\[ 170 \mod 16 = 10 \]

Therefore:

\[ 170 \equiv 10 \mod 16 \]

Finding the Remainder of \(338\) mod \(12\)#

number = 338
modulus = 12
modular_arithmetic(number, modulus)

338 ≡ 2 (mod 12)

Explanation

To find the remainder when 338 is divided by \(12\), follow these steps:

Divide \(338\) by \(12\): Compute the quotient and remainder.

\[ 338 \div 12 = 28 \text{ remainder } 2 \]

Express the division:

\[ 338 = 12 \times 28 + 2 \]

The remainder is the result of the modulo operation:

\[ 338 \mod 12 = 2 \]

Therefore:

\[ 338 \equiv 2 \mod 12 \]

Finding the Remainder of \(90\) mod \(30\)#

number = 90
modulus = 30
modular_arithmetic(number, modulus)

90 ≡ 0 (mod 30)

Explanation

To find the remainder when \(90\) is divided by \(30\), follow these steps:

Divide \(90\) by \(30\): Compute the quotient and remainder.

\[ 90 \div 30 = 3 \text{ remainder } 0 \]

Express the division:

\[ 90 = 30 \times 3 + 0 \]

The remainder is the result of the modulo operation:

\[ 90 \mod 30 = 0 \]

Therefore:

\[ 90 \equiv 0 \mod 30 \]

Modular Addition#

Modular addition involves adding two numbers and then taking the remainder when the result is divided by the modulus.

The formula for modular addition of two numbers \(a\) and \(b\) with modulus \(m\) is:

\[ (a + b) \mod m \]

Steps:

Add the numbers \(a\) and \(b\).
Take the result and apply the modulus \(m\) to find the remainder.

Functions#

def modular_addition(a, b, modulus):
    result = (a + b) % modulus
    print(f"{a} + {b} ≡ {result} (mod {modulus})")
    return result

Examples#

Finding \((10 + 17)~mod~7\)#

a = 10
b = 17
modulus = 7

result = modular_addition(a, b, modulus)

10 + 17 ≡ 6 (mod 7)

Explanation

To find the result of ( 10 + 17 ) modulo ( 7 ), follow these steps:

Perform the addition:

\[ 10 + 17 = 27 \]

Compute the remainder when divided by the modulus:

\[ 27 \div 7 = 3 \text{ remainder } 6 \]

Express the division:

\[ 27 = 7 \times 3 + 6 \]

The remainder is the result of the modulo operation:

\[ 27 \mod 7 = 6 \]

Therefore:

\[ 10 + 17 \equiv 6 \mod 7 \]

Finding \((203 + 17)~mod~10\)#

a = 203
b = 17
modulus = 10

result = modular_addition(a, b, modulus)

203 + 17 ≡ 0 (mod 10)

Explanation

To find the result of ( 203 + 17 ) modulo ( 10 ), follow these steps:

Perform the addition:

\[ 203 + 17 = 220 \]

Compute the remainder when divided by the modulus:

\[ 220 \div 10 = 22 \text{ remainder } 0 \]

Express the division:

\[ 220 = 10 \times 22 + 0 \]

The remainder is the result of the modulo operation:

\[ 220 \mod 10 = 0 \]

Therefore:

\[ 203 + 17 \equiv 0 \mod 10 \]

Finding \((-43 + 128)~mod~26\)#

a = -43
b = 128
modulus = 26

result = modular_addition(a, b, modulus)

-43 + 128 ≡ 7 (mod 26)

Explanation

To find the result of ( -43 + 128 ) modulo ( 26 ), follow these steps:

Perform the addition:

\[ -43 + 128 = 85 \]

Compute the remainder when divided by the modulus:

\[ 85 \div 26 = 3 \text{ remainder } 7 \]

Express the division:

\[ 85 = 26 \times 3 + 7 \]

The remainder is the result of the modulo operation:

\[ 85 \mod 26 = 7 \]

Therefore:

\[ -43 + 128 \equiv 7 \mod 26 \]

Finding \((3028 + 220934)~mod~85\)#

a = 3028
b = 220934
modulus = 85

result = modular_addition(a, b, modulus)

3028 + 220934 ≡ 72 (mod 85)

Explanation

To find the result of ( 3028 + 220934 ) modulo ( 85 ), follow these steps:

Perform the addition:

\[ 3028 + 220934 = 223962 \]

Compute the remainder when divided by the modulus:

\[ 223962 \div 85 = 2634 \text{ remainder } 12 \]

Express the division:

\[ 223962 = 85 \times 2634 + 12 \]

The remainder is the result of the modulo operation:

\[ 223962 \mod 85 = 12 \]

Therefore:

\[ 3028 + 220934 \equiv 12 \mod 85 \]

Modular Subtraction#

Modular subtraction involves subtracting one number from another and then taking the remainder when the result is divided by the modulus.

The formula for modular subtraction of two numbers \(a\) and \(b\) with modulus \(m\) is:

\[ (a - b) \mod m \]

Steps:

Subtract the number \(b\) from \(a\).
If the result is negative, add the modulus \(m\) until the result is non-negative.
Apply the modulus \(m\) to find the remainder.

Functions#

def modular_subtraction(a, b, modulus):
    result = (a - b) % modulus
    print(f"{a} - {b} ≡ {result} (mod {modulus})")
    return result

Examples#

Finding \((10 - 17)~mod~7\)#

a = 10
b = 17
modulus = 7

result = modular_subtraction(a, b, modulus)

10 - 17 ≡ 0 (mod 7)

Explanation

To find the result of ( 10 - 17 ) modulo ( 7 ), follow these steps:

Perform the subtraction:

\[ 10 - 17 = -7 \]

Adjust to ensure the result is within the range 0 to modulus-1:

Since we have a negative result, we adjust it by adding the modulus until it becomes non-negative:

\[ -7 + 7 = 0 \]

The adjusted result is the result of the modulo operation:

\[ 10 - 17 \equiv 0 \mod 7 \]

Finding \((217 - 240)~mod~19\)#

a = 217
b = 240
modulus = 19

result = modular_subtraction(a, b, modulus)

217 - 240 ≡ 15 (mod 19)

Explanation

To find the result of ( 217 - 240 ) modulo ( 19 ), follow these steps:

Perform the subtraction:

\[ 217 - 240 = -23 \]

Adjust to ensure the result is within the range 0 to modulus-1:

Since we have a negative result, we adjust it by adding the modulus until it becomes non-negative:

\[ -23 + 19 = -4 \]

Find the remainder when divided by the modulus:

Now, calculate the remainder when ( -4 ) is divided by ( 19 ):

\[ -4 \mod 19 = 15 \]

Therefore:

\[ 217 - 240 \equiv 15 \mod 19 \]

Finding \((2293 - 334)~mod~38\)#

a = 2293
b = 334
modulus = 38

result = modular_subtraction(a, b, modulus)

2293 - 334 ≡ 21 (mod 38)

Explanation

To find the result of ( 2293 - 334 ) modulo ( 38 ), follow these steps:

Perform the subtraction:

\[ 2293 - 334 = 1959 \]

Find the remainder when divided by the modulus:

Now, calculate the remainder when ( 1959 ) is divided by ( 38 ):

\[ 1959 \div 38 = 51 \text{ remainder } 21 \]

Express the division:

\[ 1959 = 38 \times 51 + 21 \]

The remainder is the result of the modulo operation:

\[ 1959 \mod 38 = 21 \]

Therefore:

\[ 2293 - 334 \equiv 21 \mod 38 \]

Modular Multiplication#

Modular multiplication involves multiplying two numbers and then taking the remainder when the result is divided by the modulus.

The formula for modular multiplication of two numbers \(a\) and \(b\) with modulus \(m\) is:

\[ (a \times b) \mod m \]

Steps:

Multiply the numbers \(a\) and \(b\).
Apply the modulus \(m\) to find the remainder.

Functions#

def modular_multiplication(a, b, modulus):
    result = (a * b) % modulus
    print(f"{a} * {b} ≡ {result} (mod {modulus})")
    return result

Examples#

Find \((23 \times 7)~mod~26\)#

a = 23
b = 7
modulus = 26

result = modular_multiplication(a, b, modulus)

23 * 7 ≡ 5 (mod 26)

Explanation

To find the result of ( 23 \times 7 ) modulo ( 26 ), follow these steps:

Perform the multiplication:

\[ 23 \times 7 = 161 \]

Find the remainder when divided by the modulus:

Now, calculate the remainder when ( 161 ) is divided by ( 26 ):

\[ 161 \div 26 = 6 \text{ remainder } 5 \]

Express the division:

\[ 161 = 26 \times 6 + 5 \]

The remainder is the result of the modulo operation:

\[ 161 \mod 26 = 5 \]

Therefore:

\[ 23 \times 7 \equiv 5 \mod 26 \]

Finding \((182 \times 39)~mod~8\)#

a = 182
b = 39
modulus = 8

result = modular_multiplication(a, b, modulus)

182 * 39 ≡ 2 (mod 8)

Explanation

To find the result of ( 182 \times 39 ) modulo ( 8 ), follow these steps:

Perform the multiplication:

\[ 182 \times 39 = 7104 \]

Find the remainder when divided by the modulus:

Now, calculate the remainder when ( 7104 ) is divided by ( 8 ):

\[ 7104 \div 8 = 888 \text{ remainder } 0 \]

Express the division:

\[ 7104 = 8 \times 888 + 0 \]

The remainder is the result of the modulo operation:

\[ 7104 \mod 8 = 0 \]

Therefore:

\[ 182 \times 39 \equiv 0 \mod 8 \]

Finding \((123 \times 291)~mod~39\)#

a = 123
b = 291
modulus = 39

result = modular_multiplication(a, b, modulus)

123 * 291 ≡ 30 (mod 39)

Explanation

To find the result of ( 123 \times 291 ) modulo ( 39 ), follow these steps:

Perform the multiplication:

\[ 123 \times 291 = 35853 \]

Find the remainder when divided by the modulus:

Now, calculate the remainder when ( 35853 ) is divided by ( 39 ):

\[ 35853 \div 39 = 919 \text{ remainder } 32 \]

Express the division:

\[ 35853 = 39 \times 919 + 32 \]

The remainder is the result of the modulo operation:

\[ 35853 \mod 39 = 32 \]

Therefore:

\[ 123 \times 291 \equiv 32 \mod 39 \]

Modular Inverse#

The modular inverse of a number \(a\) modulo \(m\) is a number \(x\) such that:

\[ a \times x \equiv 1 \mod m \]

The modular inverse exists if and only if \(a\) and \(m\) are coprime (i.e., \(\text{gcd}(a, m) = 1\)).

To find the modular inverse of \(a\) modulo \(m\), you can use the Extended Euclidean Algorithm.

Extended Euclidean Algorithm#

The Euclidean Algorithm is a method to find the greatest common divisor (gcd) of two integers. The Extended Euclidean Algorithm extends this to find the coefficients \(x\) and \(y\) such that:

\[ a \times x + b \times y = \text{gcd}(a, b) \]

These coefficients \(x\) and \(y\) can be used to express the gcd as a linear combination of \(a\) and \(b\).

Functions#

def modular_inverse(a, modulus):
    def extended_gcd(a, b):
        if a == 0:
            return b, 0, 1
        gcd, x1, y1 = extended_gcd(b % a, a)
        x = y1 - (b // a) * x1
        y = x1
        return gcd, x, y
    
    gcd, x, _ = extended_gcd(a, modulus)
    if gcd != 1:
        raise ValueError(f"Inverse does not exist for {a} modulo {modulus}")
    else:
        result = x % modulus
        print(f"Inverse of {a} ≡ {result} (mod {modulus})")
        return result

Examples#

Finding the modular inverse of \(23~mod~26\)#

a = 23
modulus = 26

result = modular_inverse(a, modulus)

Inverse of 23 ≡ 17 (mod 26)

Modular Inverse Calculation

To find the modular inverse of 23 mod 26, follow these steps using the Extended Euclidean Algorithm:

Initialisation: Set initial values:
- \(\text{gcd} = 1\)
- \(x = 0\)
- \(y = 1\)
Step-by-Step Calculation:

Step 0:
- \(\text{gcd} = 1\)
- \(x = 0\)
- \(y = 1\)
Step 1:
- Update values based on the Euclidean algorithm:
- \(\text{gcd} = 1\)
- \(x = 1\)
- \(y = 0\)
Step 2:
- Continue updating:
- \(\text{gcd} = 1\)
- \(x = -1\)
- \(y = 1\)
Step 3:
- Further updates:
- \(\text{gcd} = 1\)
- \(x = 8\)
- \(y = -1\)
Step 4:
- Final updates:
- \(\text{gcd} = 1\)
- \(x = -9\)
- \(y = 8\)
Result:
- Since the \(\text{gcd}\) remains 1 throughout, 23 has an inverse modulo 26.
- The final value of \(x\) after adjustments for modular arithmetic (as \(-9 \equiv 17 \ (\text{mod}\ 26)\)) gives the modular inverse.
- Thus, the inverse of 23 modulo 26 is 17.

Extending the Function#

As modular inverse is a step up from the simple addition or subtraction operations in modular arithmetic; we can actually extend the function further to output the steps for using the Extended Euclidean Algorithm to find the modular inverse. This can be useful for understanding the steps, you can also use this to check your work for practicing the algorithm.

def modular_inverse_steps(a, modulus):
    def extended_gcd(a, b):
        steps = []
        if a == 0:
            steps.append((b, 0, 1))
            return b, 0, 1, steps
        gcd, x1, y1, prev_steps = extended_gcd(b % a, a)
        x = y1 - (b // a) * x1
        y = x1
        steps = prev_steps + [(gcd, x, y)]
        return gcd, x, y, steps

    gcd, x, y, steps = extended_gcd(a, modulus)
    if gcd != 1:
        raise ValueError(f"Inverse does not exist for {a} modulo {modulus}")
    else:
        result = x % modulus
        print(f"Steps to find the modular inverse of {a} mod {modulus}:")
        for i, (gcd, x, y) in enumerate(steps):
            print(f"Step {i}: gcd = {gcd}, x = {x}, y = {y}")
        print(f"Inverse of {a} ≡ {result} (mod {modulus})")
        return

a = 11
modulus = 30

result = modular_inverse_steps(a, modulus)

Steps to find the modular inverse of 11 mod 30:
Step 0: gcd = 1, x = 0, y = 1
Step 1: gcd = 1, x = 1, y = 0
Step 2: gcd = 1, x = -1, y = 1
Step 3: gcd = 1, x = 3, y = -1
Step 4: gcd = 1, x = -4, y = 3
Step 5: gcd = 1, x = 11, y = -4
Inverse of 11 ≡ 11 (mod 30)

Finding the modular inverse of \(23~mod~49\)#

a = 23
modulus = 49

result = modular_inverse_steps(a, modulus)

Steps to find the modular inverse of 23 mod 49:
Step 0: gcd = 1, x = 0, y = 1
Step 1: gcd = 1, x = 1, y = 0
Step 2: gcd = 1, x = -1, y = 1
Step 3: gcd = 1, x = 8, y = -1
Step 4: gcd = 1, x = -17, y = 8
Inverse of 23 ≡ 32 (mod 49)

Finding the modular inverse of \(20~mod~40\)#

In the following example you’ll see what occurs when the modular inverse doesn’t exist.

a = 20
modulus = 40

result = modular_inverse_steps(a, modulus)

---------------------------------------------------------------------------
ValueError                                Traceback (most recent call last)
Cell In[24], line 4
      1 a = 20
      2 modulus = 40
----> 4 result = modular_inverse_steps(a, modulus)

Cell In[21], line 15, in modular_inverse_steps(a, modulus)
     13 gcd, x, y, steps = extended_gcd(a, modulus)
     14 if gcd != 1:
---> 15     raise ValueError(f"Inverse does not exist for {a} modulo {modulus}")
     16 else:
     17     result = x % modulus

ValueError: Inverse does not exist for 20 modulo 40

Modular Exponentiation#

Modular exponentiation involves raising a number to an exponent and then taking the remainder when the result is divided by the modulus. This operation is commonly used in fields such as cryptography.

The formula for modular exponentiation of a number \(a\) raised to an exponent \(b\) with modulus \(m\) is:

\[a^b~\mod~m\]

Steps to Perform Modular Exponentiation#

Compute the Power \(a^b\): Calculate the power of the base \(a\) raised to the exponent \(b\).
Apply the Modulus \(m\): After computing \(a^b\), take the remainder when the result is divided by the modulus \(m\).

However, computing \(a^b\) directly for large \(b\) can be computationally expensive and may result in very large intermediate results. Instead, we use an efficient method called Exponentiation by Squaring to perform modular exponentiation.

Exponentiation by Squaring#

Exponentiation by Squaring is an efficient algorithm to compute \(a^b \mod m\). It works by breaking down the exponentiation process into a series of squaring and multiplication steps, reducing the overall number of operations.

Steps of Exponentiation by Squaring:#

Initialisation: Set the result to 1 and the base to \(a\).
Iterate through the bits of the exponent \(b\):
- If the current bit is 1, multiply the result by the current base.
- Square the base for the next iteration.
Apply the modulus \(m\) at each step: Take the remainder of both the result and the base with \(m\) to keep the numbers manageable.

Functions#

This time we will make two functions from the get go, one to initially show how to get the result, and one that can give you the steps for the Exponentiation by Squaring method.

def modular_exponentiation(base, exponent, modulus):
    result = pow(base, exponent, modulus)
    print(f"{base}^{exponent} ≡ {result} (mod {modulus})")
    return result

def modular_exponentiation_steps(base, exponent, modulus):
    result = 1
    base = base % modulus
    steps = []

    while exponent > 0:
        if (exponent % 2) == 1:
            result = (result * base) % modulus
            steps.append(f"Result updated to {result} after multiplying by base {base}")
        
        base = (base * base) % modulus
        steps.append(f"Base squared and reduced modulo {modulus}: {base}")

        exponent = exponent // 2
        steps.append(f"Exponent shifted right: {exponent}")

    print(f"Steps of computation:")
    for step in steps:
        print(step)

    print(f"{base}^{exponent} ≡ {result} (mod {modulus})")
    return result

Examples#

Finding the modular exponentiation of \(11^{13}~mod~18\)#

a = 11
exponent = 13
modulus = 18

result = modular_exponentiation(a, exponent, modulus)

11^13 ≡ 11 (mod 18)

result = modular_exponentiation_steps(a, exponent, modulus)

Steps of computation:
Result updated to 11 after multiplying by base 11
Base squared and reduced modulo 18: 13
Exponent shifted right: 6
Base squared and reduced modulo 18: 7
Exponent shifted right: 3
Result updated to 5 after multiplying by base 7
Base squared and reduced modulo 18: 13
Exponent shifted right: 1
Result updated to 11 after multiplying by base 13
Base squared and reduced modulo 18: 7
Exponent shifted right: 0
7^0 ≡ 11 (mod 18)

Finding the modular exponentiation of \(283^{4}~mod~12\)#

a = 283
exponent = 4
modulus = 12

result = modular_exponentiation(a, exponent, modulus)

283^4 ≡ 1 (mod 12)

result = modular_exponentiation_steps(a, exponent, modulus)

Steps of computation:
Base squared and reduced modulo 12: 1
Exponent shifted right: 2
Base squared and reduced modulo 12: 1
Exponent shifted right: 1
Result updated to 1 after multiplying by base 1
Base squared and reduced modulo 12: 1
Exponent shifted right: 0
1^0 ≡ 1 (mod 12)

Finding the modular exponentiation of \(38273^{7}~mod~24\)#

a = 38273
exponent = 7
modulus = 24

result = modular_exponentiation(a, exponent, modulus)

38273^7 ≡ 17 (mod 24)

result = modular_exponentiation_steps(a, exponent, modulus)

Steps of computation:
Result updated to 17 after multiplying by base 17
Base squared and reduced modulo 24: 1
Exponent shifted right: 3
Result updated to 17 after multiplying by base 1
Base squared and reduced modulo 24: 1
Exponent shifted right: 1
Result updated to 17 after multiplying by base 1
Base squared and reduced modulo 24: 1
Exponent shifted right: 0
1^0 ≡ 17 (mod 24)

Modular Arithmetic Complete

Contents

Modular Arithmetic Complete#

Functions#

Examples#

Finding the Remainder of \(17\) mod \(5\)#

Finding the Remainder of \(170\) mod \(16\)#

Finding the Remainder of \(338\) mod \(12\)#

Finding the Remainder of \(90\) mod \(30\)#

Modular Addition#

Functions#

Examples#

Finding \((10 + 17)~mod~7\)#

Finding \((203 + 17)~mod~10\)#

Finding \((-43 + 128)~mod~26\)#

Finding \((3028 + 220934)~mod~85\)#

Modular Subtraction#

Functions#

Examples#

Finding \((10 - 17)~mod~7\)#

Finding \((217 - 240)~mod~19\)#

Finding \((2293 - 334)~mod~38\)#

Modular Multiplication#

Functions#

Examples#

Find \((23 \times 7)~mod~26\)#

Finding \((182 \times 39)~mod~8\)#

Finding \((123 \times 291)~mod~39\)#

Modular Inverse#

Extended Euclidean Algorithm#

Functions#

Examples#

Finding the modular inverse of \(23~mod~26\)#

Extending the Function#

Finding the modular inverse of \(23~mod~49\)#

Finding the modular inverse of \(20~mod~40\)#

Modular Exponentiation#

Steps to Perform Modular Exponentiation#

Exponentiation by Squaring#

Steps of Exponentiation by Squaring:#

Functions#

Examples#

Finding the modular exponentiation of \(11^{13}~mod~18\)#

Finding the modular exponentiation of \(283^{4}~mod~12\)#

Finding the modular exponentiation of \(38273^{7}~mod~24\)#