Modulo Calculator

How the Modulo Operation Works

The modulo operation (often written as a mod b, a % b, or a MOD b) returns the remainder when one integer is divided by another. As defined in Wolfram MathWorld and standard number theory textbooks, the modulo is one of the most fundamental operations in both pure mathematics and computer science. The fundamental relationship is a = q x b + r, where q is the quotient (the integer result of the division) and r is the remainder (the modulo result). For example, 17 mod 5 = 2 because 17 = 3 x 5 + 2. The remainder r always satisfies 0 <= r < b for positive divisors. This calculator computes the modulo of any two integers, shows the quotient, and displays the complete division equation, following the standard mathematical convention where the result is always non-negative.

The modulo operation is distinct from division in that it only returns the leftover part. When you divide 23 by 7, the answer is 3 with remainder 2, so 23 mod 7 = 2. When the dividend is perfectly divisible by the divisor, the modulo result is 0: 24 mod 6 = 0 because 24 = 4 x 6 + 0 with no remainder. When the dividend is smaller than the divisor, the modulo result equals the dividend itself: 3 mod 7 = 3, because 3 = 0 x 7 + 3. These simple rules cover all cases for positive numbers and form the foundation of modular arithmetic.

Clock Arithmetic: The Everyday Analogy

Modular arithmetic is often called "clock arithmetic" because a 12-hour clock is a perfect real-world model of mod 12. If it is 10 o'clock and you add 5 hours, the clock shows 3 (not 15), because 15 mod 12 = 3. If it is 2 o'clock and you go back 5 hours, the clock shows 9 (not -3), because the clock wraps around. This wrapping behavior is the essence of modular arithmetic: numbers cycle back to the beginning after reaching the modulus.

Days of the week work the same way with mod 7. If today is Wednesday (day 3, counting from Sunday = 0) and you want to know what day it will be in 100 days, compute (3 + 100) mod 7 = 103 mod 7 = 5, which is Friday. Calendars, shift schedules, and any repeating pattern can be modeled with modular arithmetic. The 24-hour clock uses mod 24, the minute and second displays use mod 60, and the months of the year use mod 12. Any time you encounter a cyclical system, modular arithmetic is the natural mathematical tool for working with it.

Modulo with Negative Numbers

Handling negative numbers in modulo operations is a source of confusion because different programming languages use different conventions. In mathematics, the modulo result is always non-negative: -7 mod 3 = 2, because -7 = (-3) x 3 + 2. However, in C, C++, Java, and JavaScript, the % operator returns a remainder with the same sign as the dividend: -7 % 3 = -1, because -7 = (-2) x 3 + (-1). Python and Ruby follow the mathematical convention: -7 % 3 = 2.

To convert a potentially negative remainder to the mathematical (non-negative) modulo in languages that use truncated division, use the formula: ((a % b) + b) % b. This adds b to the result if it is negative, then takes the modulo again to handle the case where a was already positive. This calculator uses the mathematical convention, always returning a non-negative result, which matches the behavior of Python and the formal definition in number theory. Understanding this distinction is critical when porting code between programming languages.

Properties of Modular Arithmetic

Modular arithmetic satisfies several useful algebraic properties. Addition is compatible with modulo: (a + b) mod n = ((a mod n) + (b mod n)) mod n. Multiplication is similarly compatible: (a x b) mod n = ((a mod n) x (b mod n)) mod n. Subtraction also works: (a - b) mod n = ((a mod n) - (b mod n) + n) mod n. These properties allow you to reduce intermediate results during computation, which is essential when working with very large numbers that might otherwise overflow.

However, division in modular arithmetic is more complex. You cannot simply divide and take the modulo. Instead, division by a is replaced by multiplication by the modular inverse of a (if it exists). The modular inverse of a modulo n exists if and only if gcd(a, n) = 1 -- that is, a and n are coprime. When the modulus is prime, every nonzero element has an inverse, and the integers modulo p form a field, which is the mathematical structure that underlies finite field arithmetic in coding theory and cryptography.

Modulo in Programming

The modulo operator is one of the most frequently used tools in programming. Checking whether a number is even or odd (n % 2 == 0 for even) is perhaps the simplest application. Cycling through array indices with (index % arrayLength) creates circular buffers and round-robin scheduling. Formatting output by inserting a line break every k items uses (i % k == 0). Extracting the last digit of a number uses n % 10, the last two digits use n % 100, and so on. Time conversions -- converting total seconds into hours, minutes, and remaining seconds -- rely on modulo 3600 and modulo 60.

Hash functions use modulo to map keys into a fixed-size table: hash(key) = someFunction(key) % tableSize. This is the foundation of hash tables, one of the most important data structures in computer science. The choice of table size matters -- prime numbers are preferred because they distribute keys more evenly, reducing collisions. In competitive programming and algorithm contests, problems often require computing results "modulo 10^9 + 7" (a large prime) to keep numbers within integer range while preserving mathematical properties needed for correctness.

Modular Arithmetic in Cryptography

Modern cryptography is built on modular arithmetic. According to NIST's Digital Signature Standard, the RSA encryption algorithm, which secures much of the internet's communication, works by choosing two large prime numbers p and q, computing their product n = p x q, and performing modular exponentiation. A message m is encrypted as c = m^e mod n and decrypted as m = c^d mod n, where e and d are the public and private exponents related by the equation e x d = 1 mod phi(n). The security relies on the fact that factoring the product n back into p and q is computationally infeasible for sufficiently large primes (typically 2048 bits or more).

The Diffie-Hellman key exchange protocol allows two parties to establish a shared secret over an insecure channel using modular exponentiation. Each party chooses a secret number, computes a public value using modular exponentiation with a shared prime modulus, and exchanges public values. The shared secret is then computed by each party using their own secret and the other's public value. The discrete logarithm problem -- finding the exponent given the base, result, and modulus -- is believed to be computationally hard, providing the security foundation. Elliptic curve cryptography extends these ideas to elliptic curves over finite fields, providing equivalent security with smaller key sizes.

Check Digit Algorithms

Many identification numbers include a check digit computed using modulo to catch transcription errors. The Luhn algorithm, used for credit card numbers, computes a weighted sum of digits and checks that the result is divisible by 10 (sum mod 10 == 0). This catches all single-digit errors and most adjacent transposition errors. ISBN-10 codes use a weighted sum modulo 11, with the check digit being the value needed to make the sum divisible by 11 (using 'X' to represent 10). ISBN-13 uses modulo 10 with alternating weights of 1 and 3.

Bank routing numbers in the United States use a weighted sum modulo 10 with weights 3, 7, and 1 repeating. Vehicle Identification Numbers (VINs) use a modulo 11 check digit. National identification numbers in many countries -- including Social Security numbers in some validation schemes -- employ modular arithmetic for error detection. These algorithms provide a fast, simple way to detect common human errors in data entry without requiring a database lookup, and they all depend fundamentally on the modulo operation.

Number Theory and Congruences

In formal number theory, the modulo relationship is expressed using congruences: a is congruent to b (mod n), written a = b (mod n), means that n divides (a - b). This is an equivalence relation that partitions the integers into n residue classes. For example, modulo 3, all integers fall into one of three classes: those congruent to 0 (multiples of 3), those congruent to 1 (numbers like 1, 4, 7, 10...), and those congruent to 2 (numbers like 2, 5, 8, 11...). Arithmetic on residue classes forms the ring of integers modulo n, denoted Z/nZ.

Important theorems in number theory are stated in terms of congruences. Fermat's Little Theorem states that if p is prime and a is not divisible by p, then a^(p-1) = 1 (mod p). Euler's theorem generalizes this: a^phi(n) = 1 (mod n) when gcd(a, n) = 1, where phi(n) is Euler's totient function. The Chinese Remainder Theorem provides a method for solving systems of simultaneous congruences with coprime moduli. These theoretical results have direct practical applications in computing modular inverses, speeding up RSA decryption, and generating pseudorandom numbers.