Modular Arithmetic Basics in DSA Rust - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is modular arithmetic?

Modular arithmetic is a way of doing math where numbers wrap around after reaching a certain value called the modulus. Think of a clock where after 12 comes 1 again.

beginner

What does the expression a % m mean in modular arithmetic?

It means the remainder when a is divided by m. For example, 17 % 5 = 2 because 17 divided by 5 leaves remainder 2.

beginner

How do addition and multiplication work in modular arithmetic?

You add or multiply numbers normally, then take the remainder after dividing by the modulus. For example, if modulus is 5, then (3 + 4) % 5 = 2 and (3 * 4) % 5 = 2.

intermediate

Why is modular arithmetic useful in programming?

It helps keep numbers within a fixed range, avoids overflow, and is used in hashing, cryptography, and algorithms that need wrap-around behavior.

intermediate

What is the result of (a - b) % m if a < b?

In modular arithmetic, (a - b) % m wraps around and stays non-negative by adding m if needed. For example, with a=2, b=5, m=7, (2 - 5) % 7 = 4.

What is 10 % 3?

A 3

B 2

C 0

D 1

10 divided by 3 leaves remainder 1.

If modulus is 6, what is (4 + 5) % 6?

A 5

B 9

C 3

D 1

Sum is 9, and 9 % 6 = 3.

Which operation is NOT valid directly in modular arithmetic?

A Division

B Multiplication

C Addition

D Subtraction

Division is tricky and not always possible in modular arithmetic without special methods.

What does modular arithmetic help prevent in programming?

A Syntax errors

B Number overflow

C Slow execution

D Memory leaks

Modular arithmetic keeps numbers within a fixed range, preventing overflow.

If a = 3, b = 5, and m = 7, what is (a - b) % m?

A 5

B 2

C 3

D 4

(3 - 5) % 7 = (-2) % 7 = 5 since remainder is always non-negative, add 7: -2 + 7 = 5.

Explain how addition and multiplication work in modular arithmetic with an example.

Think about adding or multiplying numbers and then taking remainder.

Describe why modular arithmetic is important in programming and give two examples of its use.

Consider how numbers stay within limits and where this helps.

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