Modular Arithmetic Basics in DSA Python - Execution Trace

Concept Flow - Modular Arithmetic Basics

Start with two numbers a and b

↓

Choose modulus m > 0

↓

Calculate a mod m

↓

Calculate b mod m

↓

Perform operation (add, subtract, multiply) on (a mod m) and (b mod m)

↓

Take result mod m

↓

Final result

Start with numbers a, b and modulus m. Find a mod m and b mod m, do the operation, then mod m again to get the final result.

Execution Sample

DSA Python

a = 17
b = 5
m = 7
result = (a + b) % m
print(result)

Adds 17 and 5, then finds remainder when divided by 7.

Execution Table

Step	Operation	Value Computed	Intermediate Result	Final Result
1	Calculate a mod m	17 % 7	3	3
2	Calculate b mod m	5 % 7	5	5
3	Add (a mod m) + (b mod m)	3 + 5	8	8
4	Take (8) mod m	8 % 7	1	1
5	Print result	-	-	1

💡 Finished calculation and printed result 1

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	Final
a	17	17	17	17	17	17
b	5	5	5	5	5	5
m	7	7	7	7	7	7
a_mod	-	3	3	3	3	3
b_mod	-	-	5	5	5	5
sum_mod	-	-	-	8	8	8
result	-	-	-	-	1	1

Key Moments - 3 Insights

Why do we take mod of a and b before adding?

Taking mod of a and b first keeps numbers small and avoids overflow, as shown in steps 1 and 2 of the execution_table.

Why do we take mod again after adding?

Adding two mod values can exceed the modulus, so we take mod again to keep the result within range, as in step 4.

What if a or b is already smaller than m?

If a or b is smaller than m, mod returns the number itself, so steps 1 and 2 just confirm that.

Visual Quiz - 3 Questions

Look at the execution_table, what is the value of a mod m after step 1?

A 5

B 3

C 1

D 8

💡 Hint

Check the 'Value Computed' and 'Intermediate Result' columns in step 1.

At which step does the sum exceed the modulus m?

A Step 3

B Step 4

C Step 2

D Step 1

💡 Hint

Look at the 'Intermediate Result' column to see when the sum is 8, which is greater than m=7.

If m was 10 instead of 7, what would be the final result?

A 1

B 2

C 8

D 0

💡 Hint

Calculate (17 + 5) % 10 and compare with the final result in the execution_table.

Concept Snapshot

Modular Arithmetic Basics:
- Use modulus m > 0
- Compute a mod m and b mod m first
- Perform operation (add, subtract, multiply)
- Take mod m of the result
- Result is always between 0 and m-1

Full Transcript

Modular arithmetic means working with remainders after division by a number called modulus. We start with two numbers a and b, and a modulus m. First, we find the remainder of a divided by m, called a mod m. Then we find b mod m. Next, we add these two remainders. Since the sum might be bigger than m, we take the remainder of the sum divided by m again. This final remainder is the result. This keeps numbers small and within the range from 0 to m-1. For example, with a=17, b=5, and m=7, a mod m is 3, b mod m is 5, sum is 8, and 8 mod 7 is 1. So the final result is 1.

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