AntInLoop

Modular Arithmetic Code Implementations

Complete Modular Arithmetic code implementations in C++, Python, Java, and JavaScript with time and space complexity analysis on AntInLoop.

Read Modular Arithmetic Guide ยท Launch Interactive Visualizer

C++ Implementation

// Modular Arithmetic in C++
#include <iostream>

class ModularArithmetic {
public:
    static int modAdd(int a, int b, int mod) {
        return ((a % mod) + (b % mod)) % mod;
    }

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

    static int modMul(int a, int b, int mod) {
        return ((long long)(a % mod) * (b % mod)) % mod;
    }

    static int modPow(int base, int exponent, int mod) {
        int result = 1;
        base %= mod;
        while (exponent > 0) {
            if (exponent % 2 == 1)
                result = (int)((1LL * result * base) % mod);
            base = (int)((1LL * base * base) % mod);
            exponent /= 2;
        }
        return result;
    }

    // Modular inverse using Fermat's Little Theorem (mod must be prime)
    static int modInverse(int a, int mod) {
        return modPow(a, mod - 2, mod);
    }
};

JAVA Implementation

// Modular Arithmetic in Java

public class ModularArithmetic {

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

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

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

    public static int modPow(int base, int exponent, int mod) {
        int result = 1;
        base = base % mod;
        while (exponent > 0) {
            if ((exponent & 1) == 1)
                result = (int)((long)result * base % mod);
            base = (int)((long)base * base % mod);
            exponent >>= 1;
        }
        return result;
    }

    // Modular inverse using Fermat's Little Theorem (mod must be prime)
    public static int modInverse(int a, int mod) {
        return modPow(a, mod - 2, mod);
    }
}

JAVASCRIPT Implementation

// Modular Arithmetic in JavaScript

function modAdd(a, b, mod) {
  return ((a % mod) + (b % mod)) % mod;
}

function modSub(a, b, mod) {
  return ((a % mod) - (b % mod) + mod) % mod;
}

function modMul(a, b, mod) {
  return ((a % mod) * (b % mod)) % mod;
}

function modPow(base, exponent, mod) {
  let result = 1;
  base = base % mod;
  while (exponent > 0) {
    if (exponent % 2 === 1) {
      result = (result * base) % mod;
    }
    base = (base * base) % mod;
    exponent = Math.floor(exponent / 2);
  }
  return result;
}

// Modular inverse using Fermat's Little Theorem (mod must be prime)
function modInverse(a, mod) {
  return modPow(a, mod - 2, mod);
}

PYTHON Implementation

# Modular Arithmetic in Python

def mod_add(a, b, mod):
    return (a % mod + b % mod) % mod

def mod_sub(a, b, mod):
    return (a % mod - b % mod + mod) % mod

def mod_mul(a, b, mod):
    return (a % mod * b % mod) % mod

def mod_pow(base, exponent, mod):
    result = 1
    base %= mod
    while exponent > 0:
        if exponent % 2:
            result = (result * base) % mod
        base = (base * base) % mod
        exponent //= 2
    return result

# Modular inverse using Fermat's Little Theorem (mod must be prime)
def mod_inverse(a, mod):
    return mod_pow(a, mod - 2, mod)