Real-world use

#include <cstdint>
#include <iostream>

const long long MOD = 1'000'000'007LL;

long long mod_pow(long long base, long long exp, long long mod) {
    long long result = 1 % mod;
    base %= mod;
    while (exp > 0) {
        if (exp & 1) result = result * base % mod;  // both below mod: fits in 64 bits
        base = base * base % mod;
        exp >>= 1;
    }
    return result;
}

// modulus near 10^18: multiply in 128 bits (GCC/Clang)
uint64_t mul_mod(uint64_t a, uint64_t b, uint64_t m) {
    return static_cast<uint64_t>(static_cast<unsigned __int128>(a) * b % m);
}

int main() {
    int a = 1'000'000'000, b = 1'000'000'000;
    long long wrong = a * b;              // overflows in int arithmetic first
    long long right = 1LL * a * b % MOD;  // widen to 64 bits before multiplying
    std::cout << right << ' ' << mod_pow(2, 1'000'000'000'000LL, MOD) << '\n';
    (void)wrong;
}

Pitfall 2: remainders of negative numbers

In Python -7 % 3 is 2; in C++ and Java it is -1. Normalize with ((x % m) + m) % m or Java's Math.floorMod, including the possibly negative x from extended Euclid.

import java.math.BigInteger;

public class ModPitfalls {
    public static void main(String[] args) {
        final long MOD = 1_000_000_007L;
        int a = 1_000_000_000, b = 1_000_000_000;
        long wrong = a * b;              // wrapped int product: -1486618624
        long right = (long) a * b % MOD; // 49
        System.out.println(wrong + " " + right);

        System.out.println(-7 % 3);               // -1
        System.out.println(Math.floorMod(-7, 3)); // 2

        BigInteger x = BigInteger.valueOf(3);
        BigInteger m = BigInteger.valueOf(MOD);
        System.out.println(x.modInverse(m));                        // 333333336
        System.out.println(x.modPow(BigInteger.valueOf(200), m)); // 136318165
    }
}

Pitfall 3: other common mistakes

• Fermat's a^(p-2) is the inverse only when the modulus is prime. For a composite modulus use extended Euclid and check coprimality.
• lcm(a, b) = a * b / gcd(a, b) overflows in the product first. Compute a / gcd(a, b) * b instead.
• C++ pow and JavaScript Math.pow use floating point and lose precision on large integer powers; sqrt(n) does too, so write loop bounds as i * i <= n or use math.isqrt.
• A sieve beyond about 10^8 entries strains memory; use a bit array or a segmented sieve.
• JavaScript number is exact only up to 2^53, so multiply residues modulo 10^9 + 7 as BigInt (for example (999_999_999n * 999_999_999n) % 1_000_000_007n is 64n, while the number version gives 63).

Summary

RSA, hashing, random number generators and check digits all rest on modular arithmetic. Use the standard library first (gcd, pow, BigInteger); in your own code, check for multiplication overflow, negative remainders, non-prime moduli and floating-point powers. Never build cryptography yourself.

Further reading

• Python math module
• Python built-in pow
• cppreference: std::gcd
• Java BigInteger
• cp-algorithms: Binary Exponentiation
• cp-algorithms: Binomial Coefficients
• Wikipedia: RSA cryptosystem