Experimental Math — Computing Units of Modular Rings

Image by Gerd Altmann from Pixabay

A ring is an algebraic structure modelled after the integers and their arithmetic properties. Formally, a ring is defined as a structure consisting of a nonempty set, S, and two operations; addition(+) and multiplication(*) satisfying the following properties for all x, y, z in S:

1. x + y is also a member of S (closure under addition)
2. x + y = y + x (additive commutativity)
3. x + (y + z)= (x + y) + z (associativity with respect to addition)
4. There is an element 0, such that x + 0 = 0 + x = x for all x in S (identity element with respect to addition)
5. There is an element -x, such that x + (-x) = 0 (additive inverse)
6. x * y is also a member of S (closure under multiplication)
7. x * (y * z)= (x * y) * z (associativity)
8. There is an element 1, such that x * 1 = 1 * x = x for all x in S
   (multiplicative identity)
9. x * (y + z)=(x * y)+(x * z) (left distributivity)
10. (y + z) * x =(y * x)+(z * x) (right distributivity)
11. x * y = y * x (multiplicative commutativity — optional)

What a long list of properties? Well, we can put it in a nutshell; a ring is an algebraic structure (S,+,*) such that (S,+) is an abelian group (properties 1 to 5) and (S, *) is a monoid (properties 6, 7, 8) and the * operation is distributive over the + operation (properties 9 and 10).

Since rings are modelled after the integers, obviously, the archetypal example of a ring is the set of integers and the usual arithmetic operations of addition and multiplication. The set of integers is usually represented by the letter Z, from Zahlen, the German word for numbers.
Z = {… -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7, …}.
(Z, +, *) is a ring. As an exercise, you can confirm that.

Another example of a ring, with a simple structure, is the set of integers modulo n denoted by Z/nZ or Zₙ. This is just the set of possible remainders when n divides another integer. For example Z/6Z = {0, 1, 2, 3, 4, 5}.
Generally, Z/nZ ={0, 1, 2, . . . , n−1}. The ring operations are carried out mod n. Let’s call rings of this sort modular rings. You can verify that the set of ring properties are satisfied.

There are many other examples of rings but we want to focus on modular rings in this article.

Units in Rings

Consider the following multiplications;
2 * (1/2) = 1
3 * (1/3) = 1
4 * (1/4) = 1 etc.
We see that multiplying a number by its reciprocal gives 1(the multiplicative identity), which is, of course, expected from the definition of reciprocals, but the thing is, reciprocals(or more technically, multiplicative inverses) do not always exist for all numbers. In the ring of integers (Z, +, *), what is the reciprocal or multiplicative inverse of 3? (1/3)? No. (1/3) is not an element of Z so it is not accepted. It turns out the only numbers with multiplicative inverses in (Z, +, *) are -1 and 1, and they happen to be their own inverses;
-1 * -1 = 1
1 * 1 = 1

The elements of a ring that have multiplicative inverses are called units. The set of units of a ring have interesting structure and some important applications, for example, computing the units of certain rings is equivalent to finding the solutions of certain Diophantine equations.

Computing Units of Z/nZ

Now, let’s go about computing the units of modular rings, Z/nZ. We start with a specific ring, say Z/9Z. It appears the only method available to us now for finding these units is actually carrying out all possible multiplications in Z/9Z and checking which multiplicands produce 1.
Z/9Z ={0, 1, 2, 3, 4, 5, 6, 7, 8}.
The multiplication table for Z/9Z is shown below. Remember multiplication is carried out mod 9.

From the table, we can see that the units of the ring Z/9Z are the numbers
1, 2, 4, 5, 7, 8. For an instance, from the table, 2 * 5 = 1, so 2 and 5 are units.
There are 64(8 squared) non-zero result cells in the table, meaning we carried out 64 multiplications. Generally, to compute the units of Z/nZ this way takes (n-1)² modular multiplications.

What if need to compute the units of Z/nZ when n is large? Manually constructing a multiplication table is not practicable. This is where computer code comes in. We are going to write a program in Julia to help compute the units for arbitrary n. The program logic follows the procedure above; carry out all possible multiplications in Z/nZ and note(store in an array, U) those multiplicands that produce 1. So, we are going to need two loops — nested; an outer loop for the top row and an inner loop for the leading column(or vice versa). We are going to start from 1, excluding 0, since multiplication by 0 will always give 0.

Here’s a test run of the code on the Julia REPL :

The code displays the units array, U, as a vertical list and indicates the number of elements in the array. To format the array more nicely, we can use the show() function, but we will need to add a counter this time to keep track of the number of elements in the array:

So, we now have a program for computing units in Z/nZ. The efficiency of the program can be increased by using the fact that multiplication is commutative in the ring. There are some redundant multiplications we can dispense with;
2 * 3 is the same thing as 3 * 2, we just take one and don’t bother computing the other. The figure below shows how the redundancies arise and helps in determining the savings in computational steps and probably how we can go about excluding the redundancies from our code.

At Block 1, the first cycle of the loop, there are no redundancies. At Block 2,
2 * 1 is redundant because 1 * 2 has been computed in the previous block.
At Block 3, there are 2 redundancies resulting from operations in the two previous blocks. A block gets one redundancy from each of the preceding blocks; at Block n, there will be n-1 redundancies.

Generally, for Z/nZ, there will be n-1 blocks or loop cycles, the (n-1)th block which is the last block will have (n-1)-1 = n-2 redundancies. So the total number of redundancies will be:
T = 1 + 2 + 3 + … + n-2
This is an arithmetic progression having n-2 terms with first term 1, common difference 1 and last term n-2. Using the formula for the sum of an arithmetic progression, we have:
T = ((n-2)/2)(1+n-2) = ((n-2)/2)(n-1)

That represents the savings in computational steps when we modify our program. The modified program will now take (n-1)²-T modular multiplications.

How do we modify our code to dispense with the redundant operations? I’d like to leave that as an exercise.

Is there still room for improvement in our modified units computing algorithm? Even with the removal of redundant operations, it still feels like a brute force algorithm, more like an improved “trial multiplication”. May be some more theory can help.

By the definition of units, u is a unit of Z/nZ if there is an element i of Z/nZ , such that ui ≡ 1(mod n). The congruence implies there is an integer k such that ui-1=kn or ui-kn =1. Let d be the greatest common divisor(gcd) of u and n, that means d divides u and n, and therefore divides ui-kn. And since ui-kn = 1, the divisor d must be equal to 1. If the gcd of two numbers is 1, the numbers are relatively prime, they have no common factor or divisor apart from 1. We’ve just proved that u and n are relatively prime, and that’s a defining property of units in Z/nZ; the units of Z/nZ are relatively prime to n. But is every element that is relatively prime to n a unit? We need to prove that as well.

Let v be an arbitrary element of Z/nZ that is relatively prime to n.
That means gcd(v,n) = 1. 
Then, by Bézout’s lemma, there exist integers x and y such that
vx + ny = 1
ny = 1 - vx
Since y is an integer, the last equation implies n divides 1 - vx (with a remainder of 0), in the language of congruences:
1 - vx ≡ 0(mod n)
1 ≡ vx(mod n)
vx ≡ 1(mod n). This implies v is a unit in Z/nZ which is what we wanted to prove.

The foregoing results gives us another approach to compute the units of Z/nZ; finding those elements that are relatively prime to n. As mentioned earlier, two numbers are relatively prime or coprime if their greatest common divisor (gcd) equals 1, so, our new algorithm will make use of a gcd function in a loop through the elements of Z/nZ to check for coprimality.
Julia has a built-in gcd function, but not to look like we are cheating, we are going to write our own gcd function, let’s call it ourowngcd. It is based on the Euclidean algorithm for computing gcd.

The new units computing algorithm named computeunitswithgcd is shown below.

One seeming improvement in this new algorithm is that no multiplication is involved, just the modulo operation, the previous algorithm involves both multiplication and modulo operation. We can further throw in a little, smart optimization that works only for even numbers(even numbers occur about half of the time, right?). If n is even, it cannot be coprime to an even number, so we don’t bother to check for coprimality with even elements of Z/nZ. Instead of looping over 1, 2, 3, 4…,we skip the even numbers and loop over 1, 3, 5, 7….
That’s about 50% reduction in loop cycles. The optimized code is displayed below. Check if n is even at the start, if yes, set the loop step size to 2 instead of the default 1.

Is computeunitswithgcd(n) a more efficient algorithm than computeunits(n)? You can find out experimentally by comparing the execution times of the two algorithms for a couple of reasonably large n’s.

Group of Units

One of the interesting properties of the units of a ring is that they form a group - under multiplication. The set of units of the ring Z/9Z as computed earlier is {1, 2, 4, 5, 7, 8}, you can verify that it satisfies the group properties of closure, associativity, identity, and inverse.

Now, let us prove that the set of units U of a general modular ring Z/nZ or any kind of ring at all, form a group. The operation is multiplication, *.

Closure. We want to show that for any elements a and b of U, their product,
a * b is also in U, in other words we want to show that a * b is also a unit, i.e. it has a multiplicative inverse.

Let A and B be the multiplicative inverses of a and b respectively. Then,
(a*b)*(B*A)= a*(b*B)*A = a*1*A = a*A = 1
(B*A)*(a*b)= B*(A*a)*b = B*1*b = B*b = 1
[The above statements made use of the associative property of rings and the fact that the product of an element and its inverse is 1].
 
From the two statements above, we can see that a*b has a multiplicative inverse, B*A, and is therefore a unit.

Associativity. Associativity is inherited from the ring Z/nZ.

Identity. The identity element 1 is inherited from the ring Z/nZ.

Inverse. By definition every unit has a multiplicative inverse.