Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.
Concept
Modular arithmetic
Summary
In mathematics, modular arithmetic is a system of arithmetic for integers, where numbers "wrap around" when reaching a certain value, called the modulus. The modern approach to modular arithmetic was developed by Carl Friedrich Gauss in his book Disquisitiones Arithmeticae, published in 1801.
A familiar use of modular arithmetic is in the 12-hour clock, in which the day is divided into two 12-hour periods. If the time is 7:00 now, then 8 hours later it will be 3:00. Simple addition would result in 7 + 8 = 15, but clocks "wrap around" every 12 hours. Because the hour number starts over at zero when it reaches 12, this is arithmetic modulo 12. In terms of the definition below, 15 is congruent to 3 modulo 12, so "15:00" on a 24-hour clock is displayed "3:00" on a 12-hour clock.
Given an integer n > 1, called a modulus, two integers a and b are said to be congruent modulo n, if n is a divisor of their difference (that is, if there is an integer k such that a − b = kn).
Congruence modulo n is a congruence relation, meaning that it is an equivalence relation that is compatible with the operations of addition, subtraction, and multiplication. Congruence modulo n is denoted:
The parentheses mean that (mod n) applies to the entire equation, not just to the right-hand side (here, b). This notation is not to be confused with the notation b mod n (without parentheses), which refers to the modulo operation. Indeed, b mod n denotes the unique integer a such that 0 ≤ a < n and (that is, the remainder of when divided by ).
The congruence relation may be rewritten as
explicitly showing its relationship with Euclidean division. However, the b here need not be the remainder of the division of a by n. Instead, what the statement a ≡ b (mod n) asserts is that a and b have the same remainder when divided by n. That is,
where 0 ≤ r < n is the common remainder. Subtracting these two expressions, we recover the previous relation:
by setting k = p − q.
In modulus 12, one can assert that:
because 38 − 14 = 24, which is a multiple of 12.
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.