Open access peer-reviewed chapter - ONLINE FIRST

Application of Discrete Mathematics for Programming Discrete Mathematics Calculations

Written By

Carlos Rodriguez Lucatero

Reviewed: February 1st, 2022 Published: March 30th, 2022

DOI: 10.5772/intechopen.102990

Qualitative and Computational Aspects of Dynamical Systems Edited by Kamal Shah

From the Edited Volume

Qualitative and Computational Aspects of Dynamical Systems [Working Title]

Dr. Kamal Shah, Dr. . Eiman and Dr. Arshad Ali

Chapter metrics overview

9 Chapter Downloads

View Full Metrics


In the discrete mathematics courses, topics, such as the calculation of the element in any position of a sequence of numbers generated by some recurrence relation, calculation of multiplicative inverses in algebraic ring structures modulo a number n, obtaining the complete list of combinations without repetition, for which you can take advantage of the computing power of computers and perform such calculations using computer programs in some programming language. The implementations of these calculations can be carried out in many ways and therefore their algorithmic performance can be very varied. In this chapter, I propose to illustrate by means of some Matlab programs, how the use of results of the same discrete mathematics allows to improve the algorithmic performance of said computer programs. Another topic addressed in regular discrete mathematics courses where calculations arise that could become very expensive both in time and in occupied space, if the calculations are implemented directly from the definitions is modular arithmetic. Such calculations can be carried out much more efficiently by making use of results from discrete mathematics and number theory. The application of these ideas will be developed in the following sections of this chapter.


  • recurrence relations
  • algorithms
  • generating functions
  • modular arithmetic
  • Matlab

1. Introduction

Discrete mathematics provides very useful calculation tools to enumerate mathematical objects of a certain type, such as the number of graphs that meet a certain particular property or how many regions will be formed within a circle as the number of points that grows, we will join by means of secant lines [1]. The methods and tools of discrete mathematics are of enormous relevance in the field of computer science when one wants to compare different algorithmic solutions to a problem. The goodness of an algorithmic solution must take into account, the use of runtime resources and memory space since they are limited. For this, it is necessary to carry out an analysis of the algorithm and count how many execution steps, such processing takes and how many memory locations it will occupy. When carrying out this analysis, mathematical expressions known as recurrence relationships are obtained, which reflect the behavior at execution time or the memory space occupied by the algorithm. Once the recurrence relationship is obtained, it can be evaluated to estimate, for example, how many executions steps an algorithm will take as the number of input data increases. This generates a succession of values that can eventually be graphed to give us an idea of the temporal complexity of such an algorithm. Such evaluation can be done by hand or it can be implemented, in some programming language available, a function. Normally the direct translation of the mentioned recurrences to a program produces compact and clear recursive routines. The evaluation of such routines is inefficient since many of the recursive calls repeat calculations and it is in this case that it is worth looking for more efficient iterative versions of these calculations. Even more, if possible, we can solve the recurrences to obtain a closed mathematical expression that describes the behavior of the growth in the time of the algorithm. That is where the tools of discrete mathematics acquire special relevance. In algorithm analysis books, one can find many techniques to solve certain types of recurrences and we can illustrate by giving some examples in this chapter. Either way, there are more general discrete mathematics tools for this purpose that we will also try to illustrate with examples. This process of solving recurrences can be seen as a generalization of the solution of classical problems. Some problems consist of finding the next element in a sequence of numbers and for which there are techniques, such as the method of divided differences. Sometimes obtaining the closed solution of a recurrence is not possible, however, discrete mathematics and mathematical analysis allow to define upper and lower bounds as well as approximate calculations of very good quality.

Another topic addressed in discrete mathematics courses, which requires the performance of many calculations, is that of modular arithmetic. Such calculations can be carried out much more efficiently by making use of results from discrete mathematics and number theory. The application of these ideas will be developed in the following sections of this chapter.


2. Body of the manuscript

The chapter will have the following structure. In Section 3, we will make a quick revision of some calculations problems in combinatorics. After that, in Section 4, we will talk about where the recurrence relations arise and some methods as well as mathematical tools that are frequently used to solve them. In each example, we will begin by obtaining the mathematical relationship that describes the behavior of the problem to be solved. Once the mathematical relationship is obtained, we will use it to give us an idea of the behavior it describes by evaluating it by means of some function programmed in Matlab. Later, we will obtain the associated mathematical expression or a good approximation function that we will evaluate implementing a Matlab function. This will allow us to compare the performance in the time of the evaluation of an expression and the direct application of a recurrence by implementing both in Matlab.

In Section 5, we will describe characteristics or properties of ring algebraic structures on the set of positive integers modulo some number nand directly from the definitions, we will obtain the tables of the two operations of the ring in question. Later, we will obtain the same tables more efficiently from the application of properties and theoretical results of modular arithmetic to illustrate the advantage of making use of the results of modular arithmetic to make calculations of modular arithmetic algorithmically more efficient both in time and space.


3. Combinatorics calculation

One of the most relevant topics in discrete mathematics is combinatorial analysis, where, among other things, it is important to calculate the number of all possible linear arrangements of a given size of objects of a set with repetitions or without repetitions. In some cases, the order of appearance of these objects must be taken into account. When the order of the elements is important and it is allowed to have a repetition of them, we are talking about permutations with repetition. If the repetition of elements is forbidden, then we are talking about permutations without repetition. To clarify ideas, suppose that we have a set A=abcdand that we want to calculate all possible linear arrangements of 3-position elements allowing repetitions of elements in each of the positions. The cardinality of the set of objects Ais 4 and as each of the three positions can be occupied by any of the elements of Athen the total number of possible dispositions will be 4×4×4that is to say 43=64. The resulting list of possibilities appear in Table 1.


Table 1.

Complete listing of permutation with repetitions.

This table was generated by the following Matlab function.

function y = enumeraPCR(A)

% Autor: Carlos Rodriguez Lucatero



for i=1:n

  for j=1:n

    for k=1:n

     fprintf('%s,%s,%s \n’,A(1,i),A(1,j),A(1,k));







If the repetitions of elements of A=abcdare not allowed the linear dispositions of three positions of those elements have four possibilities for the first position, three possibilities for the second position, and two possibilities for the third position, giving as a total number of linear dispositions 4×3×2=24. The listing of those dispositions can be seen in Table 2.


Table 2.

Complete listing of the permutations without repetitions.

This last table was generated by the following Matlab function.

function [y,lista] = ListaPSR(A,k)

% Autor: Carlos Rodriguez Lucatero





while r-1 > 0


  while((A(1,j) >= A(1,j+1)) & (j>0))




  while ((A(1,j) >= A(1,l)) & (l>j))








  while (t<l)













In general, if the cardinality of the set of objects is nand the number of possible positions within the linear arrangement is kthen the total of possible permutations with repetition would be equal to nk. In the event that repetitions of elements are not allowed in the arrangement, the first position can be occupied by any of the nelements of the set of objects. Once the element is assigned to position 1, the next position can be filled by any of the remaining n1elements and so on until filling the kpositions of the linear arrangement. In the general case, the calculation of the total of possible dispositions under the aforementioned conditions would be n×n1××nk+1. As you can see, this calculation can result in an excessive number of factors and for that reason the n!symbol is introduced, which is equal to n×n1×n2×3×2×1. Thus, the calculation of the total number of permutations without repetition of nobjects taken from kin kis calculated with the following formula


The factorial can be defined as a recurrence relation. Every recurrence relationship has a stop condition and a recursive step. To do this, it is necessary to define both parts of the recurrence. For this, we agree that 0!=1which constitutes the stop condition and since n!=n×n1×n2××3×2×1=n×n1!. So, we can rewrite n!as recurrence as follows


The recurrence 2 to calculate the factorial is one of the first recurrence relationships to appear in discrete mathematics. If we try to implement in Matlab a direct translation of the recurrence 2 this could be the following.

function y=fact(n)

if n<0

  disp('argument should be positive');


elseif n==0






Such an implementation is compact and elegant but has the disadvantage that it can easily overwhelm the system’s recursive call stack, which is why it is worth looking for an equivalent iterative implementation. Fortunately, it is known that recursive routines whose last instruction is a recursive call can always be translated into an iterative version. Therefore, we propose the following iterative implementation.

function y= factI( n )


for i=1:n





Sometimes when calculations have to be made, it may be enough to use good approximations. The calculation of n!can be done in an approximate and efficient way using the Stirling approximation formula whose proof can be consulted in ref. [2] and whose mathematical expression is the following


This approximation turns out to be quite good and this allows us to calculate n!very efficiently with a computer, avoiding the problem of excessive recursive calls in the case that nis very large. A possible implementation of this approach using Matlab would be the following.

function y = factStirling(n)

% Stirling approximation of the factorial

% Feller Vol. I pag 70

$ Autor: Carlos Rodriguez Lucatero



We can compare the algorithmic complexities of these three different functions to calculate n!and we can notice that both the recursive and iterative versions have a time complexity of Onwhile the Stirling approximation version is of O1which is more efficient but at the price of the calculation being approximate. This example of the different ways of calculating n!is the first example of how we can benefit from mathematical results to improve the temporal performance of the programs that we implement for this purpose.


4. Recurrences calculation and analysis of algorithms

With regard to algorithm efficiency, it is in this topic that some recurrence relationships and methods of solving said recurrences can be found to determine the time behavior of the algorithms in terms of the number of input data. One of the design techniques that allows you to build efficient algorithms is known as Divide and Conquer. A well-known problem in computing is that of ordering in ascending order a set of numerical data in disorder. In regular algorithm analysis courses, various algorithmic solutions for the said problem are studied and some of the most efficient algorithmic solutions are designed using the Divide and Conquerapproach. One of the most famous Divides and Conquer algorithms is the Merge-Sort. The operation of the Merge-Sort starts by dividing the arrangement into subarrays in half and each subarray divides it again, in the same way, proceeding recursively until it reaches a point where it is not possible to further subdivide subarrays, after which it begins to sort by interleaving the subarrays until merging the ordered subarrays of the first partition. A possible Matlab implementation of this algorithm is shown below.

function y = mergesort(A,p,r)

if (p < r)









function y = merge(A,y1,y2,p,q,r)









for k=p:r

  if L(i) <= R(j)










When analyzing the Merge-Sort, a recurrence of the time or number of steps in total that it takes depending on the size of the input is obtained, which we will denote as Tn. The recurrence obtained as a product of the analysis of this algorithm can have the following form


To solve the recurrence relation, four several methods, such as substitution, recurrence tree, or iteration of recurrence can be applied [3]. Here we will use the iteration method of recurrence. To simplify the problem, we will assume that the size of the array is n=2m, that is, it is a power of 2. Taking into account the above, we can operate a variable change in recurrence 4 which is rewritten as follows


We iterate over the recurrence 5 we obtain the following expression


We know that n=2mand therefore that m=log2n. Then we can make the change of variable in expression 5 and obtain the solution to recurrence 4 that would have the following form


Recurrence relationships are present in undergraduate courses in algorithmic analysis, mathematical thinking, or discrete mathematics. One of the topics that are usually addressed in the courses of mathematical thought is that of sequences of numbers and the detection of patterns of behavior of these sequences to illustrate the mathematical process of discovering the properties of sequences of numbers. Typical examples consist of presenting a sequence of integer values and inferring what is the next number in the sequence. In classic mathematical thinking, textbooks such as [4] systematic methods are exposed to solve this type of mathematical puzzles, such as the method of successive differences. Normally these types of exercises remain at the point of discovering the next element in the sequence, but you can go further in the problem and try to discover the mathematical expression that allows obtaining the term of a sequence of numbers in an arbitrary position. It is there where we can resort to the recurrence relations from which a recursive program can be implemented to obtain elements of the numerical sequence in any given position or even more use the tools of discrete mathematics to solve said recurrences to obtain in computationally efficient way elements in arbitrary positions in a sequence of numbers. Next, we will show these ideas with an example with numerical sequences in which we will obtain the following element of the sequence by the method of successive differences, then we will obtain some recurrence relation from which we will implement a function in Matlab that allows us to obtain any element of the sequence given the position and finally, we will solve the recurrence in question to obtain a mathematical formula that represents the form of the n-th term of the sequence from which a function will be implemented to Matlab to evaluate said mathematical expression giving the position to obtain the number that occupies that position within the given sequence of numbers.

4.1 Numerical sequences and recurrences

There are sequences of numbers known as figurative numbers since they are related to figures of a certain type that are formed by joining a certain number of points with lines. These points and lines can form, for example, triangles, squares, pentagons, or heptagons, and the associated sequences will be called triangular numbers, square numbers, pentagonal numbers, or heptagonal numbers, respectively. In Figure 1, we can see how pentagons can be formed from the number of points given in each case.

Figure 1.

Pentagonal numbers sequence.

The sequence associated with the pentagonal numbers is shown in Table 3.


Table 3.

Pentagonal numeric sequence.

Suppose you want to obtain the next element of the numerical sequence, that is, the element a5. For this, we can apply the method of successive differences that consists of taking the first difference between successive elements of the sequence, then the differences of the first successive differences are taken, and so on.

When the successive differences become constant, the process stops and we perform a backward calculation adding the last differences of each level until we reach the calculation of the last element of the original sequence.

The steps performed by this procedure appear in Table 4.


Table 4.

Successive differences on the pentagonal sequence.

The numbers that appear in boldface are generated by the backward calculation mentioned before. This procedure, although correct, can become very cumbersome if instead of wanting to calculate the next element in the sequence, you want to know the value of the element in the sequence in position 30. It is in this case that it would be worthwhile to obtain a mathematical relationship that would allow us to implement a program in any programming language that is available to obtain any element of the numerical sequence in any given position. One way to achieve this goal is to try to discover the recurrence relationship that allows the elements of the sequence to be generated until the element of the sequence in the desired position is reached. This is what we will do next. From the calculations carried out in the successive differences procedure, we can obtain the following first difference relationships between elements of the sequence


From the first differences, we can obtain the following relationships corresponding to the second differences


We can observe the relations related to the second difference; a regular behavior that allows us to establish the following generalization


From Eq. (17), we can obtain the following difference equation


As can be seen, it is a difference equation, it is non-homogeneous linear second order and with constant coefficients, and for this reason, it requires two initial conditions that are taken from the numerical sequence in question. These initial conditions are a0=1and a1=5. Thus, the equation in complete differences would be expressed in the following form


From Eq. (19), we can obtain the following recurrence>1.E20

Recurrence allows us to directly implement the following recursive function in Matlab.

function y = recpentagR(n)

%Author: Carlos Rodriguez Lucatero

if (n==0)



  if (n==1)







We can test the routine from Matlab by first calculating an element of the sequence whose value we know, for example a5=51. The result of calling the function from the Matlab prompt is the following.

>> z=recpentagR(5)

z =


Now let us try to calculate with this same routine the element of the numerical sequence at position 30, that is, a30. The result is shown below.

>> z=recpentagR(30)

z =


If we wanted to calculate a50with this recursive routine we would realize that the calculation time increases a lot because many of the calculations are recalculated and also there is a risk of overflowing the system stack due to a large amount of recursive calls. Fortunately, we can reprogram an iterative version of this function and it is the one shown below.

function y = recpentagI(n)

%Author: CRL



if (n==0)



  if (n==1)




    for i=2:n









We will test this routine by first executing it for the known value a5=51, then for the value a30whose value obtained with the recursive version was 1426 and finally, we will obtain the value a50as well as the a100value.

>> z=recpentagI(5)

z =


>> z=recpentagI(30)

z =


>> z=recpentagI(50)

z =


>> z=recpentagI(100)

z =


The runtime improvement of the iterative version over the recursive version is truly impressive. However, the execution time of a routine can be further improved to carry out this calculation by resorting to discrete mathematics tools to solve the recurrence and implement a routine that the only thing that does is evaluate in the given position the mathematical formula obtained from the solution of the recurrence. Discrete mathematics provides us with many methods to solve non-homogeneous linear difference equations, such as the one we will solve, associated with recurrence relationships. This type of difference equations can be obtained by methods, such as the iteration of recurrence, the characteristic polynomial method, or the generating function method. In this subsection, we will resolve the recurrence by applying several of these methods for illustrative purposes. For more details on solving recurrences using these methods, we recommend consulting [3, 5, 6, 7, 8].

4.2 Solving a recurrence by iteration

We start with the application of the iteration method of recurrence. For this purpose, we will use the third row of the recurrence relation (20). This equation would be the following


We apply Eq. (21) to the case of n1which would give the following equation


We substitute 22 in 21 and obtain the following equation


We apply Eq. (21) to the case of n2which would give the following equation


We substitute 24 in 23 and obtain the following equation


We apply Eq. (21) to the case of n3which would give the following equation


We substitute 26 in 25 and obtain the following equation


Continuing with this procedure until reaching the base cases and noting that certain regularities appear, such as the presence of a sum of successive natural numbers, we arrive at the following expression


Substituting a0=1,a1=5and applying Gauss’s formula to the summation in Eq. (28), we obtain the following solution


4.3 Solving a recurrence by the characteristic polynomial method

We can try another method of solving the recurrence to illustrate another tool provided by discrete mathematics. In this case, we will use the characteristic polynomial method. The difference equation that we are going to solve is linear inhomogeneous with coefficients, which makes it capable of being solved by this method. These methods are closely related to the methods of solving differential equations of the same type. The difference equation that we are going to solve is the following


The theory on the solution of equations in non-homogeneous linear differences says that the general solution is composed of a solution of the homogeneous equation plus a particular solution related to the non-homogeneous part. The homogeneous equation associated with Eq. (30) would be the following


A characteristic polynomial is associated with the homogeneous Eq. (31) that is obtained by substituting a possible solution in the difference equation. Said possible solution has the form an=crnwhere cis an arbitrary constant if we substitute said possible solution in 31 we obtain the following polynomial


The roots of the characteristic polynomial 32 are r1=1and r2=1, that is, they are real and repeated roots and since the solutions of a difference equation must be linearly independent, the form of the solution of the homogeneous difference equation would be the following


Now we proceed to solve the particular equation whose solution must be linearly independent of the solutions of the associated homogeneous equation. We note that the right-hand side of the difference Eq. (30) is fn=3which is equivalent to fn=31n. So the form of the particular solution would be the following


If we evaluate the equation in differences 30 the solution 34 we obtain the following expression


After algebraically simplifying Eq. 35 we deduce that A=32, so the general solution would have the form


Applying on 37 a0=1we deduce that c1=1. Applying on 37 a1=5we get c2=52In this way we obtain that the general solution is


We can verify that solution 37 coincides with solution 29. Finally, we can use this solution to implement a Matlab function to perform this calculation and obtain the value of an element of the sequence given the position. The Matlab function would be the following.

function y = recpentag(n)

% Author: Carlos Rodriguez Lucatero



For being convinced about the correctness of the solution, we can evaluate this Matlab function for the same values used before and we obtain the following results.

>> y = recpentag(5)

y =


>> y = recpentag(10)

y =


>> y = recpentag(30)

y =


>> y = recpentag(50)

y =


>> y = recpentag(100)

y =


4.4 Solving a recurrence by generating function method

Another powerful method of discrete mathematics to solve difference Eq. (19) associated with the recurrence 20 is that of ordinary generating functions. Said method consists, in the simplest case, in converting a numerical sequence into an infinite polynomial of a single variable whose coefficients are precisely the elements of the numerical sequence. The reason for doing this transformation is that the algebraic manipulation of these infinite polynomials is relatively simple. For this reason, we define below the concept of the ordinary generating function of a single variable.

Definition1.1 Given a numerical sequence a0,a1,a2,,ak,the function


It is called the ordinary generating function (OGF) of the sequence. The notation zkAzwill be used to refer to the coefficient akof the k-th term of the infinite polynomial.

By means of the generating functions, we can map sequences of numbers that often are integers to power series. The coefficient of the n-th adding will, therefore, be related to the n-th element of the associated numerical sequence. For example, in the generating function i=0zi=1+z+z2+z3+z4+, we observe that it is the geometric series that converges if z<1and can be expressed as 11z. We can also observe that all the terms of the sum have a coefficient of 1, so this generating function is associated with the numerical sequence 1,1,1,1,. On the other hand, since the generating functions are infinite polynomials, it is easy to apply the derivative operation to them. Thus, the derivative of the geometric series would be expressible as follows


As can be seen from 39, the derivative of the geometric series can be related to de succession of natural numbers.

It is also possible to do certain types of algebraic operations on ordinary generating functions that have an impact on the sequence of numerical values associated with the given generating function. For example, if I multiply the generating function of 11z2by z, we obtain the following effect in the numerical sequence


that is to say that we obtain a shift to the right in the sequence of numbers.

If we apply the derivative to Eq. (40), we obtain the following relationship


then we have


We have exemplified the following relationships between numerical sequences and generating functions


After all those examples, we can be convinced that it is possible to establish relationships between sequences of numbers and generating functions, as shown in Table 5.

0,1,1+12,1+12+13,,Hn,11zln11z=n1Hnzn(where Hnis the harmonic series)

Table 5.

Table of sequences and ordinary generating functions.

For more detailed information on recurrences that appear in the analysis of algorithms as well as generating functions, we recommend the excellent book [5].

After this brief summary on ordinary generating functions, we can solve the difference Eq. (19) using generating functions and that is just what we will do next. The difference equation to solve is


We know from definition 38 that a generating function is expressed mathematically as


and we apply this operator to the difference Eq. (48) keeping the same summation index for the terms of the difference Eq. (48) obtaining the following expression


Because of the index shift, the first summation is Aza0a1z. In the second term of the left hand of Eq. (50) the index of the coefficient and the power of zbeing different; so, we can factorize zand take into account the shift in the summation index and obtain the term 2z(Aza0. The difference between the summation index and the power of zin the third term of the left hand of 50 can be arranged by factoring z2and in that case, we obtain the term z2Az. The right hand of Eq. (50) is a geometric series but given the shift on the index of the summation, it is necessary to subtract the two first terms of the geometric series giving, as a result, the term 311z1z. Then taking into account these remarks, we obtain the next equation


Simplifying Eq. (51) we get the next equation


The left hand of 53 can be algebraically simplified obtaining the following expression


Simplifying de left hand of Eq. (53) we get the equation


We apply the znoperator to Eq. (54) with the purpose of obtaining the coefficient of the nth addend of the sum that will correspond to the element in the position nof the sequence of numbers studied, arriving at the equation


and then to the final result


As you can see the expressions (29), (37), and (56) are the same.


5. Modular arithmetical calculations

In discrete mathematics courses at the undergraduate level, topics of modern algebra are addressed where the most elementary algebraic structures are defined, such as the group structure and the ring structure. The algebraic structure to which we are going to devote our attention in this section is the ring structure in the context of modular arithmetic.

This algebraic structure is often used, informally, in arithmetic courses to learn to add and multiply. Formally speaking we can say that this structure is composed of a set of objects that could be in the case of arithmetic the set of integers as well as two operations which are addition and multiplication which is denoted as Z+. The two operations must be closed, that is to say, that the results they give must belong to the same set from which the operands are taken. Additionally, the operations must respect certain properties that we will define below.

Definition1.2 (Ring) Let be Rnonempty set that has two closed binary operations denoted as +y . Then R+it is a ring if a,b,cRthe following conditions are met:

a) a+b=b+a(commutative law of +).

b) a+b+c=a+b+c(Associative law of +).

c) zRsuch that a+z=z+a=a,aR(existence of identity element for +).

d) For each aR,bRsuch that a+b=b+a=z(existence of inverse under +).

e) abc=abc(Associative law for ).

f) ab+c=ab+acy b+ca=ba+ca(Distributive laws for over +).

In order to simplify the notation, the operation abcan be written as ab. The associative properties of both operations as well as the distributivity of one operation over the other can be generalized for the case of more than 2operands.

The +operation of the ring is commutative but the operation is not commutative in the 1.2 definitions. We can apply the commutativity property to the operation and we would obtain the commutative ring structure. Formally the definition of a commutative ring is as follows.

Definition1.3 (Commutative ring) Let be Ra nonempty set having two closed binary operations denoted as +and . Then R+is a ring if a,b,cRmeet the following conditions:

a) If ab=ba,a,bRthen Ris a commutative ring.

b) It is said that the ring Rhas no proper divisors of zero if for any a,bR,ab=za=zb=z.

c) If an element uRsuch that uzand ua=au=a,aRwe say that uis a unit or identity element of multiplication and that Ris a ring with unity.

Another interesting property that can be added to the list of ring properties is the existence of multiplicative inverse. The definition is the following.

Definition1.4 (Ring with multiplicative inverse) Let Rbe a ring with the unit uif a,bRand ab=ba=uthen bis called inverse multiplicative of aand ais called a unit of R. (An element bis also a unit of R).

Taking into account the existence of the unit property, we can add it to the ring commutative ring and obtain a commutative ring with unity.

Definition1.5 (Commutative ring with unity) Let be Ra commutative ring with unity. Then:

a) Ris said to have an integer domain if Rhas no proper divisors of zero.

b) Ris said to be a field if each non-zero element of Ris a unit.

Rings can have subsets that satisfy the properties of a ring as defined in 1.2 in which case we are talking about subring structures. These algebraic structures can have additive cancelation properties as well as multiplicative cancelation properties and therefore will have symmetric or inverse elements of addition as well as multiplication. Once we have understood the theoretical part of the rings we are better positioned to tackle the construction and use of finite rings specials and fields. We will start by presenting some results of the modular arithmetic needed for the de notion of operations in modular rings. These notions will be explained below.

5.1 Integers modn

In this section, we will review some notions of modular arithmetic that usually appear in introductory courses of the Theory of Numbers and that allow us to understand important concepts, such as divisibility, primality, the greatest common divisor operation as well as the algorithm of Euclid to calculate it efficiently. Let us start with establishing the meaning of some mathematical symbols that appear in this context. The expression datranslates into words like d divides a to what is the same as kZsuch that a=kdand dis called divisor of a. This means that if we divide aby d, the remainder will be 0. From here we can make the following properties and definitions.

Definition1.6 Every integer divides 0. That is xZ,x0.

Proposition1.7 If a>0and dathen da.

Proposition1.8 daif and only if da.

Definition1.9 A number xis said to be composite if it has divisors other than 1and x.

Example1.10 The number 39is composite since 339is true and 31is true as like 339.

Example1.11 The divisors of 24are 1,2,3,4,6,8,12,24. The 1and 24are known as trivial divisors.

Definition1.12 The set of divisors of a number athat are neither 1nor aare called factors of a.

Definition1.13 A number prime is here the one that has no factors.

Example1.14 The numbers 1,3,5,7,11,13are prime.

Definition1.15 A number that is not prime is said to be a composite number.

Theorem1.16 (Division Theorem) For any a,nZthere exist q,rZúnique such that a=qn+rwhere 0r<n.

q=anis called the quotient and r=amodnis called the remainder. Then naif amodnis equal to 0. From this, in conjunction with theorem 16, it can be stated that a=ann+amodnor equivalently that aann=amodn.

Definition1.17 If amodn=bmodnthen we say that abmodnif they have the same remainder aand bwhen divided by nis to say that abmodnnba.

When it is true that amodn=bmodnwe will denote it as abmodnand the equivalence classes that this relation generates will be expressed as an=a+knkZ. In general, we can say the congruence relation modulo some number npartitions to the set of integers in equivalence classes by the remainder left when divided by a number nwhich we express as Zn=an:0an1.

5.2 Common divisors and greatest common divisor

Let us start by defining the concept of a common divisor.

Definition1.18 dis a common divisor of the numbers aand bif daand dbhold.

Common divisors have the following properties.

Proposition1.19 da+band dab.

Proposition[1.20] If daand dbthen dax+byx,yZ. That is, ddivides every linear combination of aand b.

Proposition1.21 If abthen abor b=0.

Proposition1.22 If aband bahold then a=+bor a=b.

Definition1.23 The greatest common divisor of aand bdenoted as gcdab. (greatest common divisor) is: gcdab=maxd:daydb.

Example1.24 gcd2430=6,gcd57=1,gcd09=0.

Proposition1.25 If aand bare not both equal to 0, then gcdabis an integer between 1and minab.

Definition1.26 gcd00=0.

Definition1.27 aand bare relatively prime if gcdab=1.

Proposition1.28 gcdab=gcdba.

Proposition1.29 gcdab=gcdab.

Proposition1.30 gcdab=gcdab.

Proposition1.31 gcda0=a.

Proposition1.32 gcdaka=a,kZ.

Theorem1.33 If aand bare any integers and are not both equal to 0then gcdabis the smallest positive element of the set ax+by:xyZof linear combinations of aand b.

Proof:Let sbe the smallest positive element of the set of such linear combinations of aand b, then s=ax+byfor some x,yZ. Let q=as. The equation amodn=aanimplies amods=aqs=aqax+by=a1qx+bqy, so smodsis a linear combination of aand b. Since amods<sthen amods=0since sis the smallest value that is a linear combination of aand b. The above means that sa. Reasoning in a similar way we can prove that sb. Then sis a common divisor of aand b, and it also holds that gcdabsand like daand dbimplies that dax+by, so as a consequence of all this gcdabssince gcdabdivides any linear combination of awith band sis a linear combination of awith b. But gcdabsand s>0imply that gcdab<s. Combining that is satisfied simultaneously that gcdab>sand that gcdab<swe can conclude that gcdab=s.

Corollary1 For any a,bZ, if daand dbthen dgcdab.

Proof:If daand dbthen x,yZdax+byand since gcdabis a linear combination of aand bwe can conclude. .

Corollary2 a,b,nZand n0gcdanbn=ngcdab.

Corollary3 a,b,nZand a,b,n0if naband gcdan=1then nb.

Theorem1.34 a,bZ+,gcdab=gcdbamodb.


• (demo sketch).

• We first prove that gcdabgcdbamodb.

• Let d=gcdabthen daand db.

• We know that amodb=aqbwhere q=ab.

• Since amodbis a linear combination of aand b.

• from the above and the fact that daand dbthis implies that dax+bythen dband damodbwhere gcdabgcdbamodb.

• As a second part, it is proved in a similar way that gcdbamodbgcdab.

• If both gcdabgcdbamodband gcdbamodbgcdabhold we can conclude that a,bZ+,gcdab=gcdbamodb.

Theorem 1.34 provides us with the mathematical elements to be able to define a recursive algorithm for the calculation of the Greatest Common Divisor is the following.


1) if b=0

2) then return a

3) else Euclid(b, a mod b)

The following is an example of how Euclid’s algorithm works.

Example[1.35] We will calculate thegcd3021applying the Euclidean algorithm that I have just explained. The execution steps are displayed inTable 6.

= 3

Table 6.

Execution steps of the Euclid’s algorithm.

5.3 Modular rings

Definition1.36 Let nZ+,n>1. For a,bZ, tenths that ais congruent to bmodulo nand is written as abmodn, if nab, or equivalently a=b+knfor some kinZ.

Example1.37 For example:

a) 172mod5.

b) 749mod6.

Theorem1.38 The congruence modulo nis an equivalence relation Z.

Proof:(Do it as an exercise).

Since an equivalence relation on a set produces a partition of that set, then for n2the congruence relation modulo nproduces a partition of set Zin the following nequivalence classes:


By the division algorithm, we know that tZ,t=qn+rwhere 0r<n, so tror also means that t=r. We use Zto denote 012n1or when there is no ambiguity we also use ‘in Zn=0,1,2n1.

We can define closed operations addition and pipeline on the set of equivalence classes of Znas a+b=a+band acdotb=ab=ab.

Example[1.39] If n=7then 2+6=8=1and 26=12=5.

Before accepting the definitions of the modular operations a+b=a+band ab=abwe must convince ourselves that they are well defined, that is, if a=cand b=dthen a+b=c+dand ab=cd. We will prove that these operations are independent of the choice of elements within a class. So, then a=ca=c+snfor some sZand b=db=d+tnfor some tZ. Then a+b=c+sn+d+tn=c+d+s+tnso that a+bc+dmodnthat is a+b=c+d.

In the same way ab=c+snd+tn=cd+sd+ct+stnnso that abcdmodn, that is ab=cd. This leads us to establish the following theorem.

Theorem1.40 For nZ+,n>1under the closed binary operations just defined Znis a commutative ring with the unit 1.

Proof:The proof is left as an exercise for the student. What would have to be done for this is to verify that the ring properties hold for the definition of the addition and multiplication operations on Znand the properties of the ring Z+.

Before continuing with more theoretical results, let us see the tables of the operations of +and for Z5and Z6. The Z5operation tables are displayed in Table 7 and operation tables corresponding to Z6ring are shown in Table 8.


Table 7.

Operations tables of the ring Z5+.


Table 8.

Operations tables of the ring Z6+.

We can see in the tables of the +and operations of Z5all elements other than 0have an inverse element, which is why this is a field. In the case of the tables of Z6, as opposed to those of Z5, only 1and 5are elements with inverse (bf units) and 2,3,4are proper divisors of 0. If we obtained the corresponding tables for Z9, we could see that 33=36=0, that is there are also proper divisors of 0which means that it is not enough for nto be an odd number for the set Znto be a field. The latter leads us to establish the following theorem.

Theorem1.41 Znwould be a field if and only if nis a prime number.

Proof:Let nbe a prime, and suppose 0<a<n. Then the gcdan=1and since the gcdanis a linear combination of aand nthat is to say that s,tZn,as+tn=1. Therefore as1modni.e. as=1, which implies that ais an element with inverse (unit) which makes Zna field. Conversely, if nis not a prime then it can be represented as a product of two numbers, that is n=n1n2where 1<n1,n2<nand if n10so as n10but n1n2=0means that Znis not an integer domain since it has proper divisors of 0and therefore cannot be a field.

In Z6the 5has an inverse (it is a unit) and on the other hand, 3is a proper divisor of 0. It is useful and necessary to be able to detect which elements have an inverse (ie they are units) when nis composite. For this, the following theorem is established.

Theorem1.42 In Zn, ahas an inverse (it is a unit) if and only if gcdan=1.

Proof:If gcdan=1the proof will be the same as the theorem??. In the reverse direction, let aZnand a1=s. So as=1, so then as1modnand as=1+tnfor some tZbut 1=as+ntgcdan=1.

In the following example, we illustrate the application of Euclid’s algorithms to obtain multiplicative inverses of elements of a modular field-type group.

Example1.43 Find 251in Z72. Since gcd2572=1Euclid’s gcdalgorithm we get the following:


since 1is the last non-zero remainder, we have



1=8722325123+7225mod72, so then 1=4925then 49=251in Z72.

For a more detailed exposition of the previous results in modular arithmetic, greatest common divisor and Euclid’s algorithm, it is recommended to consult these bibliographical references [3, 6, 9, 10].

After this brief overview of the properties of the algebraic ring structure as well as how to work with it in the context of modular arithmetic, we are ready to discuss the advantage of applying results from discrete mathematics to perform calculations of modular arithmetic efficiently. As already explained in the previous paragraphs of this subsection, we can, from the tables of the modular ring in which we are working, obtain all the multiplicative inverses of the ring as well as all the proper divisors of zero in the event that the ring does not be a field. We can do this by generating the sum and product tables of the ring and going through the multiplication table detecting a box where the value is equal to 1in the case of multiplicative inverses, or that the box is equal to 0in the case of proper divisors of zero. This procedure for obtaining the proper divisors of zero could be carried out with the following Matlab program.

function Fz = FacPropZero(n)

% Modulo n [S, P] = TabOpMod (n)

% Search on the table P all those factors whose product is equal to 0

% CRL 29/sep/2021

[S,P] = TabOpMod(n);

[r,c] = size(P);


for i=1:r

  for j=1:r

   if (P(i,j)==0)







The procedure for obtaining the ring elements that have multiplicative inverse could be carried out with the following Matlab program.

function U = unitsZn(n)

% Modulo n [S,P] = TabOpMod(n)

% Search on the table P all those factors whose product is equal to 1

% CRL 22/sep/2021

[S,P] = TabOpMod(n);

[r,c] = size(P);


for i=1:r

  for j=1:r

    if (P(i,j)==1)







The results of the execution of the Matlab function for obtaining the list of elements of the modular ring that have multiplicative inverse for the case of n=5and n=6are the following:

>> U=unitsZn(5)

U =

1×4 cell array

  {1×2 double} {1×2 double} {1×2 double} {1×2 double}

>> U{1,1}

ans =

   1  1

>> U{1,2}

ans =

  2  3

>> U{1,3}

ans =

  3  2

>> U{1,4}

ans =

  4  4

>> U=unitsZn(6)

U =

  1×2 cell array

    {1×2 double} {1×2 double}

>> U=unitsZn(6)

U =

  1×2 cell array

    {1×2 double} {1×2 double}

>> U{1,1}

ans =

  1  1

>> U{1,2}

ans =

  5  5

The above Matlab routines look good and bad from an algorithmic perspective. The good side is that since it is a direct translation of the operations table generation of a modular ring, the programming of the routines is relatively simple. The negative aspect is in the fact that the size of the arrays to generate the tables can become very large as the number nwith respect to which the module is taken grows a lot, that is, the memory occupied will be of the order of On2. It is at this point that the properties and results of discrete mathematics in the subject of modular arithmetic come to the rescue and allow us to obtain more efficient algorithms for obtaining proper divisors of zero as well as the list of elements of the modular ring that have an inverse multiplicative. The efficient algorithm for obtaining the list of elements of a modular ring with multiplicative inverse and the respective Matlab implementation will make use of discrete mathematics results, such as Euclid’s algorithm for obtaining the greatest common divisor, as well as the version extension of this, and that will be called by a routine that solves linear modular equations of the type ax=bmodn. The multiplicative inverse xof a number amodulo nwill correspond to the solution of the modular linear equation ax=1modn. Based on theorem 34, we can implement the Euclid’s algorithm in Matlab as follows.

function y = mcdEuclides(a,b)

% Recursive function for the GCD using Euclid’s algorithm

% The first parameter musy be bigger than the second parameter

if a < b





if b == 0



  y=mcdEuclides(b, mod(a,b));



Euclid’s algorithm can be extended to obtain the coefficients aand bof xand yin the relation d=gcdab=ax+by. This will be used for obtaining multiplicative inverses of a modular ring. The Matlab implementation of the extended Euclid algorithm is as follows.

Function [d,x,y] = mcdEuclidesExtend(a,b)

% Extended GCD Euclid’s algorithm

if a < b





if b == 0





[d1,x1,y1]=mcdEuclidesExtend(b, mod(a,b));






As already mentioned, obtaining the elements of a modular ring that have a multiplicative inverse can be reduced to the problem of calculating the elements xthat satisfy the solution to the modular equation ax=1modn. The Matlab implementation of the linear modular equation solver will be the following.

Function S = ModLinEqSolv(a,b,n)

% Modular linear equation solver

% That have the form ax=b mod n

% Author: Carlos Rodriguez Lucatero 29/sep/2021

[d,x,y] = mcdEuclidesExtend(a,n);

if (mod(b,d)==0)


  for i=0:d-1







If we call this routine with the parameter b=1, it would give us the result of the value of x, which is the inverse of ain the relation ax=bmodn, if it exists, or it would return 1to indicate that the element aof the modular ring does not have a multiplicative inverse. The following routine calls the linear modular equation solver routine to get the list of elements of the modular ring that have an inverse.

Function L = unitsZnV3(n)

% Get the list of units of a modular ring

% mod n calling the routine that solves linear modular equations

% Autor: Carlos Rodriguez Lucatero 14/Ene/2022


for i=1:n

  S = ModLinEqSolv(i,1,n);

  if (S ∼=-1)





if (length(L)==0)




The elements of the list in 0correspond to the inverse of the element that does not have an inverse and therefore we would be talking about dividing elements proper to zero of the modular ring in question. The elements in the list that are not null are the inverse of the element of the modular ring represented by the position in the list. For instance, in Z5+, we have that 23=1and 44=1.

>> L = unitsZnV3(5)

L =

  1  3  2  4

>> L = unitsZnV3(6)

L =

  1 0 0 0 5


6. Conclusions

In this chapter, we address some calculation problems that take place in discrete mathematics and how we can use the theoretical results provided by discrete mathematics itself to be able to carry out these calculations more efficiently. In this chapter, we were able to verify the great utility of the use of generating functions to carry out some calculations more efficiently. Some interesting applications of the use of generating functions to count graphs with some property can be found in refs. [11, 12]. These counting techniques can later be applied to the famous probabilistic method [13, 14, 15]. Generating functions are also very useful for counting the number of possible partitions of integers. An excellent text that addresses this interesting topic is [16].

It is true that computers have not stopped increasing their storage capacity as well as the speed of their processing units. However, these resources are not infinite and there are even calculation-intensive problems in topics, such as combinatorics or modular arithmetic that could quickly exhaust these calculation resources. That is why it is worth taking advantage, when possible, of the theoretical results that discrete mathematics itself provides, to efficiently carry out the calculations that it requires. For this, we take two specific topics of discrete mathematics where that is possible. One is the obtainment of elements in arbitrary positions of a numerical sequence and the other topic was the obtainment of elements with multiplicative inverse of the elements that are proper divisors of zero in a modular ring. We illustrate this by programming functions in Matlab. I hope that the chapter will convince you of the goodness of taking advantage of the mathematical results offered by discrete mathematics to perform efficient calculations in the area of discrete mathematics.



I would like to thank the Universidad Autonoma Metropolitana, Unidad Cuajimalpa for the support they gave me to make and publish this book chapter.


  1. 1. Rodríguez-Lucatero C. The Moser’s formula for the division of the circle by chords problem revisited. 2017. Available from:
  2. 2. Feller W. An Introduction to Probability Theory and its Applications. Vol. I. New York, USA: Wiley and Sons Inc; 1968. pp. 52-53
  3. 3. Cormen TH, Leiserson CE, Rivest RL, Stein C. Introduction to Algorithms. 3d ed. Massachusetts, USA: The MIT Press; 2009
  4. 4. Miller CD, Heeren VE, Hornsby J. Matematica, razonamiento y aplicaciones. USA: Pearson; 2013
  5. 5. Sedgewick R, Flajolet P. An Introduction to the Analysis of Algorithms, Second Printing. USA: Addison-Wesley; 2001
  6. 6. Grimaldi RP. Discrete and Combinatorial Mathematics: An Applied Introduction. 3rd ed. USA: Addison-Wesley; 1994
  7. 7. Graham RL, Knuth DE, Patashnik O. Concretel Mathematics, 6th Printing. USA: Addison-Wesley; 1990
  8. 8. Wilf HS. Generatingfunctionology. 3th ed. Massachusetts, USA: A. K. Peters Ltd.; 2006
  9. 9. Hardy GH, Wright EM. Introduction to the Theory of Numbers. 5th ed. Oxford, UK: Oxford Science Publications, reprinted; 1998
  10. 10. Vinográdov I. Fundamentos de la Teora de números. URSS: Moscu: Editorial MIR; 1977
  11. 11. Harary F, Palmer EM. Graphical Enumeration. New York, NY, USA; London, UK: Academic Press; 1973
  12. 12. Rodríguez-Lucatero C. Combinatorial Enumeration of Graphs. Rijeka: IntechOpen; 2019
  13. 13. Erdös P. Graph theory and probability. Canadian Journal of Mathematics. 1959;11:34-38
  14. 14. Alon N, Spencer JH. The Probabilistic Method. 2nd ed. New York Wiley-Interscience; 2000
  15. 15. Rodríguez-Lucatero C, Alarcón L. Use of enumerative combinatorics for proving the applicability of an asymptotic stability result on discrete-time SIS epidemics in complex networks. MDPI Mathematics Open access Journal. 2019;7(1). DOI: 10.3390/math7010030
  16. 16. Andrews GE. In: Rota GC, editor. The Theory of Partitions Encyclopedia of Mathematics and its Applications. Vol. 2. USA: Addison-Wesley; 1976

Written By

Carlos Rodriguez Lucatero

Reviewed: February 1st, 2022 Published: March 30th, 2022