system of algebraic operations defined for remainders under division by a fixed positive integer; system of arithmetic for integers, where numbers "wrap around" upon reaching a certain value—the modulus From Wikipedia, the free encyclopedia
Modular arithmetic, sometimes also called clock arithmetic, is a way of doing arithmetic with integers. Much like hours on a clock, which repeat every twelve hours, once the numbers reach a certain value, called the modulus, they go back to zero.
In general, given a modulus , we can do addition, subtraction and multiplication on the set in a way that "wrap around" . This set is sometimes represented by the symbol , and called the set of integers modulo .[1][2][3]
People talked about modular arithmetic in many ancient cultures. For instance, the Chinese remainder theorem is many centuries old. The modern notation and exact definition of modular arithmetic were first described by Carl Friedrich Gauss.[4]
Modular arithmetic can be used to show the idea of congruence. In general, given a positive integer n, two integers a and b are congruent modulo n, if they have the same remainder when both are divided by n. Congruence can be written this way:
The number n is called the modulus. Another definition of congruence, that means the same thing but is sometimes more useful, is that the two integers are congruent modulo n if the difference (a - b) is an integer multiple of n. That is, if n is a factor of (a - b), then a and b are congruent mod n.
For example:
The remainder when 32 is divided by 7 is 4, and the remainder when 11 is divided by 7 is also 4. This tells us that they are congruent—when the modulus is 7.
We can use this example with the other definition too. The difference, (a - b), is 32 - 11 = 21. This shows the two numbers are congruent, because 21 = 3 × 7 and 7 is a factor of 21.
Modular arithmetic is useful in many fields, and its applications include RSA algorithm in cryptography, primality testing in computer science, and 12-tone arithmetic in music.[5] It is often used in calculating checksums and check digits.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.