What is Modular Arithmetic in DSA?

• Modular arithmetic is an arithmetic structure for integers, in which numbers “wrap around” when they reach a certain magnitude.
• Many areas of mathematics and computer science use modular arithmetic, including number theory, combinatorics, coding theory, and error-correcting codes.
• It is also utilized in algorithm design and analysis, notably in algorithms dealing with huge numbers of cryptographic operations.
• The distributive, associative, and commutative properties of modular arithmetic make it a helpful tool in various applications. Overall, modular arithmetic is a powerful mathematical tool with diverse applications in various disciplines.

Real-life uses of Modular Arithmetic:

• Hash Tables: Modular arithmetic is used in hash tables to compute the hash code of a key.
• Disjoint Sets: In disjoint-set data structures, modular arithmetic can be used to represent sets of integers as nodes in a tree.
• Random Number Generators: Modular arithmetic is used to produce pseudorandom numbers in algorithms that require random numbers.
• Primality Testing: Modular arithmetic is used in methods for verifying the primality of huge numbers to determine whether a number is a probable prime.
• Cryptography: Modular arithmetic is often utilized in cryptography techniques, such as the RSA and ElGamal encryption schemes.

Theorems associated with Modular Arithmetic:

There are several theorems associated with modular arithmetic that are used in various applications:

• The Division Theorem: asserts that there are two distinct numbers q and r for each pair of integers a and b (b is positive) such that:

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

For instance, if a=40 & b=7 then q=5 & r=5 :

40= 7 x 5 + 5

• Modular addition and subtraction: It follows the same rule such that:

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

For instance,

if a=10, b=50 & m= 7 :

(10 + 50) mod 7 = ((10 mod 7) + (50 mod 7)) mod 7
60 mod 7 = (3 + 1) mod 7
4 = 4

• Modular Multiplication: This rule states that:

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

For instance,

if a=10, b=50 & m= 7 :

(10 x 50) mod 7 = ((10 mod 7) x (50 mod 7)) mod 7
500 mod 7 = (3 x 1) mod 7
3 = 3

• Modular division: It is calculated using the formula:

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

If b and m are relatively prime, then the modular inverse of b modulo m exists and can be found using the extended Euclidean algorithm.

• Modular exponentiation: It involves finding a^b mod m. This can be done recursively or iteratively, with the time complexity being O(log n) using recursion. For instance, if a=2, b=4 & m=7 then:

a^b mod m =
2^4 mod 7 = 16 mod 7
= 2

Example:

Let us look at some codes to solve the above laws in a programmatic way:

Modular Arithmetic Operations for DSA:

public static int modAdd(int a, int b, int m) {
    return ((a % m) + (b % m)) % m;
}

public static int modSub(int a, int b, int m) {
    return ((a % m) - (b % m) + m) % m;
}

public static int modMul(int a, int b, int m) {
    return ((a % m) * (b % m)) % m;
}

public static int modDiv(int a, int b, int m) {
    int inv = modInverse(b, m);
    return (a * inv) % m;
}

Modular Exponentiation:

public static int modExp(int a, int b, int m) {
    int res = 1;
    while (b > 0) {
        if (b % 2 == 1) {
            res = (res * a) % m;
        }
        a = (a * a) % m;
        b = b / 2;
    }
    return res;
}

Properties of Modular Arithmetic:

These are the properties of modular arithmetic:

1. Commutative laws: The order of the operands does not matter for addition and multiplication modulo n. That is, (a + b) mod m = (a + b) mod m and (a x b) mod n = (b x a) mod m.
2. Associative laws: The grouping of the operands does not matter for addition and multiplication modulo m. That is, [(a + b)+c] mod m = [a+(b+c)] mod m.
3. Distributive laws: Multiplication distributes over addition modulo m. That is, [(a x b) x c] mod m = [a x (b x c)] mod m.
4. Identities: There exist additive and multiplicative identities in modular arithmetic. For any a ∈ Zm, (0 + a) mod m = a mod m and (1 x a) mod m = a mod m.
5. Additive inverse: For any a ∈ Zm, there exists an additive inverse (-a) such that a + (-a) ≡ 0 mod m.
6. Existence of multiplicative inverse: For any a ∈ Zm, there exists a multiplicative inverse z such that a x z ≡ 1 mod m.

Given a positive integer k, you need to find the length of the smallest positive integer n such that n is divisible by k, and n only contains the digit 1. Return the length of n. If there is no such n, return -1.

i.e,

Input: k = 3
Output: 3
Explanation: The smallest answer is n = 111, which has length 3.

Solution:

class Solution {
                                                                                                                                                                                                                                                                                                                                   
        
    public int smallestRepunitDivByK(int k) {
    if (k % 2 == 0 || k % 5 == 0) {
        // if k is divisible by 2 or 5, n will never be divisible by k
        return -1;
    }
    int num = 1;
    int length = 1;
    while (num % k != 0) {
        num = (num * 10 + 1) % k;
        length++;
    }
    return length;
}

}

We did this using modular arithmetic as follows:

1. Initialize a variable num with the value 1, and a variable length with the value 1.
2. While num is not divisible by k, do the following:
   • Update num to be (num * 10 + 1) % k.
   • Increment length by 1.
3. If num is divisible by k, return length. Otherwise, return -1.

Note: also read about Problems based on bit manipulation

Follow Me

Please follow me to read my latest post on programming and technology if you like my post.

https://www.instagram.com/coderz.py/

https://www.facebook.com/coderz.py