Modular Arithmetic

What is Modular Arithmetic?

In the context of our world sometimes you only care about the remainder of something, such as time. This is how Modular Arithmetic is used. For example, on the clock shown, we are using mod 12. Adding 4 hours to 9 o'clock gives 1 o'clock, since 13 is congruent to 1 mod 12.

Wikipedia Contributors. “Modular Arithmetic.” Wikipedia, 23 Apr. 2020, en.wikipedia.org/wiki/Modular_arithmetic.

Examples

Basic Modular Arithmetic

A) 7 mod 2 = 1, because 7 = 2 * 3 + 1 and 1 ≤ 2

B) 50 mod 4 = 2 because 50 = 4 * 12 + 2 and 2 ≤ 4

C) 1001 mod 25 = 1 because 1001 = 25 * 40 + 1 and 1 ≤ 25

Addition/Multiplication Modular Arithmetic

A) 11 * 5 mod 6 = 1 because 11 * 5 = 55 = 6 * 9 + 1 and 1 ≤ 6

B) 3 * 4 mod 5 = 2 because 3 * 4 = 12 = 5 * 2 + 2 and 2 ≤ 5

C) 3 + 3 mod 5 = 1 because 3 + 3 = 6 = 5 * 1 + 1 and 1 ≤ 5

Practice Problems:

Basic Modular Arithmetic:

A) What is 16 mod 3?

B) What is 27 mod 4?

C) What is 122 mod 11?

D) What is 1,001 mod 4?

E) What is 1,000,000 mod 10?

Addition/Multiplication Modular Arithmetic:

A) What is 10 + 47 mod 12?

B) What is 16 *256 mod 5?

C) What is 57 + 38 mod 17?

D) What is 2223 * 2225 mod 4?

Practice Problem Answers:

Basic Modular Arithmetic:

A) 16 mod 3 = 1 because 16 = 3 * 5 + 1 and 1 ≤ 3

B) 27 mod 4 = 3 because 27 = 4 * 6 + 3 and 3 ≤ 4

C) 122 mod 11 = 1 because 122 = 11 * 11 + 1 and 1 ≤ 11

D) 1,001 mod 4 = 1 because 1,001 = 4 * 250 + 1 and 1 ≤ 4

E) 1,000,000 mod 10 = 0 because 1,000,000 = 10 * 100,000 + 0 and 0 ≤ 10

Addition/Multiplication Modular Arithmetic:

A) 10 + 47 mod 12 = 9 because 10 + 47 = 57 = 12 * 4 + 9 and 9 ≤ 12

B) 16 * 256 mod 5 = 1 because 16 * 256 = 4096 = 5 * 819 + 1 and 1 ≤ 5

C) 57 + 38 mod 17 = 10 because 57 + 38 = 95 = 17 * 5 + 10 and 10 ≤ 17

D) 2223 * 2225 mod 4 = 3 because 2223 * 2225 = 4,946,175 = 4 * 1,236,543 + 3 and 3 ≤ 4

Practice Problem Answer Video:

IMG_1677 (1).MOV

Page updated

Report abuse