introduction to Modulo Mathematics
All numbers are integers.
Definition: the modulo operator finds the remainder after the division of one number by another (sometimes called modulus). Given two positive numbers, A (the dividend) and p (the divisor), A modulo p (abbreviated as A mod p) is the remainder of the Euclidean division of A by p. Euclidean division is the process of division of two integers, which produces a quotient and a remainder smaller than the divisor.
A mod p = C, where A, p, and C are integers, p is the divisor, and C is the remainder. So, we can write
A = k*p + C; where is k is the quotient, also an integer. We discard k*p
For example, A=13, p = 3. If we divide 13 by 3 the remainder is 1 so C =1
13 = 4*3 + 1 we discard 4*3, the remainder is 1.
One of the ways to calculate mod would be to use the calculator as follows:
Divide A by p then discard the fraction. Save the quotient, an integer, say, k. Then calculate
C = A – k*p.
For the above example 13/3 is equal to 4.333333, then k= 4
C = 13 4*3 = 1
Excel has a built-in mod function which is written as +mod (A, p)
The function works well when the number of digits is about 14 or less. If the number changes into a decimal form, then the results will not be right.
Also, some OS such as MS-windows, have a scientific calculator that has a built-in mod function. This function is better than using Excel.
Mac users, please search a calculator for your OS.
The following are some identities you can use
Identity 1 for the sum of two integers:
(A+B) mod (p) = [A mod(p)+ B mod (p)] mod (p)
Example:
Left Hand Side (LHS): (37+41) mod (5) = 78 mod (5) = 3
Right Hand Side: [37 mod (5) +41 mod (5)] mod (5)
Substitute: 37 mod (5) = 2 and 41 mod (5) =1
RHS = [1+2] mod (5) = 3
Thus LHS = RHS
Identity 2 for the product of two integers:
(A*B) mod (p) = [ A mod (p) * B mod (p)] mod (p)
Example:
p=42;
A= 835 = 19*42+37;
B= 577 = 13*42 +31
A*B = 835*577 = 481795 = 11471*42+13
37*31 = 1147 = 27* 42 + 13
A mod p = 835 mod (42) = 37;
B mod p = 577 mod (42) = 31
LHS : (A*B) mod (p) = (835*577) mod (42) = 481795 mod (42) = 13
RHS: [835 mod (42) * 577 mod (42) ] mod (42)
(37*31) mod (42) = 1147 mod (42) = 13
LHS=RHS
The above identity can be extended to calculate A^n mod(p)
Suppose we need to calculate 57^ 11 mod (67);
LHS: Using Windows calculator 57^11 mod (67) = 38
now 57^11 would be a big number. So, we break the power 11 into say 2*5+1; then first calculate 57^2 mod (67) = 33
Now we reduced 57 ^ 11 mod (67)
to calculate [(57^2 mod (67)] ^5 mod (67) * 57 mod (67)] mod (67)
Using Windows calculator: 57^2 mod (67) = 33
RHS: [(57^2 mod (67)] ^5mod (67) * 57 mod (67)] mod (67)
= [33^5 mod (67) * 57] mod (67) {using Window calculator}
= [23 *57] mod (67)
= 1311 mod (67);
=38 :
For your understanding, you may try different combinations for 11= 3*3+2; if you use excel, avoid getting numbers in e format. If you get in e format, then the calculation would be wrong. Use Windows calculator or Mac equivalent
For your response:
Choose two 4-digit numbers A and B and p two-digit divisor and calculate
A mod(p) and B mod(p)
(A+B) mod (p) Calculate directly and using the identity and to prove the identity calculate the mod value of the sum: LHS = RHS
3 (A*B) mod(p)= [Amod(p)*Bmod(p)] mod(p) to prove the identity calculate the mod value of the product LHS = RHS
4. A^5 mod (p) using 5=2+2+1 or any other combination such as 4+1.
To prove identities, you need to calculate the left-hand side and the right-hand side independently. Please let me know if you have any questions or need more clarification
Please do not choose A or B such that A mod (p) is equal to 0; e.g.
8888 mod (88) = 0
Post your results in this forum
See attached
Due Fri Feb 7th
