Modular Arithmetic Basics in DSA Python - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is modular arithmetic?

Modular arithmetic is a way of doing math where numbers wrap around after reaching a certain value called the modulus. It's like a clock where after 12, it goes back to 1.

beginner

What does the expression a % m mean?

It means the remainder when number a is divided by m. For example, 7 % 3 = 1 because 7 divided by 3 leaves remainder 1.

beginner

How do addition and multiplication work in modular arithmetic?

You add or multiply numbers normally, then take the remainder after dividing by the modulus. For example, if modulus is 5, then (3 + 4) % 5 = 2 and (3 * 4) % 5 = 2.

intermediate

Why is modular arithmetic useful in programming?

It helps keep numbers within a fixed range, avoids overflow, and is used in hashing, cryptography, and algorithms that need wrap-around behavior.

intermediate

What is the result of (a - b) % m if a < b?

Even if a is less than b, (a - b) % m gives a non-negative remainder by wrapping around. For example, with m=5, (2 - 3) % 5 = 4.

What is the value of 10 % 4?

A 3

B 0

C 1

D 2

10 divided by 4 is 2 with remainder 2, so 10 % 4 = 2.

If modulus is 7, what is (5 + 6) % 7?

A 4

B 11

C 6

D 0

5 + 6 = 11, and 11 % 7 = 4.

Which of these is true for modular multiplication?

A (a * b) % m = a % b

B (a * b) % m = ((a % m) * (b % m)) % m

C (a * b) % m = (a % m) + (b % m)

D (a * b) % m = (a + b) % m

Modular multiplication distributes over modulus: multiply remainders then take modulus again.

What happens if you do (a - b) % m and a < b?

A Result is negative

B Result is zero

C Result wraps around to a positive remainder

D Error occurs

Modular arithmetic wraps negative results to positive by adding modulus.

Why is modular arithmetic like a clock?

A Because numbers reset after reaching modulus

B Because it counts hours only

C Because it uses 24-hour format

D Because it only works with time

Like a clock resets after 12, modular arithmetic resets numbers after modulus.

Explain modular arithmetic and how addition works with an example.

Think about how a clock resets after 12 hours.

Describe why modular arithmetic is important in programming and give two examples of its use.

Consider situations where numbers must wrap around or stay small.

Practice

1. What is the result of 17 % 5 in modular arithmetic?

easy

A. 3

B. 2

C. 5

D. 12

Solution

1. Step 1: Understand the modulo operation

   The modulo operator (%) gives the remainder when the first number is divided by the second.

2. Step 2: Calculate 17 divided by 5

   17 divided by 5 is 3 with a remainder of 2.

3. Final Answer:

   2 -> Option B

4. Quick Check:

   17 % 5 = 2 [OK]

Hint: Modulo gives remainder after division [OK]

Common Mistakes:

• Confusing modulo with division
• Using subtraction instead of modulo
• Mixing up dividend and divisor

2. Which of the following is the correct syntax to compute the remainder of 25 divided by 4 in Python?

easy

A. remainder = 25 % 4

B. remainder = 25 mod 4

C. remainder = 25 // 4

D. remainder = 25 / 4

Solution

1. Step 1: Recall Python modulo operator

   In Python, the modulo operator is the percent sign (%).

2. Step 2: Check each option

   remainder = 25 % 4 uses 25 % 4 which correctly computes the remainder. remainder = 25 mod 4 uses 'mod' which is not valid syntax. remainder = 25 // 4 uses floor division (//) which gives quotient, not remainder. remainder = 25 / 4 uses normal division (/), which gives a float result.

3. Final Answer:

   remainder = 25 % 4 -> Option A

4. Quick Check:

   Use % for modulo in Python [OK]

Hint: Use % symbol for modulo in Python [OK]

Common Mistakes:

• Using 'mod' keyword
• Confusing // with %
• Using / instead of %

3. What is the output of the following Python code?

for i in range(1, 6):
    print(i % 3, end=' ')

medium

A. 0 1 2 0 1

B. 1 2 3 1 2

C. 1 2 0 1 2

D. 1 2 0 2 1

Solution

1. Step 1: Understand the loop and modulo

   The loop runs i from 1 to 5. For each i, we compute i % 3.

2. Step 2: Calculate each modulo

   1 % 3 = 1, 2 % 3 = 2, 3 % 3 = 0, 4 % 3 = 1, 5 % 3 = 2.

3. Final Answer:

   1 2 0 1 2 -> Option C

4. Quick Check:

   Modulo cycles every 3 numbers [OK]

Hint: Modulo repeats remainder pattern every divisor [OK]

Common Mistakes:

• Starting loop at 0 instead of 1
• Miscomputing modulo for 3
• Confusing modulo with division

4. Find the error in the following code snippet that tries to compute n % 4 for n = 10:

n = 10
result = n %
print(result)

medium

A. Missing operand after % operator

B. Incorrect variable name

C. Using print without parentheses

D. No error, code runs fine

Solution

1. Step 1: Analyze the modulo expression

   The line 'result = n %' is incomplete because modulo requires two operands: dividend and divisor.

2. Step 2: Identify syntax error

   Without a number or variable after %, Python will raise a syntax error.

3. Final Answer:

   Missing operand after % operator -> Option A

4. Quick Check:

   Modulo needs two numbers: a % b [OK]

Hint: Modulo operator needs both numbers [OK]

Common Mistakes:

• Leaving out divisor after %
• Using print without () in Python 3
• Typos in variable names

5. You want to find the remainder when the sum of numbers from 1 to 100 is divided by 7. Which Python expression correctly computes this using modular arithmetic?

hard

A. sum(i for i in range(1, 101)) // 7

B. (sum(range(1, 101)) // 7) % 7

C. sum(i % 7 for i in range(1, 101))

D. sum(range(1, 101)) % 7

Solution

1. Step 1: Understand the problem

   We want the remainder of the sum of numbers 1 to 100 divided by 7.

2. Step 2: Evaluate each option

   sum(range(1, 101)) % 7 correctly sums all numbers then applies modulo 7. (sum(range(1, 101)) // 7) % 7 first does floor division to get quotient then % 7, which is incorrect. sum(i % 7 for i in range(1, 101)) sums remainders but does not apply modulo to the total sum, so it gives a wrong result. sum(i for i in range(1, 101)) // 7 uses floor division (//) which gives quotient, not remainder.

3. Final Answer:

   sum(range(1, 101)) % 7 -> Option D

4. Quick Check:

   Sum then modulo gives remainder [OK]

Hint: Sum first, then modulo for remainder [OK]

Common Mistakes:

• Applying modulo inside sum without final modulo
• Using floor division instead of modulo
• Using floor division before modulo