Modular Arithmetic Basics in DSA Go - Execution Trace

Concept Flow - Modular Arithmetic Basics

Start with numbers a and b

↓

Choose modulus m

↓

Calculate a mod m

↓

Calculate b mod m

↓

Perform operation (add, sub, mul) on results

↓

Take result mod m

↓

Final result

Shows how to compute modular arithmetic by reducing numbers first, then performing operations, and finally taking modulus again.

Execution Sample

DSA Go

package main

import "fmt"

func main() {
    a := 17
    b := 23
    m := 5
    result := (a + b) % m
    fmt.Println(result)
}

Adds 17 and 23, then finds remainder when divided by 5.

Execution Table

Step	Operation	Value(s)	Calculation	Result	Explanation
1	Calculate a mod m	a=17, m=5	17 % 5	2	Remainder of 17 divided by 5 is 2
2	Calculate b mod m	b=23, m=5	23 % 5	3	Remainder of 23 divided by 5 is 3
3	Add reduced values	2 + 3	2 + 3	5	Sum of remainders is 5
4	Take sum mod m	5 % 5	5 % 5	0	Remainder of 5 divided by 5 is 0
5	Print result	result=0	N/A	0	Final modular addition result

💡 All steps done, final modular addition result is 0

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	Final
a	17	17	17	17	17	17
b	23	23	23	23	23	23
m	5	5	5	5	5	5
a_mod	N/A	2	2	2	2	2
b_mod	N/A	N/A	3	3	3	3
sum	N/A	N/A	N/A	5	5	5
result	N/A	N/A	N/A	N/A	0	0

Key Moments - 3 Insights

Why do we take modulus of a and b before adding?

Taking modulus first keeps numbers small and prevents overflow, as shown in steps 1 and 2 where a and b are reduced before addition in step 3.

Why do we take modulus again after addition?

Because sum can be equal or larger than modulus, step 4 takes modulus again to ensure final result is within 0 to m-1.

What if we skip modulus on a and b before addition?

Skipping steps 1 and 2 can cause large intermediate sums, which might overflow or be inefficient; modular arithmetic requires reducing operands first.

Visual Quiz - 3 Questions

Look at the execution_table, what is the value of a_mod after step 1?

A 3

B 2

C 0

D 5

💡 Hint

Check the 'Result' column in row with Step 1 in execution_table

At which step does the sum of remainders get reduced modulo m?

A Step 4

B Step 3

C Step 2

D Step 5

💡 Hint

Look for the step where '5 % 5' is calculated in execution_table

If m was changed to 6, what would be the final result after step 4?

A 0

B 1

C 5

D 2

💡 Hint

Calculate (2 + 3) % 6 based on a_mod and b_mod values in variable_tracker

Concept Snapshot

Modular Arithmetic Basics:
- Compute a mod m and b mod m first
- Perform operation (add, sub, mul) on these reduced values
- Take result mod m again
- Result always in range 0 to m-1
- Helps keep numbers small and avoid overflow

Full Transcript

This lesson shows how modular arithmetic works by first reducing numbers a and b using modulus m, then performing addition, and finally taking modulus again to get the final result. We traced each step: calculating a mod m, b mod m, adding them, and taking modulus of the sum. This keeps numbers small and ensures the result stays within the modulus range. Key points include why modulus is taken before and after operations and how changing modulus affects the result.

Practice

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

easy

A. 0

B. 2

C. 1

D. 3

Solution

1. Step 1: Understand the modulus operation

   The modulus operator (%) gives the remainder when the first number is divided by the second.

2. Step 2: Calculate 7 % 3

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

3. Final Answer:

   1 -> Option C

4. Quick Check:

   7 % 3 = 1 [OK]

Hint: Modulus gives remainder after division [OK]

Common Mistakes:

• Confusing modulus with division
• Using quotient instead of remainder
• Mixing up operands order

2. Which of the following is the correct syntax to compute the modulus of two integers a and b in Go?

easy

A. mod := a % b

B. mod := a mod b

C. mod := a %% b

D. mod := a mod(b)

Solution

1. Step 1: Recall Go syntax for modulus

   In Go, the modulus operator is the percent sign (%) used between two integers.

2. Step 2: Identify correct syntax

   mod := a % b uses a % b, which is the correct way to compute modulus in Go.

3. Final Answer:

   mod := a % b -> Option A

4. Quick Check:

   Go uses % for modulus [OK]

Hint: Use % operator for modulus in Go [OK]

Common Mistakes:

• Using 'mod' keyword instead of %
• Double percent signs %%
• Using function call syntax for modulus

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

package main
import "fmt"
func main() {
    a := 14
    b := 5
    fmt.Println(a % b)
}

medium

A. 2

B. 4

C. 3

D. 0

Solution

1. Step 1: Understand the code variables

   Variable a is 14 and b is 5.

2. Step 2: Calculate 14 % 5

   14 divided by 5 is 2 with remainder 4, so output is 4.

3. Final Answer:

   4 -> Option B

4. Quick Check:

   14 % 5 = 4 [OK]

Hint: Divide and find remainder for modulus [OK]

Common Mistakes:

• Using division result instead of remainder
• Confusing operands order
• Misreading variable values

4. Find the error in this Go code snippet that tries to compute modulus:

package main
import "fmt"
func main() {
    var a, b int = 10, 3
    result := a mod b
    fmt.Println(result)
}

medium

A. Missing import for modulus package

B. fmt.Println syntax error

C. Variables a and b not declared

D. Using 'mod' instead of '%' operator

Solution

1. Step 1: Check modulus operator usage

   The code uses a mod b, but Go does not have a 'mod' keyword.

2. Step 2: Correct operator in Go

   Go uses the percent sign (%) for modulus, so it should be a % b.

3. Final Answer:

   Using 'mod' instead of '%' operator -> Option D

4. Quick Check:

   Modulus in Go uses % [OK]

Hint: Use % operator, not 'mod' keyword [OK]

Common Mistakes:

• Using 'mod' keyword
• Assuming modulus needs import
• Incorrect variable declaration assumptions

5. You want to find the remainder when the sum of two large numbers a = 123456789 and b = 987654321 is divided by 1000. Which expression correctly uses modular arithmetic to compute this efficiently in Go?

hard

A. (a % 1000 + b % 1000) % 1000

B. (a + b) / 1000

C. a % 1000 + b % 1000

D. a + b % 1000

Solution

1. Step 1: Understand modular addition property

   Modular arithmetic allows (a + b) % m = ((a % m) + (b % m)) % m to avoid large sums.

2. Step 2: Apply property to given numbers

   Compute (a % 1000 + b % 1000) % 1000 to get remainder without overflow.

3. Final Answer:

   (a % 1000 + b % 1000) % 1000 -> Option A

4. Quick Check:

   (a + b) % 1000 = ((a % 1000) + (b % 1000)) % 1000 [OK]

Hint: Use modular addition to avoid big sums [OK]

Common Mistakes:

• Adding remainders without final modulus
• Not applying modulus before addition
• Misplacing parentheses