Modular Arithmetic Basics in DSA C - Execution Trace

Concept Flow - Modular Arithmetic Basics

Start with number a

↓

Choose modulus m

↓

Calculate remainder r = a % m

↓

Result is r, where 0 <= r < m

↓

Use r for further calculations or comparisons

Start with a number and a modulus, then find the remainder when the number is divided by the modulus. This remainder is the modular result used in calculations.

Execution Sample

DSA C

int a = 17;
int m = 5;
int r = a % m;
printf("%d %% %d = %d", a, m, r);

Calculate the remainder when 17 is divided by 5 using the modulus operator.

Execution Table

Step	Operation	Values	Calculation	Result	Explanation
1	Start	a=17, m=5	N/A	N/A	Initial values set
2	Calculate remainder	17 % 5	17 divided by 5 gives quotient 3 and remainder 2	2	Remainder is 2, so 17 mod 5 = 2
3	Output	Print result	N/A	17 % 5 = 2	Print the modular arithmetic result
4	End	N/A	N/A	N/A	Calculation complete

💡 Calculation stops after printing the remainder which is the modular result.

Variable Tracker

Variable	Start	After Step 2	Final
a	17	17	17
m	5	5	5
r	undefined	2	2

Key Moments - 3 Insights

Why is the result always less than the modulus m?

Because the remainder from division (a % m) is always between 0 and m-1, as shown in execution_table step 2 where remainder 2 < 5.

What happens if a is smaller than m?

If a < m, then a % m equals a itself, since a divided by m gives quotient 0 and remainder a. This is implied by the modulus definition and can be tested by changing a in the code.

Why do we use modular arithmetic in programming?

Modular arithmetic helps keep numbers within a fixed range, useful for cyclic structures like clocks or hashing. The execution_table shows how the remainder keeps the result bounded.

Visual Quiz - 3 Questions

Look at the execution_table, what is the value of r after step 2?

A 5

B 3

C 2

D 17

💡 Hint

Check the 'Result' column in row for step 2 in execution_table.

At which step does the program print the modular arithmetic result?

A Step 3

B Step 1

C Step 2

D Step 4

💡 Hint

Look for the step with 'Output' operation in execution_table.

If a was 4 and m was 5, what would be the value of r?

A 0

B 4

C 1

D 5

💡 Hint

Refer to key_moments explanation about a < m and remainder equals a.

Concept Snapshot

Modular Arithmetic Basics:
- Use '%' operator to find remainder of division.
- Result r = a % m is always 0 <= r < m.
- Useful for wrapping numbers within a range.
- Example: 17 % 5 = 2.
- Helps in cyclic calculations and hashing.

Full Transcript

Modular arithmetic means finding the remainder when one number is divided by another. We start with a number a and a modulus m. We calculate a % m, which gives the remainder r. This remainder is always between 0 and m-1. For example, 17 % 5 equals 2 because 5 goes into 17 three times with 2 left over. This remainder is useful in programming to keep numbers within a fixed range, like hours on a clock or positions in a circular list. The code example shows how to calculate and print this remainder. Key points include that the result is always less than the modulus and if the number is smaller than the modulus, the result is the number itself.

Practice

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

easy

A. 1

B. 2

C. 3

D. 0

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

   7 divided by 3 is 2 with a remainder of 1, but since 7 % 3 means remainder, it is 1.

3. Final Answer:

   1 -> Option A

4. Quick Check:

   7 % 3 = 1 [OK]

Hint: Modulo gives remainder after division [OK]

Common Mistakes:

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

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

easy

A. a mod b

B. a % b

C. mod(a, b)

D. a / b

Solution

1. Step 1: Recall C syntax for modulo

   In C, the modulo operator is represented by the percent sign '%'.

2. Step 2: Identify correct syntax

   The correct way to get remainder is a % b. Other options are invalid syntax or division.

3. Final Answer:

   a % b -> Option B

4. Quick Check:

   Modulo operator in C is % [OK]

Hint: Use % operator for modulo in C [OK]

Common Mistakes:

• Using 'mod' keyword
• Using division operator '/' instead
• Calling a function mod() which doesn't exist in C

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

#include 
int main() {
    int x = 14;
    int y = 5;
    printf("%d", (x + y) % y);
    return 0;
}

medium

A. 4

B. 0

C. 1

D. 5

Solution

1. Step 1: Calculate (x + y)

   x = 14, y = 5, so x + y = 19.

2. Step 2: Calculate (x + y) % y

   19 % 5 is the remainder when 19 is divided by 5. 5 * 3 = 15, remainder 4.

3. Final Answer:

   4 -> Option A

4. Quick Check:

   (14 + 5) % 5 = 4 [OK]

Hint: Add first, then apply modulo [OK]

Common Mistakes:

• Applying modulo before addition
• Confusing remainder with quotient
• Incorrect operator precedence

4. Identify the error in the following C code snippet that attempts to compute a % b:

int a = 10;
int b = 0;
int c = a % b;
printf("%d", c);

medium

A. Syntax error in modulo operator

B. Variable c is not declared

C. Division by zero error

D. No error, code runs fine

Solution

1. Step 1: Check divisor value

   Variable b is zero, which is the divisor in modulo operation.

2. Step 2: Understand modulo with zero divisor

   Modulo by zero is undefined and causes a runtime error (division by zero).

3. Final Answer:

   Division by zero error -> Option C

4. Quick Check:

   Modulo divisor cannot be zero [OK]

Hint: Never modulo by zero; it causes runtime error [OK]

Common Mistakes:

• Ignoring zero divisor
• Assuming modulo by zero returns zero
• Confusing syntax error with runtime error

5. Given the expression (a * b) % m, which of the following is a correct way to compute it without causing integer overflow in C when a and b are large integers?

hard

A. Use (a % b) % m

B. Use (a * b) % m directly

C. Use (a + b) % m

D. Use ((a % m) * (b % m)) % m

Solution

1. Step 1: Understand overflow risk

   Multiplying large integers a * b can overflow before modulo is applied.

2. Step 2: Apply modular multiplication property

   Using ((a % m) * (b % m)) % m keeps intermediate values smaller, preventing overflow.

3. Final Answer:

   ((a % m) * (b % m)) % m -> Option D

4. Quick Check:

   Modular multiplication reduces overflow risk [OK]

Hint: Modulo each operand before multiply to avoid overflow [OK]

Common Mistakes:

• Multiplying before modulo causing overflow
• Using addition instead of multiplication
• Incorrect modulo order