# Modulo

**Modulo** (Latin, "in the manner of the modulus") names both the remainder operation, written `a mod m` or `a % b`, which returns the remainder left when one integer is divided by another, and the preposition in the congruence relation \( a \equiv b \pmod m \), which states that \( a \) and \( b \) leave the same remainder on division by \( m \). The congruence relation and the associated arithmetic were introduced by [Carl Friedrich Gauss](https://www.edgepedia.org/carl-friedrich-gauss) in *Disquisitiones Arithmeticae*, published in 1801, and modular arithmetic now underlies hashing, pseudo-random number generation, computer arithmetic, and public-key cryptography.<sup>[1](https://www.math.cmu.edu/~rw1k/pgss/CompDiscMathNotes.pdf)</sup><sup> • </sup><sup>[2](https://la.wikisource.org/wiki/Disquisitiones_arithmeticae/Sectio_prima)</sup>

| Key fact | Detail |
|---|---|
| Definition | \( a \equiv b \pmod m \) whenever \( m \mid (a - b) \); the divisor \( m \) is the modulus<sup>[1](https://www.math.cmu.edu/~rw1k/pgss/CompDiscMathNotes.pdf)</sup> |
| Origin | Carl Friedrich Gauss, *Disquisitiones Arithmeticae*, 1801, published when he was 21<sup>[1](https://www.math.cmu.edu/~rw1k/pgss/CompDiscMathNotes.pdf)</sup> |
| Division algorithm | For any integer \( n \) and positive \( d \), unique integers \( q \) and \( r \) satisfy \( n = qd + r \) with \( 0 \le r < d \)<sup>[3](https://math.umd.edu/~pbrosnan/notes/ugalg/sect0005.html)</sup> |
| Algebraic behavior | Congruence is reflexive, symmetric, and transitive; addition, subtraction, and multiplication respect it, but cancellation by a factor not coprime to the modulus does not<sup>[1](https://www.math.cmu.edu/~rw1k/pgss/CompDiscMathNotes.pdf)</sup> |
| Programming form | The `%` operator: in Java it accepts integer and floating-point operands and follows the sign of the dividend; in C it accepts only integer types and division by zero is undefined behavior<sup>[4](https://docs.oracle.com/javase/specs/jls/se15/html/jls-15.html)</sup><sup> • </sup><sup>[5](https://cppreference.net/c/language/operator_arithmetic.html)</sup> |
| Cryptographic use | RSA codes a message as \( y \equiv x^{r} \pmod n \) with public \( n = pq \); decoding requires the secret factors \( p \) and \( q \)<sup>[6](https://dlmf.nist.gov/27.16)</sup> |
| Everyday applications | Hashing, pseudo-random number generation, shift ciphers, and two's complement arithmetic in processors<sup>[7](https://courses.cs.washington.edu/courses/cse311/20sp/lectures/lecture11.html)</sup> |

## Congruence and the modulus

Gauss's definition is stated in the first section of the *Disquisitiones*, "De numerorum congruentia in genere": if a number \( a \) measures the difference of the numbers \( b \) and \( c \), then \( b \) and \( c \) are said to be congruent with respect to \( a \), which is called the modulus; each of \( b \) and \( c \) is a residue of the other, or a non-residue in the contrary case.<sup>[2](https://la.wikisource.org/wiki/Disquisitiones_arithmeticae/Sectio_prima)</sup> In modern notation, for a fixed integer \( m \), integers \( a \) and \( b \) are congruent modulo \( m \), written \( a \equiv b \pmod m \), whenever \( m \) divides \( a - b \); otherwise \( a \not\equiv b \pmod m \).<sup>[1](https://www.math.cmu.edu/~rw1k/pgss/CompDiscMathNotes.pdf)</sup> As an illustration, although 17 and 5 differ as numbers, dividing either by 3 gives a remainder of 2, making them congruent modulo 3.<sup>[8](https://a-warded.org/open-book/university-discrete-mathematics/lesson-18)</sup>

The remainder itself is fixed by the division algorithm: for any integer \( n \) and positive integer \( d \), there exist unique integers \( q \) (the quotient) and \( r \) (the remainder) such that \( n = qd + r \) and \( 0 \le r < d \).<sup>[3](https://math.umd.edu/~pbrosnan/notes/ugalg/sect0005.html)</sup> The remainder can be expressed with the floor function as \( r = n - d \lfloor n/d \rfloor \).<sup>[3](https://math.umd.edu/~pbrosnan/notes/ugalg/sect0005.html)</sup> The clock is the standard illustration: hours run modulo 12, so 7 hours after 8 o'clock is 3 o'clock.

## Algebraic properties

Congruence behaves like equality for the basic operations. It is reflexive (\( a \equiv a \)), symmetric, and transitive, the three properties of an equivalence relation.<sup>[1](https://www.math.cmu.edu/~rw1k/pgss/CompDiscMathNotes.pdf)</sup> If \( a \equiv a' \) and \( b \equiv b' \pmod m \), then \( a + b \equiv a' + b' \), \( a - b \equiv a' - b' \), and \( a \cdot b \equiv a' \cdot b' \pmod m \).<sup>[1](https://www.math.cmu.edu/~rw1k/pgss/CompDiscMathNotes.pdf)</sup> From the late 19th century onward, Gauss's introduction of the congruence relation has been described as the first definition of an equivalence relation in modern mathematics.<sup>[9](https://ghostarchive.org/pdfarc/WcLBP)</sup>

Division is the exception. Although 28 ≡ 10 (mod 6) and 2 divides both 28 and 10, dividing the congruence by 2 fails: 14 is not congruent to 5 modulo 6. Cancellation is valid only when the canceled factor is relatively prime to the modulus, a restriction that follows from the greatest common divisor.<sup>[1](https://www.math.cmu.edu/~rw1k/pgss/CompDiscMathNotes.pdf)</sup>

## History

Gauss developed modular arithmetic and published it in the *Disquisitiones Arithmeticae* in 1801, when he was 21.<sup>[1](https://www.math.cmu.edu/~rw1k/pgss/CompDiscMathNotes.pdf)</sup> The book appeared after a long delay, and each of its seven sections aroused international interest; its chapters cover the theory of arithmetic and congruences, the proof of Euler's conjecture on quadratic reciprocity, quadratic forms, continued fractions, primality tests, and cyclotomic equations.<sup>[10](https://mathshistory.st-andrews.ac.uk/Strick/gauss.pdf)</sup> In his foreword Gauss acknowledged his precursors [Pierre de Fermat](https://www.edgepedia.org/pierre-de-fermat), Leonhard Euler, Joseph-Louis Lagrange, and above all [Adrien-Marie Legendre](https://www.edgepedia.org/adrien-marie-legendre), whose *Essai sur la théorie des nombres* of 1797 overlapped in time with the *Disquisitiones*.<sup>[10](https://mathshistory.st-andrews.ac.uk/Strick/gauss.pdf)</sup> The "modulo" notation \( a \equiv b \bmod n \), read "a is congruent to b modulo n," appears in Gauss's later computation with congruences, including his 1816 Easter algorithm.<sup>[10](https://mathshistory.st-andrews.ac.uk/Strick/gauss.pdf)</sup> A contemporary account notes that his number theory began while he was a student at [Göttingen](https://www.edgepedia.org/gottingen) and that the treatment of the congruence of numbers appears in the 1801 work.<sup>[11](https://en.wikisource.org/wiki/Page%3AA_Source_Book_in_Mathematics_%28Smith%29.pdf/131)</sup>

## Modulo in programming

Programming languages expose the remainder operation as the binary `%` operator, and its behavior on negative operands differs between languages because the underlying division can round in different directions.

**Java.** The Java Language Specification defines `%` as yielding the remainder of an implied division, with the identity `(a/b)*b+(a%b)` equal to `a`. The result is negative only if the dividend is negative and positive only if the dividend is positive, and its magnitude is always less than the divisor's: `5%3` is 2, `5%(-3)` is 2, `(-5)%3` is -2, and `(-5)%(-3)` is -2. If the integer divisor is 0, an `ArithmeticException` is thrown. Unlike C and C++, Java also accepts floating-point operands, defining `%` with round-toward-zero division, comparable to the C library function `fmod`.<sup>[4](https://docs.oracle.com/javase/specs/jls/se15/html/jls-15.html)</sup>

**C and C++.** The binary `%` operator yields the remainder of the first operand divided by the second, and the remainder operator does not work on floating-point types; the library function `fmod` provides that functionality. Since [C99](https://www.edgepedia.org/c99), integer division truncates toward zero, so the sign of the remainder follows the dividend; before that, the sign was implementation-defined. If the second operand is zero, the behavior is undefined, and `INT_MIN % -1` is undefined on two's complement systems.<sup>[5](https://cppreference.net/c/language/operator_arithmetic.html)</sup> In Python, the operator module maps the syntax `a % b` to the function `mod(a, b)`.<sup>[12](https://github.com/python/cpython/blob/main/Doc/library/operator.rst)</sup>

## Applications

**Hashing.** When a handful of values drawn from the large range \( \{0, 1, \ldots, M-1\} \) must be placed into a compact set of slots \( \{0, 1, \ldots, n-1\} \), a hash function computes \( \mathrm{hash}(x) = x \bmod p \), or alternatively \( (ax + b) \bmod p \), where \( p \) is a prime near \( n \). Using all bits of the data helps avoid collisions between similar values.<sup>[7](https://courses.cs.washington.edu/courses/cse311/20sp/lectures/lecture11.html)</sup>

**Pseudo-random number generation.** The linear congruential method generates a sequence from \( x_{n+1} = (a x_n + c) \bmod m \) with chosen \( x_0 \), \( a \), \( c \), and \( m \).<sup>[7](https://courses.cs.washington.edu/courses/cse311/20sp/lectures/lecture11.html)</sup>

**Ciphers.** The Caesar or shift cipher treats letters as numbers A = 0, B = 1, and so on, encoding with \( f(p) = (p + k) \bmod 26 \) and decoding with \( f^{-1}(p) = (p - k) \bmod 26 \); a more general affine version uses \( (ap + b) \bmod 26 \).<sup>[7](https://courses.cs.washington.edu/courses/cse311/20sp/lectures/lecture11.html)</sup>

**Public-key cryptography.** RSA-style public-key codes exploit the disparity in computer time required to find large primes and to factor large integers. A code maker chooses two large secret primes \( p \) and \( q \) of about 400 decimal digits each and publishes their product \( n = pq \), an 800-digit number. A message piece \( x \) is coded as \( y \equiv x^{r} \pmod n \) for a public prime \( r \); to decode, the receiver computes the reciprocal \( s \) of \( r \) modulo Euler's totient (count of integers up to n coprime with n) \( \varphi(n) \), so that \( y^{s} \equiv x \pmod n \). With the most efficient techniques known as of 2010, factoring an 800-digit number may require billions of years on a single computer, so the codes are considered unbreakable at least with the current state of knowledge on factoring.<sup>[6](https://dlmf.nist.gov/27.16)</sup> University cryptography courses accordingly build their number-theory foundation on modular arithmetic, Euclid's algorithm, [Euler's theorem](https://www.edgepedia.org/eulers-theorem), the [Chinese remainder theorem](https://www.edgepedia.org/chinese-remainder-theorem), and modular exponentiation before turning to Diffie-Hellman key exchange, [ElGamal encryption](https://www.edgepedia.org/elgamal-encryption), and elliptic-curve systems.<sup>[13](https://www.cl.cam.ac.uk/teaching/2526/Crypto/)</sup>

**Computer arithmetic.** [Modular arithmetic](https://www.edgepedia.org/modular-arithmetic) is described as the basis of computing: it is used with two's complement representation to implement processor arithmetic, where an \( n \)-bit register represents \( -|x| \) as the unsigned value \( 2^{n} - |x| \).<sup>[7](https://courses.cs.washington.edu/courses/cse311/20sp/lectures/lecture11.html)</sup>

## References

1. [Modular Arithmetic, PGSS Computational Discrete Mathematics Notes, Carnegie Mellon University](https://www.math.cmu.edu/~rw1k/pgss/CompDiscMathNotes.pdf)
2. [Disquisitiones arithmeticae, Sectio prima, Wikisource (Latin)](https://la.wikisource.org/wiki/Disquisitiones_arithmeticae/Sectio_prima)
3. [The division algorithm with remainder, UMD 403: Undergraduate Algebra](https://math.umd.edu/~pbrosnan/notes/ugalg/sect0005.html)
4. [Chapter 15. Expressions, The Java Language Specification, SE 15, Oracle](https://docs.oracle.com/javase/specs/jls/se15/html/jls-15.html)
5. [Arithmetic operators, C reference, cppreference.net](https://cppreference.net/c/language/operator_arithmetic.html)
6. [DLMF §27.16 Cryptography, NIST Digital Library of Mathematical Functions](https://dlmf.nist.gov/27.16)
7. [CSE 311 Spring 2020 Lecture 11, University of Washington](https://courses.cs.washington.edu/courses/cse311/20sp/lectures/lecture11.html)
8. [Modular Arithmetic, Discrete Mathematics, A-Warded](https://a-warded.org/open-book/university-discrete-mathematics/lesson-18)
9. [Modular Arithmetics before C.F. Gauss](https://ghostarchive.org/pdfarc/WcLBP)
10. [Carl Friedrich Gauss, Heinz Klaus Strick, MathShistory, University of St Andrews](https://mathshistory.st-andrews.ac.uk/Strick/gauss.pdf)
11. [A Source Book in Mathematics, Smith, page 131, Wikisource](https://en.wikisource.org/wiki/Page%3AA_Source_Book_in_Mathematics_%28Smith%29.pdf/131)
12. [operator module documentation, CPython, GitHub](https://github.com/python/cpython/blob/main/Doc/library/operator.rst)
13. [Cryptography course pages 2025–26, Department of Computer Science and Technology, University of Cambridge](https://www.cl.cam.ac.uk/teaching/2526/Crypto/)

---
*Topic: Encyclopedia › Physical world and mathematics › Mathematics and statistics › Numbers and algebra › Arithmetic and number systems › Computational arithmetic*

*Initially written Sep 17, 2026 · Reviewed: Oct 15, 2026 · Edited: Oct 15, 2026; Oct 25, 2026 · Last review: Oct 15, 2026*

*Copyright 2026 EdgeChat AI, a subsidiary of Biostate AI.*

License: Edgepedia Community License 1.0, https://www.edgepedia.org/edgepedia/license