Modular Arithmetic Basics in DSA C - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is modular arithmetic?

Modular arithmetic is a system of arithmetic for integers where numbers wrap around after reaching a certain value called the modulus.

beginner

What does the expression 'a % m' mean in modular arithmetic?

It means the remainder when integer 'a' is divided by the modulus 'm'. This remainder is always between 0 and m-1.

beginner

How do you add two numbers under modulus m?

Add the two numbers normally, then take the remainder when divided by m: (a + b) % m.

beginner

What is the result of (a * b) % m?

Multiply a and b normally, then take the remainder when divided by m: (a * b) % m.

intermediate

Why is modular arithmetic useful in programming?

It helps keep numbers within a fixed range, prevents overflow, and is used in hashing, cryptography, and cyclic structures.

What is the value of 17 % 5?

A 5

B 3

C 2

D 0

17 divided by 5 is 3 with remainder 2, so 17 % 5 = 2.

Which of these is true for modular addition?

A (a + b) % m = ((a % m) + (b % m)) % m

B (a + b) % m = (a + b)

C (a + b) % m = (a % b) % m

D (a + b) % m = (a % m) * (b % m)

Modular addition distributes over modulus: (a + b) % m = ((a % m) + (b % m)) % m.

What is (4 * 6) % 5?

A 2

B 4

C 3

D 1

4 * 6 = 24, 24 % 5 = 4, since 24 divided by 5 is 4 with remainder 4.

If a % m = 3 and b % m = 4, what is (a + b) % m?

A (3 + 4) % m

B 0

C Cannot determine

D 7

The sum modulo m is (3 + 4) % m. Without knowing m, we cannot simplify further.

Which of these is NOT a use of modular arithmetic?

A Cryptography

B Hashing functions

C Preventing integer overflow

D Sorting arrays

Sorting arrays does not typically use modular arithmetic.

Explain how modular addition works and why it is useful.

Think about adding two numbers and then wrapping around a fixed number.

Describe a real-life example where modular arithmetic is used.

Consider how hours reset after 12 or 24.

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