¶ Number Theory Algorithms
¶ Competitive programming
There’s something almost poetic about number theory. It is a field built on the most basic things imaginable—integers, divisibility, primes—yet it somehow spills into some of the deepest corners of mathematics and computer science. In competitive programming, number theory holds a special place. It doesn’t overwhelm you with long formulas or abstract symbols; instead, it pulls you in with patterns, clever tricks, and surprisingly elegant ideas that turn seemingly impossible computations into fast, beautiful solutions.
Many contestants begin their journey encountering number theory through simple modular arithmetic or prime sieves. It feels harmless at first. But the more problems you unlock, the clearer it becomes that number theory is one of the strongest pillars of algorithmic problem-solving. It gives you the tools to deal with huge inputs, impossible constraints, strange mathematical behaviors, and elegant optimizations that appear like magic until you understand the structure beneath them.
At its heart, number theory asks fundamental questions about the nature of integers—questions that have fascinated mathematicians for centuries. But in competitive programming, those questions transform into practical tools. You’re no longer just proving properties; you’re using them to compute results fast, avoid overflow, reduce complexity, and build algorithms that operate on massive numbers efficiently. What makes number theory so compelling is that the gap between theory and application is very small. You can study an idea like modular inverses one moment and directly apply it to solve a tricky counting problem the next.
The first real taste of power often comes when you realize how efficiently primes can be handled. A brute-force primality check on huge inputs stops being feasible very quickly. Then you discover the sieve of Eratosthenes, and something shifts—you see that with a smart bit of preprocessing, you can generate primes for enormous ranges almost effortlessly. You see how composite structures reveal themselves naturally through simple iteration. And then you discover faster variations, segmented sieves, bitset tricks, prime factorization techniques, and methods to handle queries rapidly even in interactive problems.
From there, modular arithmetic becomes a natural companion. When numbers grow too large to handle directly, working under a modulus becomes essential. But modulus arithmetic has its quirks. You learn how addition, subtraction, and multiplication behave in this strange but beautiful world where numbers wrap around themselves. You start using modular exponentiation to raise huge powers efficiently; you discover that exponentiation can be split recursively, reducing a seemingly impossible computation into something manageable. And then you meet Fermat’s little theorem, which suddenly lets you find modular inverses with surprising ease. It feels like discovering a hidden backstage entrance to a concert you thought you couldn’t attend.
One of the most interesting parts of number theory in competitive programming is how ideas build on one another. You learn GCD and LCM relationships not just to compute them, but to reason about divisibility, optimize loops, reduce fractions, or simplify expressions in deeper problems. The Euclidean algorithm, with its simple recursive structure, starts appearing everywhere—hidden inside formula derivations, powering modular inverses, helping construct linear Diophantine equations, or guiding solutions to problems involving ratios, periodicity, or extended constraints.
The extended version of Euclid’s algorithm opens an entirely new realm. Suddenly you can find solutions to equations of the form ax + by = c. You can determine when solutions exist, find one solution, or even generate all possible ones. This becomes invaluable when tackling problems involving shifts, ranges, or constructing minimal or maximal integers under divisibility constraints.
And then comes the joy of working with modular inverses, which show up in combinatorics, probability, hashing, cryptography-style problems, and anywhere that division appears inside a modular system. When you learn multiple ways to compute inverses—through Fermat’s theorem, extended Euclid, or precomputation using factorials—you start appreciating the depth of number theory. What looks like a small mathematical detail often becomes the key to unlocking a problem that initially seems overwhelming.
As you go deeper, you discover number-theoretic functions like Euler’s totient function, which counts the number of integers coprime to a given number. At first, you may wonder where something like that could be useful. But then you encounter modular exponent cycles, periodicity patterns, optimized power towers, or the construction of advanced sieve-like algorithms that require totients. These concepts aren’t distant theoretical curiosities; they are practical tools that appear naturally when solving competitive problems that impose large numerical boundaries.
One of the most eye-opening experiences is stumbling into the world of combinatorics through the lens of number theory. Suddenly factorials under modulus, binomial coefficients, Pascal’s triangle, and Lucas’ theorem begin to matter deeply. You realize that computing combinations like C(n, k) isn’t trivial under large moduli, and number theory provides the only manageable pathway—factorials, inverse factorials, modular inverses, or special theorems designed to handle prime moduli. You start seeing patterns: binomial coefficients mod p behave differently from mod composite numbers; multiplicities of primes matter; exponent counts guide valuations of factorials.
Eventually, you encounter multiplicative functions, a concept that feels abstract at first but soon reveals its elegance. Functions like μ(n) (the Möbius function) or φ(n) (Euler’s totient) begin forming the backbone of more advanced techniques. You start understanding that many number-theoretic problems fundamentally revolve around factorization structure—square-free components, prime decomposition, or multiplicative properties. Even though you might not need the full machinery for every contest, these insights sharpen your intuition and equip you to recognize when a problem is secretly inviting you to exploit something multiplicative.
Divisors and prime factorization form another critical part of the journey. Understanding how to generate divisors efficiently, how to count them, how to track exponent patterns, and how to use decomposition to simplify large expressions becomes indispensable. Problems that involve sums over divisors, counting pairs with certain GCD properties, or evaluating convolution-like operations suddenly stop feeling intimidating once you understand how primes shape everything.
The beauty of number theory in competitive programming is that it treats massive numbers with surprising agility. You can compute a^b mod n even when b has hundreds of digits. You can factorize numbers in logarithmic or near-logarithmic time using pre-factored primes. You can compute large combinatorics values under modulus, evaluate polynomial-like expressions efficiently, or determine existence of solutions using elegant mathematical rules. What at first appears like a barrier—“the numbers are too large”—turns into an opportunity to apply clever techniques.
One of the most delightful discoveries is learning to appreciate modular cyclic behavior. Numbers repeat in patterns under modulus, and once you recognize those cycles, problems involving repeated operations, power towers, or modular transformations become far more manageable. You start using Euler’s theorem or Carmichael functions not as theoretical curiosities, but as practical shortcuts that let you shrink gigantic numbers into something approachable. Problems that previously required heavy computation become elegant because number theory gives you the blueprint for compressing them.
And just when you feel comfortable, a new layer opens—polynomial hashing, modular arithmetic under large primes, constructing pseudo-random sequences, or solving matrix recurrences under moduli using exponentiation techniques. These problems don’t belong strictly to number theory alone, but they rely heavily on number-theoretic reasoning. Even when you're working on problems that don’t look inherently mathematical, number theory often provides the underlying magic—fast exponentiation in matrix multiplication, modular inverses in DP recurrences, prime moduli in hashing schemes.
Later, you encounter more specialized topics—primitive roots, discrete logarithms, fast factorization techniques, quadratic residues, and modular equations. These topics straddle the line between pure number theory and algorithmic design. They aren’t always required in every contest, but when they do appear, they reward you with a deep sense of satisfaction. Solving a discrete logarithm with baby-step giant-step feels like discovering a secret passage in the mathematical landscape. Learning to compute square roots modulo a prime feels like watching algebra and number theory merge into a single elegant picture.
What makes number theory so compelling in competitive programming is how the ideas reinforce each other. Once you build a foundation, every new concept settles easily into place. Modular arithmetic supports combinatorics; factorization supports divisor logic; totients support modular exponent reduction; Euclid supports inverse construction. The entire field links together in a sort of interconnected web. And once you see that web, solving number theory problems becomes less about memorizing formulas and more about recognizing which strand of the web you need to pull.
As you progress, you begin to notice that number theory cultivates a certain type of problem-solving intuition. You become quicker at spotting hidden patterns—repetition cycles, symmetry, primes that matter, divisibility constraints, or structures that rely on reducing large numbers using modular rules. Problems that used to feel too “mathematical” start to look algorithmic, almost computational. You start predicting where a modulus will simplify things, when a value must be pre-computed, when to apply fast exponentiation, or when a direct combinatorial formula is impossible without number-theoretic tools.
Eventually, number theory becomes more than just a toolbox. It becomes a way of thinking. It encourages precision, clarity, and an appreciation for the hidden structure behind integers. It teaches you that every number tells a story—how it factors, how it behaves under different moduli, how it influences counting arguments, and how it transforms under repeated operations. Understanding those stories gives you an enormous edge in competitive programming, where problems often appear convoluted but collapse once you uncover the right mathematical key.
There’s a unique kind of satisfaction that comes from solving a problem using number theory. It is the satisfaction of uncovering something deeper, something that feels almost inevitable once you see it. Whether it’s finding the last digit of a huge power, counting solutions to modular equations, constructing sequences with special properties, or optimizing combinatorial expressions, number theory brings a sense of harmony to the chaos of large numbers.
And perhaps the most beautiful part is that number theory never stops surprising you. No matter how much you learn, there is always another clever trick, another elegant theorem, another simplifying insight waiting just around the corner. It’s a field rich enough to sustain a lifetime of curiosity, yet practical enough to become a close companion in the fast-paced world of competitive programming.
¶ Number Theory Algorithms
¶ Beginner Level (1-30)
1. Introduction to Number Theory in Competitive Programming
2. Divisibility and Basic Properties
3. Prime Numbers: Definition and Identification
4. Sieve of Eratosthenes: Finding Primes Efficiently
5. Prime Factorization: Breaking Down Numbers
6. Greatest Common Divisor (GCD): Euclidean Algorithm
7. Extended Euclidean Algorithm: Solving Linear Diophantine Equations
8. Least Common Multiple (LCM): Properties and Applications
9. Modular Arithmetic: Basics and Properties
10. Modular Addition, Subtraction, and Multiplication
11. Modular Exponentiation: Fast Powering
12. Multiplicative Inverses: Definition and Applications
13. Fermat's Little Theorem: Introduction and Proof
14. Euler's Totient Function: Definition and Properties
15. Euler's Theorem: Generalization of Fermat's Little Theorem
16. Chinese Remainder Theorem: Introduction and Applications
17. Basic Problems on Prime Numbers
18. Basic Problems on GCD and LCM
19. Basic Problems on Modular Arithmetic
20. Introduction to Number Theory in Problem Solving
21. Handling Large Numbers: Big Integer Operations
22. Sum of Divisors Function: Basics
23. Number of Divisors Function: Basics
24. Perfect Numbers: Definition and Examples
25. Amicable Numbers: Introduction
26. Pythagorean Triples: Generating and Verifying
27. Fibonacci Numbers: Properties and Applications
28. Catalan Numbers: Introduction
29. Factorials and Their Properties
30. Basic Number Theory Problems in Competitive Programming
¶ Intermediate Level (31-60)
31. Advanced Sieve Techniques: Segmented Sieve
32. Pollard's Rho Algorithm: Factoring Large Numbers
33. Miller-Rabin Primality Test: Probabilistic Primality Checking
34. Lucas-Lehmer Test: Primality of Mersenne Primes
35. Carmichael Numbers: Pseudoprimes
36. Wilson's Theorem: Applications in Primality Testing
37. Legendre's Formula: Prime Factorization of Factorials
38. Mobius Function: Definition and Applications
39. Inclusion-Exclusion Principle in Number Theory
40. Sum of Divisors Function: Advanced Techniques
41. Number of Divisors Function: Advanced Techniques
42. Linear Diophantine Equations: Advanced Problems
43. Chinese Remainder Theorem: Advanced Applications
44. Discrete Logarithms: Baby-Step Giant-Step Algorithm
45. Primitive Roots: Definition and Properties
46. Quadratic Residues: Introduction
47. Legendre Symbol: Definition and Applications
48. Jacobi Symbol: Generalization of Legendre Symbol
49. Tonelli-Shanks Algorithm: Solving Quadratic Congruences
50. Continued Fractions: Basics and Applications
51. Pell's Equation: Solving and Applications
52. Sum of Squares: Representing Numbers
53. Sum of Cubes: Representing Numbers
54. Advanced Problems on GCD and LCM
55. Advanced Problems on Modular Arithmetic
56. Advanced Problems on Prime Numbers
57. Advanced Problems on Euler's Totient Function
58. Advanced Problems on Multiplicative Inverses
59. Advanced Problems on Chinese Remainder Theorem
60. Intermediate Number Theory Problems in Competitive Programming
¶ Advanced Level (61-90)
61. Sieve of Atkin: Advanced Prime Generation
62. Quadratic Sieve: Factoring Large Numbers
63. Number Field Sieve: Factoring Very Large Numbers
64. AKS Primality Test: Deterministic Primality Checking
65. Elliptic Curve Primality Proving
66. Advanced Applications of Euler's Totient Function
67. Advanced Applications of Mobius Function
68. Advanced Applications of Inclusion-Exclusion Principle
69. Advanced Applications of Chinese Remainder Theorem
70. Advanced Applications of Discrete Logarithms
71. Advanced Applications of Primitive Roots
72. Advanced Applications of Quadratic Residues
73. Advanced Applications of Legendre and Jacobi Symbols
74. Advanced Applications of Tonelli-Shanks Algorithm
75. Advanced Applications of Continued Fractions
76. Advanced Applications of Pell's Equation
77. Advanced Applications of Sum of Squares and Cubes
78. Advanced Problems on Linear Diophantine Equations
79. Advanced Problems on Modular Exponentiation
80. Advanced Problems on Multiplicative Functions
81. Advanced Problems on Prime Factorization
82. Advanced Problems on Sieve Techniques
83. Advanced Problems on Primality Testing
84. Advanced Problems on Factorials and Divisors
85. Advanced Problems on Fibonacci and Catalan Numbers
86. Advanced Problems on Pythagorean Triples
87. Advanced Problems on Perfect and Amicable Numbers
88. Advanced Problems on Carmichael Numbers
89. Advanced Problems on Wilson's Theorem
90. Advanced Number Theory Problems in Competitive Programming
¶ Expert Level (91-100)
91. Advanced Topics in Elliptic Curves
92. Advanced Topics in Algebraic Number Theory
93. Advanced Topics in Analytic Number Theory
94. Advanced Topics in Computational Number Theory
95. Advanced Topics in Cryptography and Number Theory
96. Advanced Topics in Diophantine Approximation
97. Advanced Topics in Modular Forms
98. Advanced Topics in L-Functions
99. Advanced Topics in Zeta Functions
100. Open Problems in Number Theory and Competitive Programming