Modular Arithmetic Basics in DSA C - Build from Scratch

Modular Arithmetic Basics

📖 Scenario: You are working on a simple calculator that needs to handle modular arithmetic operations. Modular arithmetic means working with remainders after division by a fixed number called the modulus.For example, if the modulus is 5, then 7 mod 5 is 2 because 7 divided by 5 leaves a remainder of 2.

🎯 Goal: Build a small program that calculates the remainder of numbers when divided by a given modulus. You will create a list of numbers, set the modulus, compute the remainders, and then print the results.

📋 What You'll Learn

Create an array of integers with exact values

Create an integer variable for the modulus

Use a loop to compute the remainder of each number when divided by the modulus

Print the remainders in order separated by spaces

💡 Why This Matters

🌍 Real World

Modular arithmetic is used in computer science for hashing, cryptography, and cyclic operations like clock arithmetic.

💼 Career

Understanding modular arithmetic helps in programming tasks involving cycles, encryption, and algorithms that require remainder calculations.

1

Create the array of numbers

Create an integer array called numbers with these exact values: 12, 25, 7, 30, 18.

DSA C

# Your code here

Hint

Use curly braces to list the numbers inside the array.

2

Set the modulus value

Create an integer variable called modulus and set it to 5.

DSA C

int numbers[] = {12, 25, 7, 30, 18};
# Your code here

Hint

Just create a normal integer variable and assign 5 to it.

3

Calculate remainders using modular arithmetic

Use a for loop with variable i from 0 to 4 to calculate the remainder of each element in numbers when divided by modulus. Store each remainder back into the numbers array at the same index.

DSA C

int numbers[] = {12, 25, 7, 30, 18};
int modulus = 5;
// Your code here

Hint

Use the % operator to get the remainder.

4

Print the remainders

Use a for loop with variable i from 0 to 4 to print each element of numbers followed by a space. Then print a newline character.

DSA C

int numbers[] = {12, 25, 7, 30, 18};
int modulus = 5;
for (int i = 0; i < 5; i++) {
    numbers[i] = numbers[i] % modulus;
}
// Your code here

Hint

Use printf("%d ", numbers[i]) inside the loop and printf("\n") after the loop.

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