Modular Arithmetic Basics in DSA Rust - Execution Trace

Concept Flow - Modular Arithmetic Basics

Start with number a

↓

Choose modulus m

↓

Calculate remainder r = a mod m

↓

Result r is in range 0 to m-1

↓

Use r for further calculations or comparisons

Start with a number and a modulus, then find the remainder when dividing the number by the modulus. This remainder is the modular result used in calculations.

Execution Sample

DSA Rust

let a = 17;
let m = 5;
let r = a % m;
println!("{} mod {} = {}", a, m, r);

Calculate 17 mod 5, which gives the remainder when 17 is divided by 5.

Execution Table

Step	Operation	Values	Calculation	Result	Explanation
1	Assign a	a=17	-	17	Set the number a to 17
2	Assign m	m=5	-	5	Set the modulus m to 5
3	Calculate remainder	a=17, m=5	17 % 5	2	Divide 17 by 5, remainder is 2
4	Print result	r=2	-	2	Output the modular result 2

💡 Calculation ends after printing the modular remainder

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	Final
a	undefined	17	17	17	17
m	undefined	undefined	5	5	5
r	undefined	undefined	undefined	2	2

Key Moments - 3 Insights

Why is the result always between 0 and m-1?

Because the remainder of division by m can never be equal to or greater than m, as shown in step 3 of the execution_table where 17 % 5 equals 2, which is less than 5.

What happens if a is smaller than m?

If a is smaller than m, the remainder is a itself. For example, if a=3 and m=5, then 3 % 5 = 3. This is because 3 divided by 5 is 0 with remainder 3.

Can the remainder be negative?

In Rust, the % operator returns the remainder with the same sign as the dividend. For positive a and m, remainder is always positive as shown in the example.

Visual Quiz - 3 Questions

Look at the execution_table at step 3, what is the remainder when 17 is divided by 5?

A 5

B 3

C 2

D 0

💡 Hint

Check the 'Result' column in step 3 of the execution_table

At which step is the modulus value assigned?

A Step 2

B Step 1

C Step 3

D Step 4

💡 Hint

Look at the 'Operation' column for 'Assign m' in the execution_table

If a was 4 and m was 5, what would be the remainder?

A 1

B 4

C 0

D 5

💡 Hint

Recall that if a < m, remainder is a itself as explained in key_moments

Concept Snapshot

Modular Arithmetic Basics:
- Use '%' operator to find remainder of division
- Result is always between 0 and m-1 for positive numbers
- Syntax: r = a % m
- Useful for wrapping numbers within a range
- Common in hashing, cyclic structures, and cryptography

Full Transcript

Modular arithmetic finds the remainder when one number is divided by another. We start with a number 'a' and a modulus 'm'. The operation 'a % m' gives the remainder after dividing 'a' by 'm'. This remainder is always between 0 and m-1 for positive numbers. For example, 17 % 5 equals 2 because 5 goes into 17 three times with 2 left over. This concept is useful in many areas like hashing and cyclic counting. In Rust, the '%' operator performs this calculation directly.

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