Modular Arithmetic Basics in DSA Python - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Modular Addition

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

DSA Python

a = 17
b = 23
mod = 10
result = (a + b) % mod
print(result)

A 0

B 10

C 1

D 9

💡 Hint

Add the numbers first, then find the remainder when divided by 10.

Adding 17 + 23 gives 40. Taking 40 modulo 10 means finding the remainder when 40 is divided by 10, which is 0.

❓ Predict Output

intermediate

Modular Multiplication Result

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

DSA Python

x = 7
 y = 5
 mod = 12
 product = (x * y) % mod
 print(product)

A 11

B 35

C 7

D 1

💡 Hint

Multiply first, then take remainder with 12.

7 times 5 is 35. 35 modulo 12 is 11 because 12 * 2 = 24 and 35 - 24 = 11.

🧠 Conceptual

advanced

Understanding Modular Inverse

Which of the following statements correctly describes the modular inverse of a number 'a' modulo 'm'?

A A number 'x' such that (a * x) % m = 0

B A number 'x' such that (a + x) % m = 0

C A number 'x' such that (a - x) % m = 1

D A number 'x' such that (a * x) % m = 1

💡 Hint

Think about what multiplying by the inverse should do under modulo.

The modular inverse of 'a' modulo 'm' is a number 'x' that when multiplied by 'a' gives 1 modulo 'm'. This means (a * x) % m = 1.

❓ Predict Output

advanced

Output of Modular Exponentiation

What is the output of this code that calculates modular exponentiation?

DSA Python

base = 4
exponent = 13
mod = 497
result = pow(base, exponent, mod)
print(result)

A 0

B 1

C 445

D 256

💡 Hint

Use Python's built-in pow with three arguments for efficient modular exponentiation.

Using pow(4, 13, 497) computes (4^13) mod 497 efficiently, which equals 445.

🔧 Debug

expert

Identify the Error in Modular Division Code

What error will this code raise when trying to perform modular division?

DSA Python

a = 10
b = 3
mod = 7
result = (a // b) % mod
print(result)

A SyntaxError

B Wrong output due to integer division instead of modular inverse

C TypeError

D ZeroDivisionError

💡 Hint

Modular division requires multiplying by modular inverse, not integer division.

The code uses integer division (//) which does not work for modular division. It will produce a wrong output, not an error.

Practice

1. What is the result of 17 % 5 in modular arithmetic?

easy

A. 3

B. 2

C. 5

D. 12

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 17 divided by 5

   17 divided by 5 is 3 with a remainder of 2.

3. Final Answer:

   2 -> Option B

4. Quick Check:

   17 % 5 = 2 [OK]

Hint: Modulo gives remainder after division [OK]

Common Mistakes:

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

2. Which of the following is the correct syntax to compute the remainder of 25 divided by 4 in Python?

easy

A. remainder = 25 % 4

B. remainder = 25 mod 4

C. remainder = 25 // 4

D. remainder = 25 / 4

Solution

1. Step 1: Recall Python modulo operator

   In Python, the modulo operator is the percent sign (%).

2. Step 2: Check each option

   remainder = 25 % 4 uses 25 % 4 which correctly computes the remainder. remainder = 25 mod 4 uses 'mod' which is not valid syntax. remainder = 25 // 4 uses floor division (//) which gives quotient, not remainder. remainder = 25 / 4 uses normal division (/), which gives a float result.

3. Final Answer:

   remainder = 25 % 4 -> Option A

4. Quick Check:

   Use % for modulo in Python [OK]

Hint: Use % symbol for modulo in Python [OK]

Common Mistakes:

• Using 'mod' keyword
• Confusing // with %
• Using / instead of %

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

for i in range(1, 6):
    print(i % 3, end=' ')

medium

A. 0 1 2 0 1

B. 1 2 3 1 2

C. 1 2 0 1 2

D. 1 2 0 2 1

Solution

1. Step 1: Understand the loop and modulo

   The loop runs i from 1 to 5. For each i, we compute i % 3.

2. Step 2: Calculate each modulo

   1 % 3 = 1, 2 % 3 = 2, 3 % 3 = 0, 4 % 3 = 1, 5 % 3 = 2.

3. Final Answer:

   1 2 0 1 2 -> Option C

4. Quick Check:

   Modulo cycles every 3 numbers [OK]

Hint: Modulo repeats remainder pattern every divisor [OK]

Common Mistakes:

• Starting loop at 0 instead of 1
• Miscomputing modulo for 3
• Confusing modulo with division

4. Find the error in the following code snippet that tries to compute n % 4 for n = 10:

n = 10
result = n %
print(result)

medium

A. Missing operand after % operator

B. Incorrect variable name

C. Using print without parentheses

D. No error, code runs fine

Solution

1. Step 1: Analyze the modulo expression

   The line 'result = n %' is incomplete because modulo requires two operands: dividend and divisor.

2. Step 2: Identify syntax error

   Without a number or variable after %, Python will raise a syntax error.

3. Final Answer:

   Missing operand after % operator -> Option A

4. Quick Check:

   Modulo needs two numbers: a % b [OK]

Hint: Modulo operator needs both numbers [OK]

Common Mistakes:

• Leaving out divisor after %
• Using print without () in Python 3
• Typos in variable names

5. You want to find the remainder when the sum of numbers from 1 to 100 is divided by 7. Which Python expression correctly computes this using modular arithmetic?

hard

A. sum(i for i in range(1, 101)) // 7

B. (sum(range(1, 101)) // 7) % 7

C. sum(i % 7 for i in range(1, 101))

D. sum(range(1, 101)) % 7

Solution

1. Step 1: Understand the problem

   We want the remainder of the sum of numbers 1 to 100 divided by 7.

2. Step 2: Evaluate each option

   sum(range(1, 101)) % 7 correctly sums all numbers then applies modulo 7. (sum(range(1, 101)) // 7) % 7 first does floor division to get quotient then % 7, which is incorrect. sum(i % 7 for i in range(1, 101)) sums remainders but does not apply modulo to the total sum, so it gives a wrong result. sum(i for i in range(1, 101)) // 7 uses floor division (//) which gives quotient, not remainder.

3. Final Answer:

   sum(range(1, 101)) % 7 -> Option D

4. Quick Check:

   Sum then modulo gives remainder [OK]

Hint: Sum first, then modulo for remainder [OK]

Common Mistakes:

• Applying modulo inside sum without final modulo
• Using floor division instead of modulo
• Using floor division before modulo