# Remainder

A **remainder** is the integer left over when one integer (the dividend) is divided by another (the divisor) and only whole multiples of the divisor are subtracted. Dividing 14 by 3 gives four full groups with 2 left over, written 14 = 3 · 4 + 2, so the remainder is 2.<sup>[1](https://www.csd.uwo.ca/~abrandt5/teaching/DiscreteStructures/Chapter4/div-mod.html)</sup>

| Key fact | Detail |
|---|---|
| Defining theorem | For integers \( b \) and \( a \neq 0 \) there exist unique integers \( q \) and \( r \) with \( b = aq + r \) and \( 0 \leq r < a \).<sup>[1](https://www.csd.uwo.ca/~abrandt5/teaching/DiscreteStructures/Chapter4/div-mod.html)</sup> |
| Names | \( q \) is the quotient and \( r \) the remainder; the operations that return them are often written div and mod.<sup>[1](https://www.csd.uwo.ca/~abrandt5/teaching/DiscreteStructures/Chapter4/div-mod.html)</sup> |
| Worked example | \( 14 = 3 \cdot 4 + 2 \): 3 divides 14 four times with a remainder of 2.<sup>[1](https://www.csd.uwo.ca/~abrandt5/teaching/DiscreteStructures/Chapter4/div-mod.html)</sup> |
| Historical role | Euclid began his number theory in the *Elements* with his algorithm, which is essentially equivalent to Bézout's equation and the division algorithm; Gauss built the theory of congruences on remainders in *Disquisitiones Arithmeticae* (1801).<sup>[2](https://arxiv.org/abs/0902.2465)</sup> |
| Computing gcd | Repeated division with remainder, stopping when the remainder is zero, is the Euclidean algorithm for the greatest common divisor.<sup>[3](https://math.oxford.emory.edu/site/math125/euclideanAlgorithm/)</sup> |
| Applications | Remainders power modular arithmetic, which underlies public-key cryptography, checksums and check digits, hash tables, and calendar cycles.<sup>[4](https://www.yijiansuan.com/en/guide/modular-guide)</sup> |

## The division theorem

The existence and uniqueness of the remainder is a theorem, usually called the division algorithm or [Euclidean division](https://www.edgepedia.org/euclidean-division) even though it is not itself a sequence of steps.<sup>[5](https://www.math.cmu.edu/~bkell/21110-2010s/extended-euclidean.html)</sup> In its standard form: let \( a, b \) be integers with \( a \neq 0 \); then there exist unique integers \( q \) and \( r \) such that

\[ b = aq + r, \quad 0 \leq r < a. \]

The condition \( 0 \leq r < a \) is what makes the pair unique: without a bound on \( r \), the same division could be written many ways, for example \( 14 = 3 \cdot 3 + 5 \) as well as \( 14 = 3 \cdot 4 + 2 \).<sup>[1](https://www.csd.uwo.ca/~abrandt5/teaching/DiscreteStructures/Chapter4/div-mod.html)</sup> A standard proof considers the set of nonnegative integers expressible as \( n - qd \) and takes its smallest element; if that element were at least \( d \), subtracting \( d \) would produce a smaller one, a contradiction.<sup>[6](https://www.math.umd.edu/~pbrosnan/notes/ugalg/sect0005.html)</sup>

The quotient is often written \( \lfloor n/m \rfloor \), the floor of \( n/m \), to make clear that the integer quotient is meant, and the remainder is then \( n \bmod m \).<sup>[7](https://cs.yale.edu/homes/aspnes/pinewiki/NumberTheory.html)</sup>

## The Euclidean algorithm

**Repeated remainders find the gcd.** Dividing \( m \) by \( n \) yields a unique quotient and remainder; applying the same process to the new pair produces a still smaller pair, and so on, until a division with remainder zero terminates the process.<sup>[3](https://math.oxford.emory.edu/site/math125/euclideanAlgorithm/)</sup> This is Euclid's algorithm, and it computes the greatest common divisor of the two numbers. Keeping track of additional information along the way yields the extended [Euclidean algorithm](https://www.edgepedia.org/euclidean-algorithm), which also finds integer coefficients expressing the gcd as a linear combination of the two original numbers.<sup>[5](https://www.math.cmu.edu/~bkell/21110-2010s/extended-euclidean.html)</sup>

The algorithm's historical weight is considerable. Euclid opened the number-theoretic books of the *Elements* with this algorithm rather than with division, and it is essentially equivalent to Bézout's equation and the division algorithm; it also implies Euclid's first theorem, the heart of the uniqueness part of the fundamental theorem of arithmetic, and Euclid's second theorem, that there are infinitely many primes. [Donald Knuth](https://www.edgepedia.org/donald-knuth) called Euclid's method "the granddaddy of all algorithms".<sup>[2](https://arxiv.org/abs/0902.2465)</sup>

## Modular arithmetic

The remainder defines congruence: two integers are congruent modulo \( m \) when they leave the same remainder on division by \( m \). [Modular arithmetic](https://www.edgepedia.org/modular-arithmetic) can be viewed simply as finding the remainder when one number is divided by another.<sup>[8](https://education.casio.co.uk/article-modular-arithmetic-explained-basics-applications-and-examples/)</sup> From the division algorithm, for each \( n \) and \( m \) there is a unique remainder \( r \) with \( 0 \leq r < m \) and \( n = qm + r \), and this unique \( r \) is written \( n \bmod m \).<sup>[7](https://cs.yale.edu/homes/aspnes/pinewiki/NumberTheory.html)</sup>

Remainder arithmetic has a wide practical reach. It plays a central role in cryptography, where encryption and decryption algorithms use modular operations to protect data and generate secure keys.<sup>[8](https://education.casio.co.uk/article-modular-arithmetic-explained-basics-applications-and-examples/)</sup> It also powers week cycles, checksums such as the last digit of ID cards (a weighted sum mod 11 in the GB 11643 standard), and hash tables.<sup>[4](https://www.yijiansuan.com/en/guide/modular-guide)</sup> In the ISBN scheme, the first nine digits carry publication data and the tenth digit is a redundancy check for errors.<sup>[9](https://www.cs.cornell.edu/~rafael/discmath.pdf)</sup> A useful algebraic fact is that remainders of powers depend only on the remainder of the base: if a number is written \( mq + r \), then \( (mq+r)^2 = m(mq^2 + 2qr) + r^2 \), so the final remainder of the square is determined by \( r^2 \) alone.<sup>[10](https://www.math.gordon.edu/~kcrisman/mat338/section-5.html)</sup>

## Remainders in programming

**Languages disagree on negative dividends.** Java's language specification defines `%` on floating-point operands analogously to the integer remainder operator, with an implied division using round-toward-zero, comparable to the C library function `fmod`; the floating-point remainder \( r \) of \( n \) divided by \( d \) satisfies \( r = n - d \cdot q \) with \( q \) chosen as large as possible in magnitude without exceeding the true quotient.<sup>[11](https://download.java.net/java/early_access/jdk27/docs/specs/jls/jls-15.html)</sup> The practical consequence is that code hashing or indexing with negative values must know the language's convention before relying on the result.<sup>[4](https://www.yijiansuan.com/en/guide/modular-guide)</sup>

## Cultural and computational extensions

A modified form of Euclid's algorithm gained popularity among musical composers after Godfried Toussaint's 2005 survey of Euclidean rhythms in world music; one non-recursive matrix construction uses only modular arithmetic and combinatorics, though it does not outperform the traditional divide-with-remainder method.<sup>[12](https://arxiv.org/abs/2206.12421)</sup> In computer arithmetic, Barrett-type algorithms carry out entire computations in residue form using only modular arithmetic, without converting back to large integers via the Chinese Remainder Theorem, with cryptographic applications in view.<sup>[13](https://arxiv.org/abs/1602.01551)</sup>

## References

1. [Divisibility and Modular Arithmetic, Discrete Structures for Computing (A. Brandt, Western University)](https://www.csd.uwo.ca/~abrandt5/teaching/DiscreteStructures/Chapter4/div-mod.html)
2. [Shaohua Zhang, Euclid's Number-Theoretical Work, arXiv:0902.2465](https://arxiv.org/abs/0902.2465)
3. [The Euclidean Algorithm, Emory University Math 125 materials](https://math.oxford.emory.edu/site/math125/euclideanAlgorithm/)
4. [Modular Arithmetic: Remainders, Rules & Applications, Yijian Suan guide](https://www.yijiansuan.com/en/guide/modular-guide)
5. [21-110: The extended Euclidean algorithm, Carnegie Mellon University](https://www.math.cmu.edu/~bkell/21110-2010s/extended-euclidean.html)
6. [UMD 403: The division algorithm with remainder, University of Maryland](https://www.math.umd.edu/~pbrosnan/notes/ugalg/sect0005.html)
7. [NumberTheory, James Aspnes, Yale University](https://cs.yale.edu/homes/aspnes/pinewiki/NumberTheory.html)
8. [Modular arithmetic explained: basics, applications and examples, Casio Education](https://education.casio.co.uk/article-modular-arithmetic-explained-basics-applications-and-examples/)
9. [Modular Arithmetic, Cornell CS discrete mathematics notes](https://www.cs.cornell.edu/~rafael/discmath.pdf)
10. [NTIC: The Division Algorithm, Gordon College](https://www.math.gordon.edu/~kcrisman/mat338/section-5.html)
11. [Chapter 15. Expressions, Java Language Specification, JDK 27](https://download.java.net/java/early_access/jdk27/docs/specs/jls/jls-15.html)
12. [On The Euclidean Algorithm: Rhythm Without Recursion, arXiv:2206.12421](https://arxiv.org/abs/2206.12421)
13. [New Residue Arithmetic Based Barrett Algorithms, Part I, arXiv:1602.01551](https://arxiv.org/abs/1602.01551)

---
*Topic: Encyclopedia › Physical world and mathematics › Mathematics and statistics › Numbers and algebra › Number theory › Elementary number theory › Congruences and modular arithmetic*

*Initially written Sep 17, 2026 · Reviewed: Sep 30, 2026; Oct 15, 2026 · Edited: Sep 30, 2026; Oct 15, 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