Modular Arithmetic | Engineering Mathematics (2024)

Modular arithmetic is the branch of arithmetic mathematics related to the “mod” functionality. Basically, modular arithmetic is related to the computation of a “mod” of expressions. Expressions may have digits and computational symbols of addition, subtraction, multiplication, division or any other.

Modular arithmetic, often referred to as “clock arithmetic,” is a system of arithmetic for integers, where numbers wrap around upon reaching a certain value, known as the modulus. This concept is widely used in various fields, including cryptography, computer science, and engineering.

Here we will discuss briefly all modular arithmetic operations.

What is Modular Arithmetic?

In modular arithmetic, numbers are reduced within a certain range, defined by the modulus. For two integers a and b, and a positive integer n, we say that a is congruent to b modulo n if their difference is an integer multiple of n. This is denoted as:

a ≡ b (mod n)

Quotient Remainder Theorem

It states that, for any pair of integers a and b (b is positive), there exist two unique integers q and r such that:

a = b x q + r where 0 <= r < b

Example: If a = 20, b = 6 then q = 3, r = 2 20 = 6 x 3 + 2

Modular Addition

The rule for modular addition is:

(a + b) mod m = ((a mod m) + (b mod m)) mod m

Example:

(15 + 17) % 7= ((15 % 7) + (17 % 7)) % 7= (1 + 3) % 7= 4 % 7= 4

The same rule is to modular subtraction. We don’t require much modular subtraction but it can also be done in the same way.

Modular Multiplication

The Rule for modular multiplication is:

(a x b) mod m = ((a mod m) x (b mod m)) mod m

Example:

(12 x 13) % 5= ((12 % 5) x (13 % 5)) % 5= (2 x 3) % 5= 6 % 5= 1

Modular Division

The modular division is totally different from modular addition, subtraction and multiplication. It also does not exist always.

(a / b) mod m is not equal to ((a mod m) / (b mod m)) mod m.

This is calculated using the following formula:

(a / b) mod m = (a x (inverse of b if exists)) mod m

Modular Inverse

The modular inverse of a mod m exists only if a and m are relatively prime i.e. gcd(a, m) = 1. Hence, for finding the inverse of a under modulo m, if (a x b) mod m = 1 then b is the modular inverse of a.

Example: a = 5, m = 7 (5 x 3) % 7 = 1 hence, 3 is modulo inverse of 5 under 7.

Modular Exponentiation

Finding a^b mod m is the modular exponentiation. There are two approaches for this – recursive and iterative.

Example:

a = 5, b = 2, m = 7(5 ^ 2) % 7 = 25 % 7 = 4

There is often a need to efficiently calculate the value of xⁿ mod m. This can be done in O(logn) time using the following recursion:

It is important that in the case of an even n, the value of x^n/2 is calculated only once.

This guarantees that the time complexity of the algorithm is O(logn) because n is always halved when it is even.

The following function calculates the value of xⁿ mod m:

#include<bits/stdc++.h>#include<iostream>using namespace std;//function that calculate modular exponentiation x^n mod m.int modpower(int x, int n, int m) { if (n == 0) //base case  return 1%m;  long long u = modpower(x,n/2,m);  u = (u*u)%m; if (n%2 == 1) //when 'n' is odd u = (u*x)%m; return u;}//driver functionint main(){  cout<<modpower(5,2,7)<<endl; return 0;}

#include <stdio.h>//function that calculate modular exponentiation x^n mod m.int modpower(int x, int n, int m) { if (n == 0) //base case  return 1 % m;  long long u = modpower(x, n / 2, m);  u = (u * u) % m; if (n % 2 == 1) // when 'n' is odd u = (u * x) % m; return u;}//driver functionint main(){  printf("%d\n", modpower(5, 2, 7)); return 0;}

import java.util.*;class GFG { //function that calculate modular exponentiation x^n mod m. public static int modpower(int x, int n, int m) { if (n == 0) //base case  return 1 % m;  long u = modpower(x, n / 2, m);  u = (u * u) % m; if (n % 2 == 1) // when 'n' is odd u = (u * x) % m; return (int)u; } //driver function public static void main(String[] args) { System.out.println(modpower(5, 2, 7)); }}

#function that calculate modular exponentiation x^n mod m.def modpower(x, n, m): if n == 0: # base case return 1 % m u = modpower(x, n // 2, m) u = (u * u) % m if n % 2 == 1: # when 'n' is odd u = (u * x) % m return u#driver functionprint(modpower(5, 2, 7))

// function that calculates modular exponentiation x^n mod m.function modpower(x, n, m) { if (n == 0) { // base case return 1 % m; } let u = modpower(x, Math.floor(n / 2), m); u = (u * u) % m; if (n % 2 == 1) { // when 'n' is odd u = (u * x) % m; } return u;}// driver functionconsole.log(modpower(5, 2, 7));

output:4

Time complexity: O(logn), because n is always halved when it is even.

Fermat’s theorem states that

x^m−1 mod m = 1

when m is prime and x and m are coprime. This also yields

x^k mod m = x^{k mod (m−1)} mod m.

Also Read:

• Euler’s Totient Function
• Compute n! under modulo p
• Wilson’s Theorem
• How to compute mod of a big number?
• Find value of y mod (2 raised to power x)

Applications of Modular Arithmetic

1. Cryptography

Modular arithmetic is fundamental in cryptography, particularly in public-key cryptosystems like RSA, which relies on the difficulty of factoring large numbers and properties of modular exponentiation.

2. Computer Science

Modular arithmetic is used in hashing algorithms, checksums, and cryptographic hash functions to ensure data integrity and security.

3. Number Theory

In number theory, modular arithmetic helps solve congruences and Diophantine equations, contributing to the understanding of integer properties and relationships.

4. Digital Signal Processing

Modular arithmetic is used in algorithms for efficient computation in digital signal processing, particularly in the Fast Fourier Transform (FFT) and error-correcting codes.

5. Clock Arithmetic

The concept of modular arithmetic is akin to how clocks work, where the hours wrap around after reaching 12 or 24.

Conclusion – Modular Arithmetic

Modular arithmetic is a powerful mathematical tool with wide-ranging applications in cryptography, computer science, number theory, and digital signal processing. Its properties and rules enable efficient computation and problem-solving in various domains. Understanding modular arithmetic is essential for professionals and researchers in these fields.

FAQs on Modular Arithmetic

What is modular arithmetic?

Modular arithmetic is a system of arithmetic for integers, where numbers wrap around upon reaching a certain value, known as the modulus.

How is modular arithmetic used in cryptography?

Modular arithmetic is fundamental in cryptography, especially in public-key cryptosystems like RSA, which rely on properties of modular exponentiation.

What are the basic operations in modular arithmetic?

The basic operations include addition, subtraction, multiplication, exponentiation, and division, each performed within the confines of a given modulus.

How is modular arithmetic applied in computer science?

It is used in hashing algorithms, checksums, and cryptographic hash functions to ensure data integrity and security.

Why is modular arithmetic important in digital signal processing?

It is used in efficient computation algorithms like the Fast Fourier Transform (FFT) and error-correcting codes, reducing computational complexity.