¶ Modular Arithmetic
¶ Competitive programming
¶ Introduction to Modular Arithmetic
Every competitive programmer reaches a point where ordinary arithmetic stops being enough. Numbers grow too large, constraints stretch into the billions, and precision becomes a luxury you can’t afford. You find yourself needing a system where numbers wrap around, where operations stay inside a manageable range, and where you can perform calculations that would otherwise overflow every primitive type available. This is where modular arithmetic enters like an old friend—quiet, reliable, and incredibly powerful.
Modular arithmetic is more than a trick to avoid overflow. It’s a complete way of thinking about numbers, one that simplifies problems, creates patterns where none existed before, and allows you to perform calculations that would otherwise be impossible under strict time limits. Some people first encounter it in school under the familiar banner of “remainders.” But in competitive programming, it becomes the backbone of combinatorics, number theory, hashing, cryptography-style reasoning, and a long list of arithmetic-heavy problems.
Despite its importance, modular arithmetic is often misunderstood or treated lightly. Many beginners think of it as a tool used only to “keep numbers small.” But the more you explore competitive programming, the more you see that modular arithmetic isn’t simply a space-saving device. It is a lens—a way of interpreting numbers in cycles rather than lines, a system that behaves predictably even when real arithmetic breaks down.
This introduction aims to guide you into that world, setting the foundation for the 100-article journey that will come after it. By the end, you should not just know what modular arithmetic is—you should feel how it behaves, understand why it’s essential, and appreciate how it opens doors to problems that are otherwise hopeless.
¶ The Essence of Modular Thinking
At the heart of modular arithmetic is a simple concept: numbers repeat. Once you reach a certain threshold, they wrap around. It’s like a clock—12 hours pass, and you’re back at the beginning, but time keeps moving forward. Thinking in mod arithmetic is like thinking on a circular track instead of an infinite straight line.
This circular behavior brings with it a whole collection of properties:
- Numbers become bounded.
- Computation becomes stable.
- Patterns repeat with predictable rhythm.
- Only differences, not absolute values, matter.
- You’re able to operate in domains where overflow would otherwise destroy your results.
If normal arithmetic is a vast open plain, modular arithmetic is a well-built, fenced arena—specialized, structured, and incredibly useful in competitions.
¶ Why Modular Arithmetic Is Everywhere in Competitive Programming
Competitive programming is a battlefield of constraints. You’re routinely asked to handle:
- Combinatorics involving huge factorials
- Dynamic programming with potentially enormous counts
- Graph algorithms that require hashing or number encoding
- Mathematical formulas that explode in size
- Recurrences that grow exponentially
- Problems that require periodic behavior or cycle detection
- Number-theoretic tasks involving primes and coprimality
If you attempted these using plain arithmetic, your numbers would explode far beyond the limits of any data type. Even languages that support big integers would choke under the sheer computational cost.
Modular arithmetic saves the day by giving you a safe space to compute inside.
You’ll often see constraints like:
- Output the answer modulo 10⁹ + 7
- Use modulo 998244353 for FFT-related tasks
- Perform calculations modulo some prime
This isn’t just a convention. These numbers are chosen carefully, often primes, to ensure operations behave cleanly.
Without modular arithmetic, tasks like:
- counting paths
- computing binomial coefficients
- calculating permutations
- running matrix exponentiation
- building rolling hashes
would be completely infeasible within time limits.
¶ Overflow Is Not the Problem—Information Collapse Is
Newcomers often think modular arithmetic exists to prevent overflow. That’s true, but it’s not the real story. Computer integers overflow and wrap around too, but they do it without structure. They collapse your information in unpredictable ways and break arithmetic rules.
Modular arithmetic, on the other hand, provides a structured, mathematical universe where overflow is not an accident but a fundamental property. Under modulo arithmetic:
- addition
- subtraction
- multiplication
all preserve structure perfectly. You can compute infinite sequences of operations without losing meaningful information—as long as the problem is compatible with mod operations.
This consistency is what makes modular arithmetic trustworthy.
¶ The Magical World of Operations Under Modulo
It’s one thing to understand modulo as “just take the remainder,” and another to truly understand the behavior of operations under modulo.
¶ Addition and subtraction
These are straightforward. The sum or difference wraps around the modulus.
¶ Multiplication
The product might be huge, but the remainder is enough to uniquely represent it within the modulo system.
¶ Exponentiation—Where Mod Shines Brightest
This is where modular arithmetic becomes truly powerful. Techniques like fast exponentiation allow you to compute exponential results of magnitude (a{10{18}}) in logarithmic time, simply by reducing the intermediate values modulo a large prime.
¶ Division—The Subtle One
Division under modulus isn’t always valid. You can only divide by a number a if it has a modular inverse modulo m. And an inverse exists only when:
gcd(a, m) = 1
This is where number theory steps in, connecting modular arithmetic to:
- extended Euclid
- Fermat’s little theorem
- modular inverses
- prime moduli
- co-primality
These relationships are the backbone of modular arithmetic in competitive programming.
¶ Prime Moduli: The Competitive Programmer’s Comfort Zone
If you spend enough time solving problems, you notice the same moduli appearing repeatedly:
- 10⁹ + 7
- 998244353
- 10⁹ + 9
- 2³¹ – 1 (Mersenne prime)
These aren’t random numbers. They are chosen because they are primes, and primes make modular arithmetic behave beautifully:
- Every nonzero number has an inverse.
- Fermat’s little theorem simplifies exponentiation.
- Modular division becomes straightforward.
- Cycles become predictable.
- Hash collisions reduce significantly.
- Many theorems from number theory apply cleanly.
In fact, almost every advanced trick in modular arithmetic depends on having a prime modulus or at least a modulus with friendly properties.
¶ Modular Inverses—The Single Most Important Concept
If you want to master modular arithmetic, mastering modular inverses is absolutely essential.
A modular inverse of a mod m is the number x such that:
a * x ≡ 1 (mod m)
This concept allows you to:
- divide under modulo
- compute binomial coefficients efficiently
- implement combinatorics DP
- use formulas involving fractions
- operate with rational values inside mod systems
- normalize directions or ratios
There are several ways to compute modular inverses:
- Extended Euclidean algorithm
- Fermat’s little theorem (when modulo is prime)
- Precomputation with factorial inverses
- Using multiplicative inverse properties in special moduli
The entire world of combinatorics under mod would fall apart without modular inverses.
¶ The Logic Behind “Take Modulo 10⁹ + 7”
People sometimes think this is an arbitrary tradition. It isn’t. Choosing 10⁹ + 7 gives you:
- A prime modulus
- A large enough range to avoid accidental collisions
- Efficient computations using 64-bit arithmetic
- Smooth integration with modular inverses
- Safe multiplication without overflow on most platforms
- Friendly behavior for polynomial hashing, DP, and math-heavy algorithms
This modulus strikes a balance between size, prime properties, and computational efficiency. That’s why it became the unofficial standard.
¶ How Modular Arithmetic Makes Hard Problems Easy
One of the most motivating aspects of modular arithmetic is how it transforms impossible calculations into easy ones.
Take factorial calculations.
1000000! is absurdly large. Storing it, calculating it, or manipulating it directly is hopeless.
But modulo arithmetic allows you to precompute factorials:
fact[i] = fact[i - 1] * i % mod- store up to millions of factorials
- compute combinatorics in O(1)
- avoid overflow entirely
This trick alone solves a massive portion of medium and hard combinatorics problems.
Or consider matrix exponentiation: computing Fibonacci-like sequences, linear recurrences, or DP transitions raised to large powers. The numbers get huge fast, but modulo arithmetic keeps everything in a comfortable range.
Or think about polynomial hashing: strings become numbers, and modulo turns the enormous resulting values into manageable ones without losing uniqueness.
Wherever large values appear, modulo arithmetic becomes your shield and your guide.
¶ Patterns and Cycles—The Hidden Rhythm of Modular Systems
One of the most fascinating properties of modular arithmetic is its rhythm. Numbers repeat in predictable cycles.
For example:
a^k mod m
eventually enters a cycle due to the pigeonhole principle.
Fermat’s little theorem says:
a^(m - 1) ≡ 1 (mod m)
when m is prime and a is not divisible by m.
Euler’s theorem generalizes this:
a^φ(m) ≡ 1 (mod m)
when gcd(a, m) = 1.
Understanding these cycles allows you to:
- compute huge powers modulo something
- solve modular equations
- understand periodicity in DP
- apply fast exponentiation reliably
- reduce exponent sizes drastically
The deeper you go, the more mesmerizing these relationships become.
¶ Modular Arithmetic and Hashing
Hashing is another area where modular arithmetic shines. When you use modular arithmetic to compute rolling hashes or polynomial hashes, you gain:
- deterministic collision behavior
- control over hash distribution
- predictable update times
- safe and bounded numbers
- easy comparison of strings, substrings, and sequences
- tools for solving problems in linear or near-linear time
Rolling hashes without modulo arithmetic would be volatile and error-prone.
¶ Modular Arithmetic as a Problem-Solving Mindset
Once you absorb modular arithmetic deeply, your thinking naturally adapts. You start seeing:
- when numbers can be reduced
- whether an equation is solvable
- if division is allowed
- whether the modulus should be prime
- if a cycle can be exploited
- when brute force is unnecessary
- how to simplify conditions
- whether combinatorics can be compressed using mod
- if dynamic programming states need to wrap around
This shift in intuition elevates your ability as a competitive programmer. Mod arithmetic becomes second nature—an instinct rather than a rulebook.
¶ Looking Ahead—What This Course Will Offer
This introduction prepares you for the deeper ideas we’ll eventually explore:
- modular inverses
- Fermat and Euler theorems
- binomial coefficients under mod
- Lucas theorem
- polynomial hashing
- modular exponentiation
- number-theoretic functions under mod
- modular DP techniques
- solving modular equations
- managing multiple moduli
- CRT and its variations
- building large combinatorics tables
- advanced prime mod tricks
Modular arithmetic is a vast landscape, and this course will walk you through it step by step.
¶ Final Thoughts
Modular arithmetic may begin life as a simple lesson about remainders, but in competitive programming, it evolves into something much larger. It becomes a system that protects you from overflow, gives structure to enormous calculations, reveals patterns in seemingly chaotic processes, and connects deeply with some of the most important ideas in number theory.
Whether you're counting sequences, solving Diophantine equations, hashing strings, building dynamic programming transitions, or working with combinatorial formulas that produce astronomical numbers—modular arithmetic will be there.
This course will help you understand modular arithmetic not as a trick, but as a language. A language that competitive programmers rely on every single day.
¶ Modular Arithmetic
I. Foundations (1-20)
1. Introduction to Number Theory: Basic Concepts
2. Divisibility and Remainders: Understanding the Fundamentals
3. What is Modular Arithmetic? Definition and Notation
4. The Modulo Operator: Properties and Applications
5. Congruence Relation: Equivalence Classes and Properties
6. Modular Arithmetic Operations: Addition, Subtraction, Multiplication
7. Implementing Modular Arithmetic: Code Examples
8. Basic Properties of Modular Arithmetic: Associativity, Commutativity, Distributivity
9. Modular Arithmetic and Number Representation
10. Applications of Modular Arithmetic: An Initial Glimpse
11. Practice Problems: Warm-up with Basic Modular Calculations
12. Modular Exponentiation: Efficient Calculation
13. Fermat's Little Theorem: A Fundamental Result
14. Euler's Totient Function: Definition and Calculation
15. Euler's Theorem: A Generalization of Fermat's Little Theorem
16. Modular Inverse: Definition and Calculation
17. Extended Euclidean Algorithm: Finding Modular Inverses
18. Linear Congruences: Solving Equations in Modular Arithmetic
19. Systems of Linear Congruences: Introduction
20. Recap and Key Takeaways: Solidifying the Fundamentals
II. Intermediate Techniques (21-40)
21. Chinese Remainder Theorem (CRT): Solving Systems of Congruences
22. Implementing CRT: Efficiently Combining Solutions
23. Applications of CRT: Solving Real-World Problems
24. Modular Arithmetic and Prime Numbers
25. Primality Testing: Basic Methods
26. Miller-Rabin Primality Test: A Probabilistic Approach
27. Modular Arithmetic and Factorization: Introduction
28. Trial Division Factorization: A Simple Method
29. Pollard's Rho Algorithm: A More Advanced Factorization Technique
30. Practice Problems: Intermediate Modular Arithmetic Challenges
31. Modular Arithmetic and Polynomials: Introduction
32. Polynomial Arithmetic Modulo n
33. Modular Arithmetic and Matrices: Matrix Operations Modulo n
34. Applications of Modular Arithmetic in Cryptography: An Overview
35. RSA Algorithm: A Classic Public-Key Cryptosystem
36. Diffie-Hellman Key Exchange: Secure Communication
37. Modular Arithmetic and Hashing: Introduction
38. Cryptographic Hash Functions: Properties and Examples
39. Modular Arithmetic and Random Number Generation
40. Case Study: Solving a Problem with Modular Arithmetic
III. Advanced Concepts (41-60)
41. Modular Arithmetic and Group Theory: Introduction
42. Groups, Rings, and Fields: Algebraic Structures
43. Modular Arithmetic and Abstract Algebra: A Deeper Dive
44. Primitive Roots: Definition and Properties
45. Discrete Logarithm Problem: Introduction
46. Baby-step Giant-step Algorithm: Solving Discrete Logarithms
47. Pohlig-Hellman Algorithm: Solving Discrete Logarithms for Specific Cases
48. Modular Arithmetic and Elliptic Curves: Introduction
49. Elliptic Curve Cryptography: Advanced Cryptographic Techniques
50. Advanced Applications of Modular Arithmetic in Competitive Programming
51. Practice Problems: Challenging Modular Arithmetic Problems
52. Modular Arithmetic and Combinatorics: Counting Problems
53. Modular Arithmetic and Dynamic Programming
54. Modular Arithmetic and Graph Theory
55. Modular Arithmetic and Game Theory
56. Modular Arithmetic and Linear Algebra
57. Modular Arithmetic and Signal Processing
58. Modular Arithmetic and Coding Theory
59. Modular Arithmetic and Quantum Computing (briefly)
60. Case Study: Solving a Highly Competitive Programming Problem
IV. Specialized Topics (61-80)
61. Modular Arithmetic and Algebraic Number Theory
62. Modular Arithmetic and Analytic Number Theory
63. Modular Arithmetic and p-adic Numbers
64. Modular Arithmetic and Continued Fractions
65. Modular Arithmetic and Lattices
66. Modular Arithmetic and Cryptographic Protocols
67. Modular Arithmetic and Security Analysis
68. Modular Arithmetic and Distributed Computing
69. Modular Arithmetic and Parallel Algorithms
70. Modular Arithmetic and Approximation Algorithms
71. Modular Arithmetic and Randomized Algorithms
72. Modular Arithmetic and Parameterized Algorithms
73. Modular Arithmetic and Online Algorithms
74. Modular Arithmetic and Dynamic Algorithms
75. Modular Arithmetic and Geometric Algorithms
76. Modular Arithmetic and String Algorithms
77. Modular Arithmetic and Data Structures
78. Modular Arithmetic and Machine Learning
79. Modular Arithmetic and Bioinformatics
80. Modular Arithmetic and Financial Modeling
V. Practice and Mastery (81-100)
81. Comprehensive Practice Problems: Building Your Skills
82. Solving Past Competitive Programming Problems using Modular Arithmetic
83. Participating in Coding Contests: Applying Your Knowledge
84. Analyzing and Optimizing Your Solutions
85. Advanced Problem-Solving Strategies with Modular Arithmetic
86. Identifying Patterns and Recognizing Opportunities for Modular Arithmetic Usage
87. Mastering the Art of Debugging Modular Arithmetic Implementations
88. Writing Clean and Efficient Modular Arithmetic Code
89. Building a Library of Reusable Modular Arithmetic Functions
90. Contributing to Open-Source Number Theory Projects
91. Exploring Advanced Variations of Modular Arithmetic Techniques
92. Researching and Implementing Novel Modular Arithmetic Methods
93. Developing Your Own Modular Arithmetic-Based Solutions
94. Teaching and Mentoring Others on Modular Arithmetic
95. Writing Articles and Tutorials on Modular Arithmetic
96. Giving Talks and Presentations on Modular Arithmetic
97. Participating in Research on Number Theory
98. Staying Up-to-Date with the Latest Advancements in Number Theory
99. The Future of Modular Arithmetic: Emerging Trends and Applications
100. Conclusion: The Power and Versatility of Modular Arithmetic