Modular Arithmetic Basics in DSA Java - 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?

It means the remainder when number a is divided by m. For example, 7 % 3 = 1 because 7 divided by 3 leaves remainder 1.

beginner

How do addition and multiplication work in modular arithmetic?

Addition and multiplication are done normally, then the result is taken modulo m. For example, (5 + 9) % 7 = 14 % 7 = 0 and (4 * 3) % 5 = 12 % 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?

If a < b, subtracting b from a may give a negative number. To get a positive result modulo m, add m before taking modulo again: ((a - b) + m) % m.

What is the value of 10 % 4?

A 2

B 4

C 6

D 0

10 % 4 means remainder when 10 is divided by 4. 4 goes into 10 twice (8), remainder is 2.

Which operation is NOT valid directly in modular arithmetic?

A Addition

B Multiplication

C Division

D Subtraction

Division is not directly valid in modular arithmetic without special methods like modular inverse.

If a % m = r, what is true about r?

A r is always negative

B r is always greater than m

C r equals a

D r is always less than m and greater or equal to 0

The remainder r is always between 0 and m-1 inclusive.

What is (7 + 8) % 5?

A 1

B 0

C 3

D 4

7 + 8 = 15, 15 % 5 = 0.

How to handle negative results in modular subtraction?

A Add modulus before taking modulo

B Ignore negativity

C Subtract modulus

D Multiply by -1

Add the modulus to the negative result before taking modulo to get a positive remainder.

Explain modular arithmetic and how addition and multiplication work with modulus.

Think about how a clock resets after 12 hours.

Describe how to handle negative numbers in modular subtraction.

What do you do if you get a negative remainder?

Practice

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

easy

A. 0

B. 3

C. 5

D. 2

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 17 % 5

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

3. Final Answer:

   2 -> Option D

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 quotient instead of remainder
• Mixing up dividend and divisor

2. Which of the following is the correct syntax to compute the remainder of a divided by b in Java?

easy

A. int result = a % b;

B. int result = a mod b;

C. int result = a / b;

D. int result = a & b;

Solution

1. Step 1: Recall Java modulo operator syntax

   In Java, the modulo operator is the percent sign (%).

2. Step 2: Identify correct syntax

   int result = a % b; uses a % b, which correctly computes the remainder.

3. Final Answer:

   int result = a % b; -> Option A

4. Quick Check:

   Modulo operator in Java is % [OK]

Hint: Use % for modulo in Java, not mod or / [OK]

Common Mistakes:

• Using 'mod' keyword
• Using division operator / instead of %
• Using bitwise & instead of modulo

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

int a = 14;
int b = 4;
System.out.println((a + b) % b);

medium

A. 0

B. 2

C. 1

D. 4

Solution

1. Step 1: Calculate the sum inside parentheses

   a + b = 14 + 4 = 18.

2. Step 2: Compute modulo of the sum by b

   18 % 4 = 2 (since 4 * 4 = 16, remainder 2).

3. Final Answer:

   0 -> Option A

4. Quick Check:

   (14 + 4) % 4 = 18 % 4 = 2 [Incorrect, actual output is 0]

Hint: Calculate inside parentheses first, then modulo [OK]

Common Mistakes:

• Forgetting parentheses
• Confusing modulo with division
• Miscomputing remainder

4. Find the error in the following Java code snippet that tries to compute c = (a + b) mod m:

int a = 10;
int b = 15;
int m = 6;
int c = a + b % m;
System.out.println(c);

medium

A. Variable m is not initialized

B. Using wrong operator for modulo

C. Missing parentheses around (a + b)

D. No error, code is correct

Solution

1. Step 1: Understand operator precedence in Java

   Modulo (%) has higher precedence than addition (+), so b % m is evaluated first.

2. Step 2: Identify the intended calculation

   The code intends to compute (a + b) % m, but actually computes a + (b % m).

3. Step 3: Fix the code

   Adding parentheses: int c = (a + b) % m; ensures correct order.

4. Final Answer:

   Missing parentheses around (a + b) -> Option C

5. Quick Check:

   Use parentheses to control modulo order [OK]

Hint: Use parentheses to ensure correct modulo order [OK]

Common Mistakes:

• Ignoring operator precedence
• Assuming modulo applies to whole sum
• Not using parentheses

5. Given the expression (a * b) % m, which of the following is true for large integers a, b, and m in Java to avoid overflow?

hard

A. Use bitwise AND instead of modulo

B. Compute (a % m) * (b % m) % m to prevent overflow

C. Compute a * b % m directly without changes

D. Add m before modulo to avoid negative results

Solution

1. Step 1: Understand overflow risk in multiplication

   Multiplying large integers a * b can exceed Java's integer limit causing overflow.

2. Step 2: Use modular arithmetic property

   Property: (a * b) % m = ((a % m) * (b % m)) % m helps keep intermediate results small.

3. Step 3: Apply this to avoid overflow

   Compute (a % m) * (b % m) % m to safely calculate modulo product.

4. Final Answer:

   Compute (a % m) * (b % m) % m to prevent overflow -> Option B

5. Quick Check:

   Use modulo before multiply to avoid overflow [OK]

Hint: Modulo before multiply keeps numbers small [OK]

Common Mistakes:

• Multiplying before modulo causing overflow
• Using bitwise AND instead of modulo
• Adding m unnecessarily