Modular Arithmetic

Modular arithmetic is a type of arithmetic operation that revolves around remainders. It involves performing arithmetic operations on remainders of numbers after dividing them by a fixed number called the modulus. In C++, modular arithmetic is implemented using the modulo operator %.

For example, suppose we want to perform the operation (4 + 7) % 3. This involves adding 4 and 7, which gives us 11. We then take the remainder of 11 after dividing it by 3, which is 2. Therefore, the result of (4 + 7) % 3 is 2.

In C++, we could write this as:


int result = (4 + 7) % 3;

This would set the variable result equal to 2.

Modular arithmetic in C++ is commonly used for a variety of purposes, including:

Hashing algorithms

Cryptography

Generating random numbers

Modular arithmetic is often performed using a fixed modulus value. In many programming contests and applications, the most common modulus value used is 10^9+7, which is usually written as 1e9+7. This particular modulus value is often used for a number of reasons, including its large size, which makes it unlikely for the results to overflow; and its relative prime nature, which ensures that many operations can be performed efficiently.

Using mod 1e9+7 for modular arithmetic in C++ involves taking the remainder of a calculation after dividing it by this fixed value. For example, suppose we want to calculate the result of (3 * 5) + (7 * 2) modulo 1e9+7. We can perform the calculation first, which gives us 29. We then take the remainder of 29 after dividing it by 1e9+7:


int result = ((3 * 5) + (7 * 2)) % 1000000007;

This sets the result variable equal to 29 modulo 1e9+7, which is 29.

Using the mod 1e9+7 for modular arithmetic in C++ is commonly used in programming contests and applications, particularly in problems involving large numbers and algorithms such as dynamic programming, hashing, and combinatorics.

Modular arithmetic involves performing basic arithmetic operations, such as addition, subtraction, multiplication, and division, using a fixed modulus value.

Modular Addition:

Modular addition is performed by adding the two numbers first and then taking the remainder of the sum after dividing by the modulus. In C++, the modulo operator % is used for this purpose. For example, to calculate the result of (a+b) % m, where a, b, and m are integer numbers, we could use the following code:


int result = ((a % m) + (b % m)) % m;

Modular Subtraction:

Modular subtraction is performed by first subtracting the second number from the first number and then taking the remainder of the difference after dividing by the modulus. In C++, the modulo operator % is used for this purpose. For example, to calculate the result of (a-b) % m, where a, b, and m are integer numbers, we could use the following code:


int result = ((a % m) - (b % m)) % m;

Note that we add m to the difference before taking the remainder to ensure that the result is positive.

Modular Multiplication:

Modular multiplication is performed by multiplying the two numbers first and then taking the remainder of the product after dividing by the modulus. In C++, the modulo operator % is used for this purpose. For example, to calculate the result of (a*b) % m, where a, b, and m are integer numbers, we could use the following code:


int result = ((a % m) * (b % m)) % m;

Modular Division:

Modular division is performed by calculating the modular inverse of the second number and then multiplying it with the first number. The modular inverse of a number b with respect to a modulus m is the value of x such that (b*x) % m = 1. In C++, several methods can be used to calculate the modular inverse, such as Extended Euclidean Algorithm, Fermat's Little Theorem,and Binary Exponentiation. Once the modular inverse inv of b modulo m has been calculated, the result of (a/b) % m is calculated as:


int result = (a * inv) % m;

Overall, these modular arithmetic operations are helpful in many programming and mathematical contexts where dealing with large integer numbers or remainders is required.

Fermat’s theorem:

Fermat's Little Theorem is a mathematical theorem that provides a way to find the remainder of a division operation in modular arithmetic.

Modular arithmetic is a type of arithmetic where numbers "wrap around" after reaching a certain value. For example, in modular arithmetic with a modulus of 8, the sequence of numbers goes 0, 1, 2, 3, 4, 5, 6, 7, 0, 1, 2, 3, ... and so on. If you add 1 to 7 in modular arithmetic with a modulus of 8, you "wrap around" to 0.

Fermat's Little Theorem states that for any prime number p and any integer a not divisible by p, a raised to the power of p-1 is congruent to 1 modulo p. In other words,

a^(p-1) ≡ 1 (mod p)

This theorem is useful for finding the remainder of a division operation in modular arithmetic. For example, if you want to find the remainder of 28 divided by 7 in modular arithmetic with a modulus of 5, you can use Fermat's Little Theorem:

First, note that 7 is a prime number and not divisible by 5, so we can use Fermat's Little Theorem with a=28 and p=7:

28^(7-1) ≡ 1 (mod 7)

28^6 ≡ 1 (mod 7)

Now we can reduce 28 to an equivalent value modulo 7:

28 ≡ 0 (mod 7)

So we can substitute this into the equation:

0^6 ≡ 1 (mod 7)

0 ≡ 1 (mod 7)

Since 0 is not congruent to 1 modulo 7, our assumption was incorrect and we cannot use Fermat's Little Theorem to find the remainder of 28 divided by 7 in modular arithmetic with a modulus of 5.


#include <iostream>
using namespace std;

// Function to calculate a^b mod m
int powmod(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 /= 2;
    }
    return res;
}

// Function to calculate the remainder of a/b mod m
int moddiv(int a, int b, int m) {
    int inverse = powmod(b, m-2, m);
    return (a * inverse) % m;
}

int main() {
    int a, b, m;
    cout << "Enter a, b, and m: ";
    cin >> a >> b >> m;
    int remainder = moddiv(a, b, m);
    cout << "The remainder of " << a << "/" << b << " mod " << m << " is: " << remainder << endl;
    return 0;
}

The powmod function calculates a^b mod m efficiently using exponentiation by squaring. The moddiv function calculates the remainder of a/b mod m by finding the inverse of b using Fermat's Little Theorem and then multiplying a by the inverse modulo m.

In the main function, the user is prompted to enter the values of a, b, and m. The moddiv function is called with these values, and the resulting remainder is printed to the console.

PRACTICE PROBLEMS :

Number of Music Playlists

Count the Number of Ideal Arrays