Modular Arithmetic- Concept Of Modulo Arithmetic
Modular Arithmetic- Concept Of Modulo Arithmetic
Introduction to Modular Math
When we divide two integers we will obtain an equation that appears like the following:
A/B = Q remainder R
A is the dividend
B is the divisor
Q is the quotient
R is the remainder
Every so often, we are only interested in what the remainder is when we divide A by B.
For these cases there is an operator known as modulo operator written as mod for short.
Making use of the same A, B, Q, and R as above, we would get: A mod B = R
We would say this as A modulo B is congruent to R, Where B is known as the modulus.
For instance:
6 + 4 = k(mod7),
3 x 5 = b(mod6),
m = 2(mod 3), e
13/5 = 2 reminder 3, 13 Mod 5 = 3
Envision modulus with clocks
Take not of what takes place when we increase numbers by one and then divide them by 3.
0/3 = 0 remainder 0, 1/3 = 0 remainder 1, 2/3 = 0 remainder 2, 3/3 = 1 remainder 0, 4/3 = 1 remainder 1, 5/3 = 1 remainder 2, 6/3 = 2 remainder 0
The remainders begin with 0 and increases by 1 every time, till the number reaches one less than the number we are dividing by. After that, the succession repeats.
By observing this, we can see the modulo operator by making use of circles.
We write 0 at the peak of a circle and continue clockwise writing integers 1, 2, ... up to one less than the modulus.
For instance, a clock with the 12 substituted by a 0 would be the circle for a modulus of 12.
To obtain the result of A mod B we can follow the steps below:
1. Build this clock for size B
2. Begin at 0 and move around the clock A steps
3. Anytime we land is our solution.
If the number is positive we step clockwise, if it's negative we step counter-clockwise.
Examples
8 mod 4 = ?
With a modulus of 4 we make a clock with numbers 0, 1, 2, 3. We begin from 0 and go through 8 numbers in a clockwise direction 1, 2, 3, 0, 1, 2, 3, 0.
We ended up at 0 so 8 mod 4 = 0.
7 mod 2 = ?
With a modulus of 2 we make a clock with numbers 0, 1. We begin from 0 and move through 7 numbers in a clockwise direction 1, 0, 1, 0, 1, 0, 1.
We end up at 1 so 7 mod 2 = 1.
-5 mod 3 = ?
With a modulus of 3, we make a clock with numbers 0, 1, 2. We begin at 0 and move through 5 numbers in counter-clockwise direction (5 is negative) 2, 1, 0, 2, 1.
We will end up at 1 so -5 mod 3 = 1.
As a Conclusion:
If we have A mod B and we increase A by a multiple of B, we will end up in the same spot, i.e.
A mod B = (A + K . B) mod } B for any integer K .
For instance:
3 mod 10 = 3, 13 mod 10 = 3, 23 mod 10 = 3, 33 mod 10 = 3
Important Notes
mod in programming languages and calculators
-5 % 3 = -2.
Congruence Modulo
You may come across an expression like:
A ≡ B mod C
This says that A is congruent to B modulo C. It is related to the expressions we used here, but not really the same.
An Introductory Example
Everyone is aware that set of integers can be broken up into the following two categories:
the even numbers (..., –6, –4, –2, 0, 2, 4, 6,...); and
the odd numbers (..., –5, –3, –1, 1, 3, 5,...).
There are some generalizations we can make about the arithmetic of numbers depending on which of these two classes they are from. For instance, we know that the sum of two even numbers is even. The sum of an even number and an odd number is odd. The sum of two odd numbers is even. The product of two even numbers is even and so on.
Modular arithmetic allows us to mention these results quite accurately, and it as well makes available a conducive language for similar but somewhat more complex statements. In the above example, our modulus is the number 2. The modulus can be thought of as the number of classes that we have broken the integers up into. It is as well the difference between any two "consecutive" numbers in a given category.
Now, we denote each of our two categories by one symbol. We allow the symbol "0" to stand for "the category of all even numbers" and the symbol "1" to stand for "the category of all odd numbers". There is no major reason why we have selected the symbols 0 and 1; we could have chosen 2 and 1, or –32 and 177, but 0 and 1 are the conservative choices.
The statement "the sum of two even numbers is even" can be expressed in the following way: 0 + 0 ≡ 0 mod 2.
At this point, the "≡" symbol is not equality but congruence symbol, and the "mod 2" just represents modulus 2. The above statement is read as "Zero plus zero is congruent to zero, modulo two." The statement "the sum of an even number and an odd number is odd" is denoted by
0 + 1 ≡ 1 mod 2.
Those examples are very natural enough but we don’t write "the sum of two odd numbers is even". It is written in this way with an initially weird looking expression.
1 + 1 ≡ 0 mod 2.
At this point the symbols "≡" and "mod 2" are rapidly very significant. We have related statements for multiplication:
0 × 0 ≡ 0 mod 2,
0 × 1 ≡ 0 mod 2,
1 × 1 ≡ 1 mod 2.
In a sense, we have produced a number system with addition and multiplication but in which the only numbers that are in existence are 0 and 1. You may ask the use of this. Well, our number system is the system of integers modulo 2, and due to the preceding six properties, any arithmetic done in the integers translates to arithmetic done in the integers modulo 2. This means that if we take any equality that involves addition and multiplication of integers, for example:
12 × 43 + 65 × 78 = 5586,
then reducing each one of the integer modulo 2. That is replacing every integer by its class "representative" 0 or 1), then we will get a valid congruence. The example above is reduced to
0 × 1 + 1 × 0 ≡ 0 mod 2,
or 0 + 0 ≡ 0 mod 2.
More practical applications of reduction modulo 2 are present in solving equations. Suppose we want to know the integers that might solve the equation:
3a – 3 = 12
Of course, we can solve for a, but if we didn't require to know what a is precisely and only cared about, for example, whether it was even or odd, we could carry out the following. Reducing modulo 2 gives the congruence
1a + 1 ≡ 0 mod 2,
or
a ≡ –1 ≡ 1 mod 2,
Therefore, any integer a, satisfying the equation 3a – 3 = 12 ought to be odd.
Since any integer solution of an equation reduces to a solution modulo 2, it then means that if there is no solution modulo 2, there is no solution in integers. For instance, suppose that a is an integer solution to
2a – 3 = 12,
which reduces to
0 • a + 1 ≡ 0 mod 2,
or 1 ≡ 0 mod 2. This is in disagreement because 0 and 1 are different numbers modulo 2 (there is no even number which is an odd number, and vice versa). Thus, the above congruence has no solution, therefore, a couldn't have been an integer. This shows that the equation 2a – 3 = 12 do not have any integer solution.
Less insignificantly, suppose the system of equations
6a – 5b = 4,
2a + 3b = 3.
Modulo 2, these equations reduce to
0 + 1b ≡ 0 mod 2,
0 + 1b ≡ 1 mod 2.
This means that b is both even and odd, which is as well I disagreement. Thus, we are aware that the original system of equations possesses no integer solutions, and to prove this, we didn't even require to know anything about a.
As shown by the examples above, one of the powers of modular arithmetic is the capacity to show, frequently very simply, that a few specific equations and systems of equations possess no integer solutions. Without modular arithmetic, we would need to find all of the solutions and then see if any turned out to be integers.
Definition and Further Examples
There is nothing special about the number 2. Any integer (except 0) will work for the modulus m. We at this point provide the mathematical definition of congruence.
Definition
Let m ≠ 0 be an integer. We say that two integers a and b are congruent modulo m if there is an integer k in such a way that a – b = km, and in this case we write
a ≡ b mod m.
Observe that the condition "a – b = km for a few integer k" is equivalent to the condition "m divides a – b".
In the section above we made use of the modulus m = 2. Even though we wrote congruences with the use of just 0 and 1, in reality any integers are valid. Modulo 2, all of the even numbers are congruent to each other since the variation of any two even numbers is divisible by 2:
... ≡ –6 ≡ –4 ≡ –2 ≡ 0 ≡ 2 ≡ 4 ≡ 6 ≡ ... mod 2.
Again, every odd number is congruent to every other odd number modulo 2 since the variation of any two odd numbers is even:
... ≡ –5 ≡ –3 ≡ –1 ≡ 1 ≡ 3 ≡ 5 ≡ ... mod 2.
Thus, anywhere we wrote "0" we could have written any other even number, and in the same way "1" could have been replaced by any odd number. For instance, rather than writing 0 × 1 + 1 × 0 ≡ 0 mod 2, an equally authentic statement would have been
10 × (–13) + 27 × 6 ≡ –122 mod 2.
No comments
Post a Comment