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.