Modular Arithmetic Basics in DSA C - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Modular Addition

What is the output of the following C code snippet that performs modular addition?

DSA C

int a = 17;
int b = 23;
int mod = 10;
int result = (a + b) % mod;
printf("%d\n", result);

A 1

B 0

C 10

D 9

💡 Hint

Remember that modular addition sums the numbers and then takes the remainder after division by the modulus.

The sum of 17 and 23 is 40. Taking 40 modulo 10 gives 0 because 40 is divisible by 10.

❓ Predict Output

intermediate

Modular Multiplication Result

What will be printed by this C code that calculates modular multiplication?

DSA C

int x = 7;
int y = 8;
int mod = 5;
int product = (x * y) % mod;
printf("%d\n", product);

A 2

B 6

C 0

D 1

💡 Hint

Multiply first, then take the remainder after dividing by the modulus.

7 times 8 is 56. 56 modulo 5 is 1 because 5*11=55 and 56-55=1.

🧠 Conceptual

advanced

Properties of Modular Arithmetic

Which of the following statements about modular arithmetic is FALSE?

A Modular multiplication is distributive over addition: (a * (b + c)) mod m = ((a * b) mod m + (a * c) mod m) mod m

B Modular addition is associative: (a + b) mod m = ((a mod m) + (b mod m)) mod m

C Modular subtraction always produces a positive result

D For any integer a, (a mod m) is always between 0 and m-1 inclusive

💡 Hint

Think about what happens when subtracting a larger number from a smaller one in modular arithmetic.

Modular subtraction can produce negative intermediate results before applying the modulus, so it does not always produce a positive result directly without adjustment.

❓ Predict Output

advanced

Modular Exponentiation Output

What is the output of this C code that calculates modular exponentiation using a simple loop?

DSA C

int base = 3;
int exponent = 4;
int mod = 5;
int result = 1;
for (int i = 0; i < exponent; i++) {
    result = (result * base) % mod;
}
printf("%d\n", result);

A 1

B 2

C 3

D 4

💡 Hint

Calculate 3^4 first, then take modulo 5.

3^4 = 81. 81 modulo 5 is 1 because 5*16=80 and 81-80=1. But the loop calculates modulo at each step, so let's check stepwise:

• i=0: result=1*3=3 %5=3
• i=1: result=3*3=9 %5=4
• i=2: result=4*3=12 %5=2
• i=3: result=2*3=6 %5=1

Final result is 1.

🧠 Conceptual

expert

Modular Inverse Existence

Which condition must be true for an integer 'a' to have a modular inverse modulo 'm'?

A 'a' and 'm' are coprime (their greatest common divisor is 1)

B 'a' is less than 'm'

C 'm' is a prime number

D 'a' is an even number

💡 Hint

Think about when division modulo 'm' is possible.

An integer 'a' has a modular inverse modulo 'm' only if 'a' and 'm' share no common divisors other than 1, meaning gcd(a, m) = 1.

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