Modular Arithmetic Basics in DSA Rust - Build from Scratch

Modular Arithmetic Basics

📖 Scenario: You are working with a simple calculator that uses modular arithmetic to keep numbers within a fixed range, like a clock. This helps avoid very large numbers and keeps results predictable.

🎯 Goal: Build a small Rust program that calculates the remainder when numbers are divided by a fixed modulus. You will create a list of numbers, set a modulus value, compute each number modulo the modulus, and print the results.

📋 What You'll Learn

Create a vector of integers with exact values: 15, 23, 7, 31, 10

Create a variable called modulus and set it to 12

Use a for loop with variable num to iterate over the vector and compute num % modulus

Store the results in a new vector called mod_results

Print the mod_results vector

💡 Why This Matters

🌍 Real World

Modular arithmetic is used in clocks, cryptography, hashing, and many algorithms to keep numbers within a fixed range.

💼 Career

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

1

Create the list of numbers

Create a vector called numbers with these exact integers: 15, 23, 7, 31, 10

DSA Rust

# Create a vector called numbers with the values 15, 23, 7, 31, 10
// Your code here

Hint

Use vec![...] to create a vector with the exact numbers inside square brackets.

2

Set the modulus value

Create a variable called modulus and set it to 12

DSA Rust

fn main() {
    let numbers = vec![15, 23, 7, 31, 10];
    // Create a variable called modulus and set it to 12
    // Your code here
}

Hint

Use let modulus = 12; to create the variable.

3

Calculate modular results

Create a mutable vector called mod_results. Use a for loop with variable num to iterate over numbers. Inside the loop, push num % modulus into mod_results

DSA Rust

fn main() {
    let numbers = vec![15, 23, 7, 31, 10];
    let modulus = 12;
    // Create a mutable vector mod_results
    // Use a for loop with num to iterate over numbers
    // Push num % modulus into mod_results
    // Your code here
}

Hint

Remember to declare mod_results as mutable with mut. Use for num in numbers to loop. Use push to add results.

4

Print the modular results

Print the mod_results vector using println!

DSA Rust

fn main() {
    let numbers = vec![15, 23, 7, 31, 10];
    let modulus = 12;
    let mut mod_results = Vec::new();
    for num in numbers {
        mod_results.push(num % modulus);
    }
    // Print mod_results
    // Your code here
}

Hint

Use println!("{:?}", mod_results); to print the vector in debug format.

Practice

1. What is the result of 7 % 3 in modular arithmetic?

easy

A. 2

B. 1

C. 3

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 7 modulo 3

   7 divided by 3 is 2 with a remainder of 1, so 7 % 3 = 1.

3. Final Answer:

   1 -> Option A

4. Quick Check:

   7 % 3 = 1 [OK]

Hint: Modulo gives remainder after division [OK]

Common Mistakes:

• Confusing modulo with division
• Using 3 instead of remainder
• Thinking modulo returns quotient

2. Which of the following is the correct Rust syntax to compute the remainder of 15 divided by 4?

easy

A. let result = 15 / 4;

B. let result = 15 mod 4;

C. let result = 15 % 4;

D. let result = 15 rem 4;

Solution

1. Step 1: Recall Rust modulo syntax

   In Rust, the modulo operator is the percent sign (%), not 'mod' or 'rem'.

2. Step 2: Identify correct syntax

   let result = 15 % 4; uses % correctly: let result = 15 % 4;

3. Final Answer:

   let result = 15 % 4; -> Option C

4. Quick Check:

   Rust uses % for modulo [OK]

Hint: Use % operator for modulo in Rust [OK]

Common Mistakes:

• Using 'mod' keyword incorrectly
• Using division operator instead of modulo
• Using 'rem' which is invalid syntax

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

fn main() {
    let a = 10;
    let b = 6;
    let c = (a + b) % 7;
    println!("{}", c);
}

medium

A. 4

B. 2

C. 3

D. 1

Solution

1. Step 1: Calculate sum inside parentheses

   a + b = 10 + 6 = 16.

2. Step 2: Compute modulo 7 of the sum

   16 % 7 = 2 (because 7 * 2 = 14, remainder 2).

3. Step 3: Check printed output

   The code prints the value of c, which is 2.

4. Final Answer:

   2 -> Option B

5. Quick Check:

   (10 + 6) % 7 = 2 [OK]

Hint: Calculate sum first, then modulo [OK]

Common Mistakes:

• Modulo before addition
• Wrong remainder calculation
• Confusing modulo with division

4. Identify the error in this Rust code snippet that tries to compute modulo:

fn main() {
    let x = 20;
    let y = 0;
    let z = x % y;
    println!("{}", z);
}

medium

A. Division by zero error at runtime

B. Syntax error: % operator not allowed

C. Variable y is not initialized

D. No error, code runs fine

Solution

1. Step 1: Analyze modulo operation with zero divisor

   Modulo by zero is undefined and causes a runtime error in Rust.

2. Step 2: Identify error type

   The code will compile but panic at runtime due to division by zero.

3. Final Answer:

   Division by zero error at runtime -> Option A

4. Quick Check:

   Modulo by zero causes runtime panic [OK]

Hint: Never modulo by zero; causes runtime panic [OK]

Common Mistakes:

• Thinking it's a syntax error
• Ignoring zero divisor
• Assuming code runs fine

5. You want to compute (a * b) % m for very large integers a and b in Rust without overflow. Which approach is best?

hard

A. Compute a * b first, then modulo m

B. Convert numbers to strings and then modulo

C. Use floating point multiplication and then modulo

D. Use modular multiplication: ((a % m) * (b % m)) % m

Solution

1. Step 1: Understand overflow risk

   Multiplying large integers directly can overflow before modulo is applied.

2. Step 2: Apply modular multiplication property

   Using ((a % m) * (b % m)) % m keeps intermediate values small and avoids overflow.

3. Step 3: Evaluate other options

   Compute a * b first, then modulo m risks overflow; options B and C are invalid or inefficient.

4. Final Answer:

   Use modular multiplication: ((a % m) * (b % m)) % m -> Option D

5. Quick Check:

   (a * b) % m = ((a % m) * (b % m)) % m [OK]

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

Common Mistakes:

• Multiplying before modulo causing overflow
• Using floats incorrectly
• String conversion misuse