In mathematics, modular arithmetic is a calculation system for integers, with the help of which they “flip” when a certain value is reached - the module (or the plural of them). A modern approach to this kind of science was developed by Karl Friedrich Gauss in his book Disquisitiones Arithmeticae, published in 1801. This method is very popular with computer scientists, since it is very interesting and opens up certain new possibilities in operations with numbers.
Essence
Since the number of hours starts anew after it reaches 12, it is arithmetic modulo 12. According to the definition below, 12 corresponds to not only 12, but also 0, so you can also name the time called “12:00”. "0:00". After all, 12 coincides with 0 modulo 12.
Modular arithmetic can be mathematically processed by introducing a congruent relation to integers, which is compatible with operations on integers: addition, subtraction and multiplication. For a positive integer n, two numbers a and b are called congruent modulo n if their difference a - b is a multiple of n (that is, if there is an integer k such that a - b = kn).
Deductions
In theoretical mathematics, modular arithmetic is one of the foundations of number theory, affecting almost all aspects of its study, and is also widely used in the theory of groups, rings, knots, and abstract algebra. In the field of applied mathematics, it is used in computer algebra, cryptography, computer science, chemistry, the visual and musical arts.
Practice
A very practical application is the calculation of checksums in the identifiers of serial numbers. For example, some generally accepted book standards use arithmetic modulo 11 (if released before January 1, 2007) or modulo 10 (if issued before or after January 1, 2007). Similarly, for example, in International Bank Account Numbers (IBAN). It uses arithmetic modulo 97 to detect user input errors in bank account numbers.
In chemistry, the last digit of a CAS registration number (a unique identification number for each chemical compound) is a check digit. It is calculated by taking the last digit from the first two parts of the CAS registration number, multiplied by 1, the previous digit 2 times, the previous digit 3 times, etc., adding all this and calculating the sum modulo 10.
What is cryptography? The fact is that it has a very strong connection with the topic under discussion. In cryptography, the laws of modular arithmetic directly underlie public-key systems such as RSA and Diffie-Hellman. Here it provides the finite fields that underlie elliptic curves. Used in a variety of symmetric key algorithms, including Advanced Encryption Standard (AES), the International Data Encryption Algorithm, and RC4.
Application
This method is used in areas where you need to read numbers. It was developed by mathematicians, and everyone uses it, especially computer scientists. This is well described in books like Modular Arithmetic for Dummies. However, a number of experts recommend that you do not take such literature seriously.
In computer science, modular arithmetic is often used in bitwise and other operations, including cyclic data structures of fixed width. It is very much used by analysts. Modulo operation is implemented in many programming languages ​​and calculators. In this case, it is one example of such an application. Comparison modulo, division with remainder and other tricks are also used in programming.
In music, arithmetic modulo 12 is used when considering a system of equal temperament of twelve tones, in which the octave and enharmonics are equivalent. In other words, tonality in a ratio of 1-2 or 2-1 is equivalent. In music and other humanitarian disciplines, arithmetic plays a rather significant role, but usually do not write about this in computer science textbooks.
Method of casting nines
The Nine cast method offers a quick check of manual decimal arithmetic calculations. It is based on modular arithmetic modulo 9 and, in particular, on the decisive property 10 10 1.
there are other examples. Arithmetic modulo 7 is used in algorithms that determine the day of the week for a particular date. In particular, the Zeller congruence and the Doomsday algorithm make heavy use of modulo 7 arithmetic.
Other applications
Cryptography has already been said about modular arithmetic. In this area, it is simply irreplaceable. In a more general sense, modular arithmetic also finds application in disciplines such as law, economics (for example, game theory) and other areas of the social sciences. In other words, where the proportional division and distribution of resources plays a major role.
Since modular arithmetic has such a wide range of applications, it is important to know how difficult it is to solve the comparison system. A linear congruence system can be solved in polynomial time in the form of a Gaussian exception. This is described in more detail by the linear congruence theorem. Algorithms, such as Montgomery reduction, also exist to allow simple arithmetic operations to be performed efficiently. For example, multiplication and exponentiation modulo n, for large numbers. It is very important to know to understand what cryptography is. After all, it just works with similar operations.
Congruence
Some operations, such as searching for a discrete logarithm or quadratic congruence, seem as complex as integer factorization, and thus are the starting point for cryptographic algorithms and encryption. These problems may be NP-intermediate.
Examples
Below are three fairly fast C functions - two for performing modular multiplication and one for raising to modular numbers for unsigned integers not exceeding 63 bits, without overflow of transient operations.
Soon after the detection of integers (1, 2, 3, 4, 5 ...), it becomes obvious that they are divided into two groups:
- Even: divisible by 2 (0, 2, 4, 6 ..).
- Odd: not divisible by 2 (1, 3, 5, 7 ...).
Why is this distinction important? This is the beginning of abstraction. We notice the properties of a number (for example, even or odd), and not just the number itself (“37”).
This allows us to study mathematics at a deeper level and find relationships between types of numbers, rather than specific ones.
Number Properties
Being a "triple" is just another property of the number. Perhaps not as immediately useful as even / odd, but it is. We can create rules like “thirteen x three veins = thirteen” and so on. But it is crazy. We cannot make new words all the time.
The modulo operation (abbreviated mod or “%” in many programming languages) is the remainder of the division. For example, “5 mod 3 = 2”, which means 2 - the remainder when you divide 5 by 3.
When converting everyday terms into math, an “even number” is where it is “0 mod 2”, that is, the remainder is 0 when divided by 2. An odd number is “1 mod 2” (has a remainder of 1).
Even and odd numbers
What is even x even x odd x odd? Well, that’s 0 x 0 x 1 x 1 = 0. In fact, you can see if an even number is multiplying anywhere, where the whole result will be zero.
The trick of modular mathematics is that we have already used it to store time - sometimes it is called "clock arithmetic."
For example: 7:00 (morning / evening - it does not matter). Where will the hour hand be in 7 hours?
Modulations
(7 + 7) mod 12 = (14) mod 12 = 2 mod 12 [2 is the remainder when 14 is divided by 12. Equation 14 mod 12 = 2 mod 12 means that 14 hours and 2 hours look the same at 12- hour watch. They are congruent, denoted by the triple equal sign: 14 ≡ 2 mod 12.
Another example: it's 8:00 a.m. Where will the big hand be in 25 hours?
Instead of adding 25 to 8, you can understand that 25 hours is simply “1 day + 1 hour”. The answer is simple. So, the hours will end 1 hour ahead - at 9:00.
(8 + 25) mod 12 ≡ (8) mod 12 + (25) mod 12 ≡ (8) mod 12 + (1) mod 12 ≡ 9 mod 12. You intuitively converted 25 to 1 and added this to 8.
Using the clock as an analogy, we can find out if the rules of modular arithmetic work, and they work.
Addition / Subtraction
Suppose two times look the same on our watch ("2:00" and "14:00"). If we add the same x hours to both, what will happen? Well, they change the same amount on a watch! 2:00 + 5 hours ≡ 14:00 + 5 hours - both will show 7:00.
What for? We can simply add 5 to the 2 residues that both have, and they advance equally. For all congruent numbers (2 and 14), addition and subtraction have the same result.
It is harder to see if the multiplication remains the same. If 14 ≡ 2 (mod 12), can we multiply both numbers and get the same result? Let's see what happens when we multiply by 3.
Well, 2:00 * 3 Ă— 6:00. But what is 14:00 * 3?
Remember, 14 = 12 + 2. So we can say
14 * 3 = (12 + 2) * 3 = (12 * 3) + (2 * 3)
The first part (12 * 3) can be ignored! An overflow of 12 hours, which carries 14, is simply repeated several times. But who cares? In any case, we ignore overflow.
Multiplication
When multiplying, only the remainder matters, that is, the same 2 hours for 14:00 and 2:00. It is intuitively clear that this is how I see that multiplication does not change the relationship with modular mathematics (you can multiply both sides of the modular relation and get the same result).
We do this intuitively, but it's nice to give him a name. You have a flight arriving at 3 p.m. He is delayed for 14 hours. What time will it land?
14 ≡ 2 mod 12. So, you should think of it as 2 hours, so the plane will land 5 hours in the morning. The solution is simple: 3 + 2 = 5 in the morning. This is a bit more complicated than a simple modulo operation, but the principle is the same.