ModuloMaths

introduction to Modulo MathematicsAll 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 writeA = k*p + C; where is k is the quotient, also an integer. We discard k*pFor example, A=13, p = 3. If we divide 13 by 3 the remainder is 1 so C =113 = 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 calculateC = A – k*p.For the above example 13/3 is equal to 4.333333…, then k= 4C = 13 – 4*3 = 1Excel 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 useIdentity 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) = 3Right Hand Side: [37 mod (5) +41 mod (5)] mod (5)Substitute: 37 mod (5) = 2 and 41 mod (5) =1RHS = [1+2] mod (5) = 3Thus LHS = RHSIdentity 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 +31A*B = 835*577 = 481795 = 11471*42+1337*31 = 1147 = 27* 42 + 13A mod p = 835 mod (42) = 37;B mod p = 577 mod (42) = 31LHS : (A*B) mod (p) = (835*577) mod (42) = 481795 mod (42) = 13RHS: [835 mod (42) * 577 mod (42) ] mod (42)(37*31) mod (42) = 1147 mod (42) = 13LHS=RHSThe 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) = 38now 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) = 33Now 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) = 33RHS: [(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 equivalentFor your response:Choose two 4-digit numbers A and B and p two-digit divisor and calculate1. A mod(p) and B mod(p)2. (A+B) mod (p) Calculate directly and using the identity and to prove the identity calculate the mod value of the sum: LHS = RHS3 (A*B) mod(p)= [Amod(p)*Bmod(p)] mod(p) to prove the identity calculate the mod value of the product LHS = RHS4. 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 clarificationPlease do not choose A or B such that A mod (p) is equal to 0; e.g.8888 mod (88) = 0Post your results in this forum