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.