CodeWithYash

Foundation · Module 2 · Lesson 3

Modular arithmetic

Overflow-safe arithmetic and cyclic values.

15–25 min readLesson 9 of 123

Lesson 9 of 123

1d streak

Theory lesson · Step-by-step

Understand Modular arithmetic

Overflow-safe arithmetic and cyclic values.

Worked approach

Trace the reasoning step by step

  1. 1Write the relevant identity or bit property for Modular arithmetic.
  2. 2Normalize signs, ranges, and overflow-sensitive values before calculating.
  3. 3Apply one valid transformation and verify the identity still holds.
  4. 4Stop at the simplest base form, then translate the result back to the requested output.
  5. 5Test zero, one, negative values, repeated factors, and numeric limits.

Concrete example

Compute 3¹³ mod 7 without constructing 3¹³.

  1. 13¹ ≡ 3
  2. 23² ≡ 2
  3. 33⁴ ≡ 4
  4. 43⁸ ≡ 2
  5. 53¹³ = 3⁸·3⁴·3

2 × 4 × 3 mod 7 = 3.

What must remain true (Loop Invariant)

Every transformation used by Modular arithmetic preserves the mathematical quantity or relation being computed.

Cost Model

Complexity & Trade-offs

Fast exponentiation
O(log exponent)
O(1) iterative
The bound follows from the number of states visited and the work performed per transition.

When to use it

  • Counting, divisibility, modular cycles, masks, and overflow-safe arithmetic.
  • Replacing simulation with a mathematical identity.
  • Encoding compact state for search and dynamic programming.

Common mistakes

  • Using an identity without checking its domain or overflow behavior.
  • Forgetting how the language handles negative remainder and signed shifts.
  • Confusing value magnitude with the number of input values.

Practice prompts

  • Reproduce the worked Modular arithmetic example without looking at the trace.
  • Change one input condition and explain whether the Modular arithmetic invariant still holds.
  • Implement the approach, derive its cost, and compare it with a straightforward baseline.

Mastery check

Can you derive it instead of memorizing it?

State the invariant before looking at code.
Explain why every transition is safe.
Construct a worst-case input.
Name one alternative and its trade-off.