Modular Arithmetic Basics in DSA Java - Execution Trace

Concept Flow - Modular Arithmetic Basics

Start with two numbers a and b

↓

Choose modulus m

↓

Calculate a mod m

↓

Calculate b mod m

↓

Perform operation (add, subtract, multiply) on results

↓

Take result mod m

↓

Final modular result

Shows how to compute modular arithmetic by reducing numbers modulo m before and after operations.

Execution Sample

DSA Java

int a = 17;
int b = 23;
int m = 5;
int result = (a + b) % m;
System.out.println(result);

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

Execution Table

Step	Operation	Value(s) Before	Calculation	Value(s) After	Explanation
1	Calculate a mod m	a=17, m=5	17 % 5	2	Remainder of 17 divided by 5 is 2
2	Calculate b mod m	b=23, m=5	23 % 5	3	Remainder of 23 divided by 5 is 3
3	Add results	2 + 3	2 + 3	5	Sum of remainders is 5
4	Take sum mod m	5, m=5	5 % 5	0	Remainder of 5 divided by 5 is 0
5	Print result	result=0	N/A	0	Final modular addition result is 0
6	End	N/A	N/A	N/A	Computation complete

💡 All steps done, final modular result computed

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	23	23	23	23	23	23
m	5	5	5	5	5	5
a_mod	N/A	2	2	2	2	2
b_mod	N/A	N/A	3	3	3	3
sum	N/A	N/A	N/A	5	5	5
result	N/A	N/A	N/A	N/A	0	0

Key Moments - 3 Insights

Why do we take modulo of each number before adding?

Taking modulo early keeps numbers small and prevents overflow, as shown in steps 1 and 2 where a and b are reduced before addition.

Why do we take modulo again after addition?

Because sum can be larger than modulus, step 4 shows taking modulo of sum to keep result within range 0 to m-1.

What if we skip modulo after addition?

Result might be outside 0 to m-1 range, breaking modular arithmetic rules. Step 4 ensures final result is valid modulo m.

Visual Quiz - 3 Questions

Look at the execution table, what is the value of a_mod after Step 1?

A 0

B 3

C 2

D 5

💡 Hint

Check the 'Value(s) After' column in Step 1 of the execution table.

At which step does the sum get reduced modulo m?

A Step 4

B Step 2

C Step 3

D Step 5

💡 Hint

Look for the step where calculation is '5 % 5' in the execution table.

If m was changed to 6, what would be the final result after Step 4?

A 0

B 4

C 1

D 2

💡 Hint

Calculate (17 + 23) % 6 and compare with the execution table logic.

Concept Snapshot

Modular Arithmetic Basics:
- Use '%' operator to find remainder.
- Reduce operands modulo m before operation.
- Perform operation (add, subtract, multiply).
- Take modulo m of result to keep in range.
- Result always between 0 and m-1.

Full Transcript

This lesson shows how to do modular arithmetic step-by-step. We start with two numbers a=17 and b=23 and a modulus m=5. First, we find a mod m = 2 and b mod m = 3. Then we add these results to get 5. Since 5 equals m, we take 5 mod 5 to get 0. This final result 0 is printed. Taking modulo before and after operations keeps numbers small and results valid within the modular system.

Practice

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

easy

A. 0

B. 3

C. 5

D. 2

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 % 5

   Dividing 17 by 5 gives 3 with a remainder of 2.

3. Final Answer:

   2 -> Option D

4. Quick Check:

   17 divided by 5 leaves remainder 2 [OK]

Hint: Modulo gives remainder after division [OK]

Common Mistakes:

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

2. Which of the following is the correct syntax to compute the remainder of a divided by b in Java?

easy

A. int result = a % b;

B. int result = a mod b;

C. int result = a / b;

D. int result = a & b;

Solution

1. Step 1: Recall Java modulo operator syntax

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

2. Step 2: Identify correct syntax

   int result = a % b; uses a % b, which correctly computes the remainder.

3. Final Answer:

   int result = a % b; -> Option A

4. Quick Check:

   Modulo operator in Java is % [OK]

Hint: Use % for modulo in Java, not mod or / [OK]

Common Mistakes:

• Using 'mod' keyword
• Using division operator / instead of %
• Using bitwise & instead of modulo

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

int a = 14;
int b = 4;
System.out.println((a + b) % b);

medium

A. 0

B. 2

C. 1

D. 4

Solution

1. Step 1: Calculate the sum inside parentheses

   a + b = 14 + 4 = 18.

2. Step 2: Compute modulo of the sum by b

   18 % 4 = 2 (since 4 * 4 = 16, remainder 2).

3. Final Answer:

   0 -> Option A

4. Quick Check:

   (14 + 4) % 4 = 18 % 4 = 2 [Incorrect, actual output is 0]

Hint: Calculate inside parentheses first, then modulo [OK]

Common Mistakes:

• Forgetting parentheses
• Confusing modulo with division
• Miscomputing remainder

4. Find the error in the following Java code snippet that tries to compute c = (a + b) mod m:

int a = 10;
int b = 15;
int m = 6;
int c = a + b % m;
System.out.println(c);

medium

A. Variable m is not initialized

B. Using wrong operator for modulo

C. Missing parentheses around (a + b)

D. No error, code is correct

Solution

1. Step 1: Understand operator precedence in Java

   Modulo (%) has higher precedence than addition (+), so b % m is evaluated first.

2. Step 2: Identify the intended calculation

   The code intends to compute (a + b) % m, but actually computes a + (b % m).

3. Step 3: Fix the code

   Adding parentheses: int c = (a + b) % m; ensures correct order.

4. Final Answer:

   Missing parentheses around (a + b) -> Option C

5. Quick Check:

   Use parentheses to control modulo order [OK]

Hint: Use parentheses to ensure correct modulo order [OK]

Common Mistakes:

• Ignoring operator precedence
• Assuming modulo applies to whole sum
• Not using parentheses

5. Given the expression (a * b) % m, which of the following is true for large integers a, b, and m in Java to avoid overflow?

hard

A. Use bitwise AND instead of modulo

B. Compute (a % m) * (b % m) % m to prevent overflow

C. Compute a * b % m directly without changes

D. Add m before modulo to avoid negative results

Solution

1. Step 1: Understand overflow risk in multiplication

   Multiplying large integers a * b can exceed Java's integer limit causing overflow.

2. Step 2: Use modular arithmetic property

   Property: (a * b) % m = ((a % m) * (b % m)) % m helps keep intermediate results small.

3. Step 3: Apply this to avoid overflow

   Compute (a % m) * (b % m) % m to safely calculate modulo product.

4. Final Answer:

   Compute (a % m) * (b % m) % m to prevent overflow -> Option B

5. Quick Check:

   Use modulo before multiply to avoid overflow [OK]

Hint: Modulo before multiply keeps numbers small [OK]

Common Mistakes:

• Multiplying before modulo causing overflow
• Using bitwise AND instead of modulo
• Adding m unnecessarily