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