Modular Multiplication

Let's explore modular multiplication: i.e.,

(A * B) mod N

By changing the values of A, B, and N below, we can find various outputs. For example, if A = 7, B =4, and N =8, the result is 4. Similarly, you can calculate other values.

NOTE: We can notice here that the output ranges from 0 to N.

Next, let's observe all the outputs by multiplying an integer by all the values from 0 to N. Below, by changing the value of b, we can see all the outcomes in a cyclic way.

CASE 1: When N is Prime.

Here, we will notice that every number multiplied with a particular number has a unique output. Thus, we see every arrow leaving from that number once and an arrow entering the number once. For example, when n=17, b =10, we can see an arrow goes from 1 to 10, signifying when we multiply 10 by 1, we get the output 10. Similarly, we see an arrow originates from 12 and enters 1, meaning when 12 is multiplied by 10 in (mod 17) world, we get 1 as the result.

CASE 2: When N is Composite.

Case 2.a: gcd(N,b)=1

Here, we will notice that when gcd(N,b)=1, then every number multiplied by b has a unique output. Thus, we see every arrow leaving from that number once and an arrow entering the number once. For example, when n=18, b =11, thus gcd(18,11)=1, we can see an arrow goes from 1 to 11, denoting when we multiply 11 by 1, we get the result 11. Similarly, we see an arrow originates from 5 and enters to 1, indicating when 11 is multiplied by 5 in (mod 18) world, we get 1 as the result.

Case 2.b: gcd(N,b)!=1

Here, we will notice that when gcd(N,b)!=1, some numbers, when multiplied by b, have the identical result. Thus, we see some arrows directed toward a single output.

For example, when n=18, b =12, thus gcd(18,12)=6, we can see many arrows enter 0, 6, and 12, which signifies that there is only a few possible outputs.

NOTE: Let's look at the multiplication table for mod n. This table will help us understand two key concepts: Closure property and additive inverse property in a group. (Note: there are two other properties, namely associative and the existence of identity element, but we are not going to discuss them.)

Closure Property: Here, when "n is prime," each row and each column of the table have values from 1 to (n-1). On the other hand, when "n is composite," only some rows and each columns have values from 1 to (n-1), i.e., the row "i" for which gcd(i, n)=1.

Multiplicative inverse: As we know, in the multiplicative world, when we multiply two numbers resulting in 1 as the output, both the numbers are said to be the multiplicative inverse of each other. Mathematically,

When "n is prime":

In the table, if we consider n=7, every row is a permutation of numbers from 1 to 6.

Here, when we consider a row and find 1 in the cell, the corresponding column value represents the multiplicative inverse.

For example, when n = 7, if we consider the row corresponding to 3, we will find 1 in the sixth cell from the right, whose corresponding column value is 5. Thus 5 is the multiplicative inverse of 3 in (mod 10) world.

When "n is composite":

We can see only a few rows has a permutation of numbers from 1 to n-1

For example, if we consider n=6, the row corresponding to 5 has a permutation of numbers from 1 to 5. Other rows have only some of the values from 1 to 5. We realize those rows correspond to the value i such that gcd(i, n) is not equal to 1.

In these scenarios, we can only find multiplicative inverse in the rows where we see a permutation of numbers from 1 to 5. In our example, this row corresponds to the value 5. Here, the multiplicative inverse of 5 is also 5, which is the corresponding column value of the cell with value 1.

Conclusion: We can find the multiplicative inverse integer i in mod n only if gcd(i,n)=1.

NEXT: After learning about modular multiplication and condition to find multiplicative inverse, let's learn about modular exponentiation, primarily focusing on the primitive roots or generators and Fermat's Theorem.