Number Theory Basics
Quick introduction
Hi again ! Time for some math ! We will dive into some basics of number theory that will help you solve competitive programming problems. Let's go ! Basically, number theory studies integers, based on the divisibility relation and its many properties, but...
What is divisibility ?
Quick reminder from primary school, we say that an integer divides another integer whenever there exists some integer such that . For example divides , divides , divides , but doesn't divide and doesn't divide . We can also use the notation which means divides . For example but . The following expressions describe the same property :
- divides .
- is a divisor of .
- is a multiple of .
- for some integer .
Here are some nice properties of divisibility :
- for all integers .
- and for all integers .
- and implies that .
Prime Numbers
We say that a positive integer is prime number if it has exactly positive divisors, and itself. For example are primes, but are not.
Euclidean Division (Euclid’s Division Lemma)
Remember the Euclidean Division algorithm you studied at school ? He will become our best friend now ! Consider that you are dividing by . You would obtain as a result, and as remainder, and just write . Euclid's division lemma says that for any integers , we can find unique integers such that . Pretty easy as you know this since primary school, but how can we use this to solve hard problems ? You probably know that in C++ and Python, gives us the remainder , hence to check if a number is divisible by another one, we just have to compute the division remainder and check if it is equal to zero.
Hence we can find the positive divisors of a positive integer using the following algorithm :
for i from 1 to N :
if N%i == 0 :
print(i)Also we can check if a number is prime by simply counting the number of divisors, and checking if it is equal to 2.
On the divisors listing algorithm
There's obviously a better way to find all the positive divisors of a positive integer, notice that if we write , then we have one of the following cases :
Hence we can see we can list all the divisors of by simply listing the pairs such that divides and , giving us a better time complexity of about .
for i from 1 to floor(sqrt(N)) :
if N%i == 0 :
print(i)
print(N/i)Notice that they are not ordered, but you can easily fix this by storing the values in an array in an ordered way.
GCD and LCM
GCD stands for Greatest Common Divisor, such that is the greatest integer that divides both and . We also say that and are coprime when . Example : , . .
LCM stands for Least Common Multiple, such that is the smallest positive integer that is a multiple of both and . Example : , . .
Nice property : .
Modular Arithmetic Basics
We write when the remainders obtained when dividing by and by are the same. Examples :
It has almost the same properties as algebraic equality :
- and
- and
- and
Warning : This does not always work for division, and involves modular inverses.
It follows from the definition that is the same as , hence we get the formal definition : if and only if .
Basic Example :
Show that if and , then holds true.
As , and , then by multiplication . And since , by addition we get that .
External Resources
Books, Websites and Notes
- Olympiad Number Theory Through Challenging Problems's 2 first chapters.
- Competitive Programmer’s Handbook's chapter 21.
- The Art of Modular Arithmetic
- MODNT's chapters 1 and 2
- Mathraining.be (fr) chapters 1 to 3
Videos
- Computations Modulo P in Competitive Programming - Errichto
- AMO Summer Camp 2023 - Number Theory Lecture
- AMO Summer Camp 2023 - Number Theory Practice