Modular Arithmetic Basics in DSA C++ - Build from Scratch

Modular Arithmetic Basics

📖 Scenario: Imagine you are working with a clock that shows numbers from 0 to 11. When the number goes beyond 11, it starts again from 0. This is an example of modular arithmetic, which is useful in many computer programs like cryptography, hashing, and cyclic data structures.

🎯 Goal: You will create a simple program to perform modular addition and multiplication using a fixed modulus. This will help you understand how numbers wrap around in modular arithmetic.

📋 What You'll Learn

Create an integer variable called modulus with the value 12.

Create two integer variables called a and b with values 7 and 10 respectively.

Calculate the modular addition of a and b using modulus and store it in mod_add.

Calculate the modular multiplication of a and b using modulus and store it in mod_mul.

Print the values of mod_add and mod_mul.

💡 Why This Matters

🌍 Real World

Modular arithmetic is used in clocks, cryptography, hashing algorithms, and cyclic data structures where numbers wrap around after reaching a limit.

💼 Career

Understanding modular arithmetic is important for software developers working in security, algorithms, and systems programming.

1

Create the modulus and numbers

Create an integer variable called modulus and set it to 12. Then create two integer variables called a and b with values 7 and 10 respectively.

DSA C++

// Your code here

Hint

Use simple integer variable declarations and assignments.

2

Calculate modular addition

Using the variables a, b, and modulus, create an integer variable called mod_add that stores the result of (a + b) modulo modulus.

DSA C++

int modulus = 12;
int a = 7;
int b = 10;
// Your code here

Hint

Use the modulo operator % to find the remainder after addition.

3

Calculate modular multiplication

Using the variables a, b, and modulus, create an integer variable called mod_mul that stores the result of (a * b) modulo modulus.

DSA C++

int modulus = 12;
int a = 7;
int b = 10;
int mod_add = (a + b) % modulus;
// Your code here

Hint

Use the modulo operator % to find the remainder after multiplication.

4

Print the modular results

Print the values of mod_add and mod_mul using std::cout. Print mod_add first, then print mod_mul on the next line.

DSA C++

int modulus = 12;
int a = 7;
int b = 10;
int mod_add = (a + b) % modulus;
int mod_mul = (a * b) % modulus;
// Your code here

Hint

Use std::cout << mod_add << std::endl; and std::cout << mod_mul << std::endl; to print the results.

Practice

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

easy

A. 5

B. 3

C. 2

D. 0

Solution

1. Step 1: Understand the modulo operation

   The modulo operator (%) gives the remainder after division of the first number by the second.

2. Step 2: Calculate 17 % 5

   Dividing 17 by 5 gives 3 with a remainder of 2.

3. Final Answer:

   2 -> Option C

4. Quick Check:

   17 divided by 5 leaves remainder 2 [OK]

Hint: Modulo gives remainder after division [OK]

Common Mistakes:

• Confusing modulo with division
• Using 5 instead of remainder
• Ignoring remainder sign

2. Which of the following is the correct syntax to compute the modulo of two integers a and b in C++?

easy

A. a // b

B. a mod b

C. mod(a, b)

D. a % b

Solution

1. Step 1: Recall C++ modulo operator syntax

   In C++, the modulo operator is represented by the percent sign (%).

2. Step 2: Identify correct syntax

   Among the options, only a % b is valid C++ syntax for modulo.

3. Final Answer:

   a % b -> Option D

4. Quick Check:

   C++ uses % for modulo [OK]

Hint: Use % operator for modulo in C++ [OK]

Common Mistakes:

• Using 'mod' keyword
• Using '//' which is floor division in some languages
• Using function call syntax incorrectly

3. What is the output of the following C++ code?

int a = 14;
int b = 4;
int c = (a + b) % 5;
std::cout << c << std::endl;

medium

A. 3

B. 4

C. 2

D. 1

Solution

1. Step 1: Calculate sum inside parentheses

   a + b = 14 + 4 = 18.

2. Step 2: Calculate modulo 5 of the sum

   18 % 5 = 3 because 5 * 3 = 15 and remainder is 3.

3. Final Answer:

   3 -> Option A

4. Quick Check:

   (14 + 4) % 5 = 18 % 5 = 3 [OK]

Hint: Add first, then modulo [OK]

Common Mistakes:

• Modulo before addition
• Wrong remainder calculation
• Confusing output with sum

4. Identify the error in the following C++ code snippet that tries to compute modulo:

int x = 10;
int y = 0;
int z = x % y;
std::cout << z << std::endl;

medium

A. Syntax error in modulo operator

B. Division by zero error

C. Variable z not declared

D. No error, code runs fine

Solution

1. Step 1: Check modulo divisor value

   The divisor y is 0, which is invalid for modulo operation.

2. Step 2: Understand runtime behavior

   Modulo by zero causes a runtime error (division by zero).

3. Final Answer:

   Division by zero error -> Option B

4. Quick Check:

   Modulo divisor cannot be zero [OK]

Hint: Modulo divisor must not be zero [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 can be very large?

hard

A. Use ((a % m) * (b % m)) % m

B. Use (a % m) * (b % m)

C. Use ((long long)a * b) % m

D. Use (a * b) % m directly

Solution

1. Step 1: Understand integer overflow risk

   Multiplying large int values a and b directly can cause undefined behavior due to overflow before % m.

2. Step 2: Safe computation using modulo properties

   Using ((a % m) * (b % m)) % m ensures intermediate values stay within range and prevents overflow.

3. Step 3: Why others fail

   ((long long)a * b) % m may still overflow if b is large and not casted. (a % m) * (b % m) misses final modulo. (a * b) % m overflows.

4. Final Answer:

   ((a % m) * (b % m)) % m -> Option A

5. Quick Check:

   Modulo before multiply and after prevents overflow [OK]

Hint: Apply modulo before and after multiplication to avoid overflow [OK]

Common Mistakes:

• Modulo before multiply without final modulo
• Missing final modulo
• Direct multiplication without modulo