Modular arithmetic
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 [math]\displaystyle{ n }[/math], we can do addition, subtraction and multiplication on the set [math]\displaystyle{ \{ 0, 1, \ldots, n-1\} }[/math] in a way that "wrap around" [math]\displaystyle{ n }[/math]. This set is sometimes represented by the symbol [math]\displaystyle{ \mathbb{Z}_n }[/math], and called the set of integers modulo [math]\displaystyle{ n }[/math].[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]
Congruence
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:
- [math]\displaystyle{ a \equiv b \pmod n\, }[/math]
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:
- [math]\displaystyle{ 32 \equiv 11 \pmod 7,\, }[/math]
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.
Uses
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.
Related pages
References
- ↑ "Comprehensive List of Algebra Symbols". Math Vault. 2020-03-25. Retrieved 2020-08-12.
- ↑ Weisstein, Eric W. "Modular Arithmetic". mathworld.wolfram.com. Retrieved 2020-08-12.
- ↑ "2.3: Integers Modulo n". Mathematics LibreTexts. 2013-11-16. Retrieved 2020-08-12.
- ↑ Richard Taylor (2012). "Modular Arithmetic: Driven by Inherent Beauty and Human Curiosity". Institute for Advanced Study. Retrieved 7 March 2013.
- ↑ AsKew, A.; Kennedy, K.; Klima, V. (2018-05-28). "Modular Arithmetic and Microtonal Music Theory". PRIMUS. 28 (5): 458–471. doi:10.1080/10511970.2017.1388314. ISSN 1051-1970. S2CID 125451485.