Modular Arithmetic Basics in DSA Javascript - 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 results

↓

Take result mod m

↓

Final result

Start with numbers a, b and modulus m. Find remainders of a and b by m, perform operation, then take remainder again.

Execution Sample

DSA Javascript

const a = 17;
const b = 5;
const m = 6;
const result = ((a % m) + (b % m)) % m;
console.log(result);

Adds 17 and 5 under modulus 6 and prints the result.

Execution Table

Step	Operation	Value/Expression	Result	Explanation
1	Calculate a mod m	17 % 6	5	17 divided by 6 leaves remainder 5
2	Calculate b mod m	5 % 6	5	5 divided by 6 leaves remainder 5
3	Add remainders	5 + 5	10	Sum of remainders before mod
4	Take mod of sum	10 % 6	4	10 divided by 6 leaves remainder 4
5	Print result	console.log(4)	4	Final modular addition result

💡 All steps done, final modular addition result is 4

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	6	6	6	6	6	6
a_mod	undefined	5	5	5	5	5
b_mod	undefined	undefined	5	5	5	5
sum	undefined	undefined	undefined	10	10	10
result	undefined	undefined	undefined	undefined	4	4

Key Moments - 3 Insights

Why do we take modulus after adding the remainders instead of before?

Because adding remainders can exceed the modulus, so we take modulus again to keep the result within range, as shown in step 4 of the execution_table.

Why is 5 % 6 equal to 5 and not 0?

Because 5 is less than 6, so the remainder when dividing 5 by 6 is 5 itself, as shown in step 2 of the execution_table.

Can modulus be zero or negative?

No, modulus must be a positive number greater than zero to define a valid remainder operation, as stated in the concept_flow.

Visual Quiz - 3 Questions

Look at the execution_table, what is the value of 'a_mod' after step 1?

A 6

B 17

C 5

D 0

💡 Hint

Check the 'Result' column in row with Step 1 in execution_table.

At which step does the sum exceed the modulus m?

A Step 3

B Step 2

C Step 4

D Step 5

💡 Hint

Look at the 'Value/Expression' and 'Result' columns in execution_table rows.

If we changed m to 12, what would be the final result after step 4?

A 4

B 10

C 5

D 0

💡 Hint

Calculate (17 % 12) + (5 % 12) then take % 12, refer to variable_tracker for values.

Concept Snapshot

Modular Arithmetic Basics:
- Use '%' operator to find remainder.
- Compute a % m and b % m first.
- Perform operation (add, subtract, multiply) on remainders.
- Take modulus again to keep result in range.
- Modulus m must be > 0.
- Example: ((a % m) + (b % m)) % m

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 positive modulus m. We find the remainder of a divided by m, called a_mod, and the remainder of b divided by m, called b_mod. Then we add these remainders. Since the sum can be bigger than m, we take the remainder of the sum divided by m again. This final remainder is the modular addition result. For example, with a=17, b=5, and m=6, a_mod is 5, b_mod is 5, sum is 10, and final result is 4. This keeps numbers within the range 0 to m-1. Modulus must be positive. This method works similarly for subtraction and multiplication.

Practice

1. What is the result of 7 % 3 in modular arithmetic?

easy

A. 2

B. 3

C. 1

D. 0

Solution

1. Step 1: Understand the modulus operation

   The modulus operator (%) gives the remainder after division of the first number by the second.

2. Step 2: Calculate 7 divided by 3

   7 divided by 3 is 2 with a remainder of 1.

3. Final Answer:

   1 -> Option C

4. Quick Check:

   7 % 3 = 1 [OK]

Hint: Modulus gives remainder after division [OK]

Common Mistakes:

• Confusing modulus with division
• Using 3 instead of remainder
• Thinking modulus returns quotient

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

easy

A. a % b

B. a mod b

C. mod(a, b)

D. a // b

Solution

1. Step 1: Recall JavaScript modulus syntax

   In JavaScript, the modulus operator is the percent sign (%) placed between two numbers or variables.

2. Step 2: Identify correct syntax

   Only a % b correctly computes the remainder of a divided by b.

3. Final Answer:

   a % b -> Option A

4. Quick Check:

   Use % for modulus in JavaScript [OK]

Hint: Use % operator for modulus in JavaScript [OK]

Common Mistakes:

• Using 'mod' keyword
• Using integer division operator //
• Calling a non-existent mod() function

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

const x = 15;
const y = 4;
console.log(x % y);

medium

A. 4

B. 3

C. 0

D. 1

Solution

1. Step 1: Calculate 15 divided by 4

   15 divided by 4 is 3 with a remainder of 3.

2. Step 2: Apply modulus operator

   The expression 15 % 4 returns the remainder, which is 3.

3. Final Answer:

   3 -> Option B

4. Quick Check:

   15 % 4 = 3 [OK]

Hint: Modulus returns remainder after division [OK]

Common Mistakes:

• Confusing remainder with quotient
• Expecting 4 instead of remainder
• Mistaking modulus for division

4. Find the error in the following code snippet that tries to compute the modulus of two numbers:

let a = 10;
let b = 3;
let result = a % b();
console.log(result);

medium

A. Missing semicolon after console.log

B. Modulus operator should be replaced with division

C. Variables a and b should be strings

D. Using parentheses after b causes an error

Solution

1. Step 1: Analyze the modulus expression

   The code uses a % b(), which treats b as a function call, but b is a number, not a function.

2. Step 2: Identify the error

   Parentheses after b cause a runtime error because numbers cannot be called like functions.

3. Final Answer:

   Using parentheses after b causes an error -> Option D

4. Quick Check:

   Variables are not functions, so no () after b [OK]

Hint: Don't add () after variables unless they are functions [OK]

Common Mistakes:

• Adding () after number variables
• Confusing modulus with division
• Ignoring runtime errors

5. You want to find the remainder when the sum of two numbers a = 123456789 and b = 987654321 is divided by 1000. Which expression correctly computes this using modular arithmetic properties?

hard

A. ((a % 1000) + (b % 1000)) % 1000

B. (a % 1000) + (b % 1000)

C. a + b % 1000

D. a % (b % 1000)

Solution

1. Step 1: Recall modular addition property

   The remainder of a sum modulo m equals the sum of remainders modulo m: (a + b) % m = ((a % m) + (b % m)) % m.

2. Step 2: Apply property to given numbers

   Compute (a % 1000) and (b % 1000), add them, then take modulo 1000 again to get correct remainder.

3. Final Answer:

   ((a % 1000) + (b % 1000)) % 1000 -> Option A

4. Quick Check:

   Use modular addition: ((a%m)+(b%m))%m [OK]

Hint: Add remainders then mod again for sum modulus [OK]

Common Mistakes:

• Skipping final modulus after addition
• Adding without modulus
• Using wrong modulus order