¶ Number Theory Basics
¶ Competitive programming
¶ Introduction to Number Theory Basics in Competitive Programming
There’s something quietly enchanting about number theory. Long before computers existed—long before algorithms, competitions, or modern problem-solving—people were already fascinated by the mysteries hidden inside the simplest objects imaginable: numbers. From ancient mathematicians who carved patterns into stone tablets to contemporary problem solvers clicking away on their keyboards during late-night contests, the story of number theory is one long thread of curiosity, discovery, and elegant reasoning.
In competitive programming, number theory takes on a special life of its own. It appears everywhere—sometimes boldly at the center of the problem, sometimes hidden behind layers of logic, waiting to be uncovered. The more you learn, the more you realize how much power lies in understanding the behavior of integers. And the deeper your understanding becomes, the easier it is to see patterns that once looked chaotic.
This course, composed of one hundred thoughtful articles, will take you on a journey through the foundational ideas of number theory as they relate to competitive programming. Our goal isn’t just to teach formulas or theorems. It’s to build intuition—to make number theory feel like a natural language you can think in rather than a collection of memorized facts. Over the coming articles, you will learn concepts that you’ll use again and again in contests, whether you’re solving simple mathematical puzzles or handling problems with massive constraints.
Before diving into the chapters ahead, let’s take some time to understand what makes number theory so fundamental, so endlessly useful, and so deeply enjoyable.
¶ Why Number Theory Matters in Competitive Programming
At first glance, number theory might sound like a niche topic. After all, isn't competitive programming more about algorithms, data structures, and clever tricks? But when you step into higher-rated contests or deeper problem sets, you gradually discover that nearly every category of programming has number theory hiding under the surface.
Take a look at the kinds of problems that often pop up:
- finding greatest common divisors
- computing modular inverses
- counting divisors or prime factors
- handling huge numbers efficiently
- detecting cycles in modular arithmetic
- identifying patterns in sequences
- solving linear congruences
- performing fast exponentiation
- dealing with big primes or pseudo-primes
- generating primes up to large limits
- working with multiplicative functions
- understanding periodicity and modular behavior
These aren’t rare occurrences—they’re routine. Number theory isn’t a bonus skill; it’s one of the core pillars of competitive programming.
What makes it especially important is that number theory gives you a way to reason about problems that would otherwise be intractable. Anytime the input grows large—millions, billions, or more—you simply cannot brute-force your way through. You need structure. You need shortcuts. Number theory provides those tools.
¶ The Beauty of Working With Integers
One of the first things you realize when studying number theory is how predictable integers can be when viewed the right way. Without any background, they might appear random; but each theorem, each pattern you discover, peels back another layer and reveals a remarkable order.
A small example: the idea that every integer greater than 1 is either prime or can be broken into primes. That seems obvious today, but it’s extraordinary once you realize how much that property controls the behavior of numbers. It’s the reason factorization works. It’s the reason we can talk about gcds, lcms, or prime distributions. It’s the backbone behind enormous fields of cryptography.
Or consider modular arithmetic—a simple idea where you wrap numbers around like the hours on a clock. It seems tiny, almost childish. But this small idea controls everything from hashing to cryptographic protocols to competitive programming tricks like computing exponents in logarithmic time.
When you learn number theory basics, you begin recognizing these hidden structures everywhere. You start seeing gcds in unexpected places. You start recognizing when a problem is secretly about modular inverses. You begin noticing how periodicity shows up in sequences that seemed chaotic at first. Number theory sharpens your mathematical intuition.
¶ A Journey Through Concepts You Will Actually Use
One of the challenges new learners face is that number theory can get abstract fast. You can wander into deep theorems that aren’t needed in contests. This course avoids that by focusing on the core, practical ideas you will repeatedly encounter.
Throughout this course, you’ll explore:
- what primes really are and how to find them
- the power of classical tools like gcd, lcm, and Euclid’s algorithm
- the magic of modular arithmetic and congruences
- how to compute large powers quickly
- how modular inverses unlock new solution paths
- how to use Fermat’s little theorem and Euler’s theorem
- the structure of multiplicative functions
- how divisors behave and how to count them efficiently
- the idea behind prefix sums and cumulative divisors
- how factorization works at different scales
- why phi(n) matters and how it behaves
- how to deal with linear Diophantine equations
- how Chinese remainder theorem solves tricky combination problems
- how to handle combinatorial values under modulus
- how to work with bitwise number theory
- how periodicity helps reduce massive search spaces
Each of these topics is more than a theoretical idea—they become practical tools, keys that unlock new doors in contest problems.
If you’ve ever stared blankly at a problem that said “compute the sum of divisors for numbers up to 10^7," or “determine if a^b = c under modulo m,” or “find x satisfying two modular equations,” this course will transform those problems from intimidating walls into approachable exercises.
¶ The Power of Modular Arithmetic
If there’s one recurring character in the story of number theory in competitive programming, it’s modular arithmetic. The idea is ridiculously simple: when numbers get too large, shrink them. Wrap them around. Let them loop like the hours of a clock.
And yet, from that tiny idea comes:
- modular exponentiation
- modular inverses
- modular linear equations
- modular combinations
- modular division
- modular multiplicative functions
- modular periodicity
- modular hashing
- modular search
- modular DP
- modular recurrence handling
Understanding number theory basics means mastering the behavior of integers inside these modular environments. And once you truly grasp how modular operations behave, a whole world of problems that once seemed out of reach becomes accessible.
This course will guide you through modular arithmetic step by step—not just how to compute under a modulus, but how to think under a modulus.
¶ Why Intuition Matters More Than Memorizing Formulas
There is a temptation when studying number theory to memorize results: Fermat’s theorem, Euler’s theorem, Wilson’s theorem, formula for lcm, formula for divisors, and so on. But contest problems don’t reward memorization. They reward the ability to see a problem from the right angle.
For example:
A problem asks you to compute something like:
a^(b^c) mod m
A student who memorized modular exponentiation might apply it incorrectly.
But someone with genuine intuition will know when to use Euler’s totient function, when to reduce exponents, when to apply modular cycles, and when the modulus complicates things.
Or consider a simple gcd-related problem. A memorizer may try to plug in numbers mechanically. But someone who understands Euclid’s algorithm deeply knows how gcd behaves under addition, subtraction, modulo, and factorization.
This course is structured not to give you a list of facts, but to help you build the instinct that allows you to approach problems with clarity and creativity.
¶ Number Theory as a Bridge to Other Domains
As you progress, you’ll realize something surprising: number theory is not isolated. It spills into many other areas of competitive programming.
It enhances your thinking in:
- combinatorics
- dynamic programming
- graph theory
- hashing
- binary search
- bit manipulation
- probability
- string algorithms
- geometry
- optimization problems
When you understand how integers behave, patterns in these other fields become easier to see. For example, many graph problems boil down to gcd relationships. Many DP problems require modular arithmetic. Many combinatorics problems explode without number theory constraints. Even greedy algorithms get simpler when you understand the divisibility structure that governs the problem.
The broader your number theory foundation becomes, the more you start to see its fingerprints everywhere.
¶ The Emotional Journey of Learning Number Theory
There is a familiar emotional arc for anyone who has learned number theory with dedication.
¶ Curiosity
You start by noticing that problems involving integers feel different. There’s a deeper structure beneath them.
¶ Confusion
You encounter something like modular inverses for the first time, or a Diophantine equation solution, and feel bewildered.
¶ Breakthrough
After working through examples, things begin to click. You start recognizing patterns.
¶ Application
You solve your first few problems that rely directly on number theory. It feels empowering.
¶ Mastery
You reach a point where you look at a problem and intuitively see the underlying structure—modular cycles, prime factorizations, periodic behavior, gcd patterns, all at once.
This course is designed to help you reach that final stage—not through brute force, but through gradual development of understanding and confidence.
¶ Why This Topic Deserves a 100-Article Course
Number theory is rich. Even at the “basics” level, it contains:
- dozens of deeply useful tools
- countless patterns and properties
- intricate relationships between numbers
- essential techniques for efficient computing
Each article in this course builds on the previous one, slowly and intentionally. Some articles introduce foundational concepts like gcd or primes. Others explore deeper patterns like multiplicativity or modular behavior. Some walk you through beautiful algorithms like the sieve of Eratosthenes or fast exponentiation. Others highlight how these ideas come together in real contest problems.
The progression is designed to feel like peeling layers from an onion. With every new article, a little more of the underlying structure becomes visible.
By the time you finish the entire course, you won’t just know number theory—you will think in number theory.
¶ Before You Begin
Number theory doesn’t require genius or mathematical flair. What it does require is patience, curiosity, and a willingness to approach problems with an open mind. This course will take you from the simplest ideas to the most powerful tools used in competitive programming.
Before you begin, remind yourself:
- You don’t need to memorize everything.
- You don’t need specialized math background.
- You don’t need to fear the abstract.
Number theory grows on you gradually. The joy comes not only from answering problems correctly but from understanding why the answer works.
By the end of this course, integers will no longer feel like random objects. They will feel like familiar terrain—a landscape where each hill, valley, and contour has meaning.
So take a deep breath.
Prepare your mind.
Let curiosity guide you.
Welcome to the world of Number Theory Basics—a world filled with patterns, beauty, and the thrill of understanding.
¶ Number Theory Basics
¶ Beginner Level
1. Introduction to Number Theory in Competitive Programming
2. Basic Definitions: Integers, Prime Numbers, and Divisibility
3. Prime Numbers: What Are They and Why Are They Important?
4. The Fundamental Theorem of Arithmetic
5. Divisibility Rules: Quick Methods for Simple Checks
6. Greatest Common Divisor (GCD): Definition and Properties
7. Euclidean Algorithm for GCD
8. Extended Euclidean Algorithm: Solving Linear Diophantine Equations
9. Least Common Multiple (LCM): Definition and Calculation
10. Properties of GCD and LCM
11. Sieve of Eratosthenes for Finding Prime Numbers
12. Prime Factorization of a Number
13. Factorization Algorithms and Their Applications
14. Understanding Modular Arithmetic
15. Basic Modular Operations: Addition, Subtraction, Multiplication
16. Modular Inverse: Definition and Computation
17. Fermat's Little Theorem: Application in Modular Arithmetic
18. Finding Modular Exponentiation Efficiently
19. Chinese Remainder Theorem: Solving Systems of Modular Equations
20. Basic Applications of Number Theory in Competitive Programming
¶ Intermediate Level
21. Divisors of a Number: How to Calculate Them
22. Prime Factorization and Its Importance in Solving Problems
23. Euler’s Totient Function: Definition and Calculation
24. Euler’s Theorem and Its Application
25. Modular Exponentiation: Efficient Algorithms for Large Numbers
26. Fast Exponentiation Techniques: Binary Exponentiation
27. Wilson’s Theorem: Testing Primes Using Factorials
28. Perfect Numbers and Amicable Numbers
29. Understanding Pairs of Numbers: Coprime and Relatively Prime
30. Solving Problems Using GCD and LCM
31. Efficient Calculation of GCD Using Binary GCD Algorithm
32. Application of GCD in Linear Diophantine Equations
33. Fermat's Little Theorem in Action: Fast Primality Testing
34. Solving Problems Using Modular Arithmetic
35. Chinese Remainder Theorem: Extended Algorithms and Applications
36. Computing the Modular Inverse Using the Extended Euclidean Algorithm
37. Finding Powers of Numbers Under Modulo Operation
38. Greatest Common Divisor in Multiple Numbers
39. Efficient Ways to Compute Large Powers in Modular Arithmetic
40. Advanced Modular Arithmetic and Applications in Algorithms
¶ Advanced Level
41. Advanced Modular Inverses and Their Applications
42. Prime Testing Algorithms: Miller-Rabin and AKS Primality Test
43. Sieve of Eratosthenes: Optimizing for Large Ranges
44. Primality Testing: Efficient Approaches for Large Numbers
45. Chinese Remainder Theorem for Non-Coprime Moduli
46. Elliptic Curves and Their Applications in Cryptography
47. Modular Arithmetic in Cryptographic Algorithms
48. Number Theoretic Transform (NTT): Introduction and Applications
49. Solving Quadratic Residues and Non-Residues
50. Using Legendre Symbol to Simplify Modular Arithmetic
51. Jacobi Symbol and Its Properties
52. Linear Congruences: Solving Systems with Modular Arithmetic
53. Quadratic Congruences and Solutions
54. Solving Polynomial Congruences Efficiently
55. Finding Square Roots Modulo Prime Numbers
56. Advanced Applications of Euler’s Theorem
57. Chinese Remainder Theorem for Large Systems of Equations
58. Advanced GCD Algorithms for Multiple Numbers
59. Efficient Algorithms for Finding All Divisors of a Number
60. Understanding the Relationship Between GCD, LCM, and Divisors
61. Generating and Using Primes Efficiently in Algorithms
62. Pell’s Equation and Its Applications
63. Diophantine Equations: Solving Integer Solutions
64. Modular Multiplicative Inverses in Cryptography
65. Fast Factorization Algorithms: Pollard’s Rho Method
66. Factorization of Large Numbers Using Pollard's Rho and Elliptic Curves
67. RSA Cryptography: Using Modular Arithmetic for Encryption
68. Primality Testing with AKS Primality Test
69. Discrete Logarithms and Their Computational Difficulty
70. Shanks’ Baby-step Giant-step Algorithm for Discrete Logarithms
71. RSA Key Generation and Security: Number Theory in Cryptography
72. Efficient Use of Modular Inverses in Cryptographic Protocols
73. Finding Modular Roots: Applications in Cryptography
74. Fast Computation of Totients for Large Numbers
75. Chinese Remainder Theorem and Polynomial Systems
76. Generating Large Primes for Cryptographic Systems
77. Understanding Fermat’s Little Theorem and Its Generalization
78. Optimized Modular Exponentiation for Large Numbers
79. Applications of Number Theory in Hash Functions
80. Carmichael Numbers and Strong Pseudoprimes
81. Factorization of Large Numbers Using Quadratic Sieve
82. Understanding Fermat Pseudoprimes and Their Detection
83. Number Theoretic Algorithms in Big Integer Arithmetic
84. Sieve Algorithms for Counting Primes in Large Intervals
85. Primes and Factorization in Polynomial Time
86. Solving Modular Equations with Large Moduli
87. Computing Modular Square Roots Using Tonelli-Shanks
88. Efficient Algorithms for Finding Prime Factors of Large Numbers
89. Mathematical Induction in Number Theory Proofs
90. Primality Proving and the Role of Number Theory in Cryptography
91. Advanced Techniques for Generating Prime Numbers
92. Applications of Modular Arithmetic in Fast Fourier Transform
93. Number Theoretic Optimizations for String Matching Algorithms
94. Efficient Algorithms for Calculating Modular Inverses in Cryptography
95. Advanced Number Theory in Computational Geometry
96. Number Theoretic Algorithms in Graph Theory
97. Finding Prime Divisors Using Pollard’s Rho Method
98. Computing Large Integer Powers Using Modular Arithmetic
99. Optimization Techniques for Modular Exponentiation in Competitive Programming
100. Final Thoughts on Number Theory for Competitive Programming