Number Theory for Competitions

An overview of the number theory topics that appear most often at the district, national and SIO (Serbian informatics olympiad) level: divisibility, prime numbers, GCD, modular arithmetic and fast exponentiation. Every topic has a short reminder and a link to a detailed lesson; modular arithmetic is explained here in full.

Before you start: prerequisites – Mathematical algorithms.
How to learn: type in and run every example, and solve the tasks at the end on your own first; open the hint and the solution only after that. All programs are in C++.

Divisibility and remainders

The number a is divisible by b if a % b == 0. The remainder of division is the basis of many tasks: the digits of a number (% 10), parity (% 2), cycles (the day of the week is % 7). Careful: in C++ the remainder of a negative number is negative (-7 % 3 == -1), so for the mathematical remainder you write ((a % m) + m) % m.

Prime numbers

  • Checking whether a number is prime: division up to √n – Prime numbers and factorisation.
  • All the prime numbers up to 107: the sieve of Eratosthenes, complexity O(n log log n).
  • Factorising into primes and the number of divisors: if n = p₁^a₁ · … · pₖ^aₖ, the number of divisors is (a₁+1)·…·(aₖ+1).

GCD and LCM

Euclid's algorithm: gcd(a, b) = gcd(b, a % b), complexity O(log min(a, b)). The LCM is a / gcd(a, b) * b. C++17 has ready-made functions gcd and lcm (the header <numeric>). In detail: Finding the GCD and LCM.

Modular arithmetic

When the exact result is huge (the number of paths, the number of arrangements…), the task asks for the remainder of division by some number m, most often 109 + 7 (a prime number). These rules hold:

  • (a + b) mod m = ((a mod m) + (b mod m)) mod m
  • (a − b) mod m = ((a mod m) − (b mod m) + m) mod m
  • (a · b) mod m = ((a mod m) · (b mod m)) mod m

That is why the remainder is taken after every operation, so intermediate results stay small. The product of two numbers smaller than 109+7 is smaller than 1018 and fits in a long long.

Division does not work by the same rule. Instead of dividing by a, you multiply by the modular inverse a⁻¹ – the number for which a · a⁻¹ mod m = 1. When m is prime and a is not divisible by m, by Fermat's little theorem a⁻¹ = am−2 mod m.

#include <iostream>
using namespace std;

const long long MOD = 1000000007;

long long power(long long a, long long b) {       // a^b mod MOD
    long long r = 1;
    a %= MOD;
    while (b > 0) {
        if (b & 1) r = r * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return r;
}

long long inverse(long long a) { return power(a, MOD - 2); }

int main() {
    long long a, b;
    cin >> a >> b;
    cout << (a + b) % MOD << "\n";
    cout << ((a - b) % MOD + MOD) % MOD << "\n";      // never negative
    cout << a % MOD * (b % MOD) % MOD << "\n";
    cout << a % MOD * inverse(b) % MOD << "\n";       // "a / b" modulo
    return 0;
}

For a = 10, b = 4 the last line gives 500000006 – that is the number x for which 4 · x ≡ 10 (mod 109+7), that is, "10/4 = 2.5" modulo.

Fast exponentiation

ab mod m for b up to 1018 is calculated in O(log b) steps, by halving the exponent (the function power above). A step-by-step explanation: The fast exponentiation algorithm, and the recursive version in the lesson Factorial, power and GCD – recursively.

What next

Practice tasks

Every task has an example, a hint and a solution. The solutions have been checked on the examples from the text.

TASK 01Difficulty: easy

The day of the week

Today is the day with the order number d (0 = Monday, …, 6 = Sunday). Which day will it be after k days? k can also be negative (how many days ago), |k| ≤ 1018. Print the order number of the day.

Example 1

Input

0 10

Output

3

Example 2

Input

2 -9

Output

0
TASK 02Difficulty: medium-hard

The number of divisors

Read a natural number n (n ≤ 1012) and print how many divisors it has.

Example 1

Input

12

Output

6

Example 2

Input

1000000000000

Output

169
TASK 03Difficulty: harder

A sum of fractions modulo

Calculate 1/1 + 1/2 + … + 1/n modulo 109+7 (n ≤ 106), that is, print Σ i⁻¹ mod p.

Example 1

Input

1

Output

1

Example 2

Input

3

Output

833333341
Common mistakes and tips
  • Always take the remainder after a multiplication; otherwise even a long long overflows.
  • Fix a negative remainder with ((x % m) + m) % m.
  • The inverse through Fermat's theorem works only for a prime modulus.
  • The loop "up to √n" is written as p * p <= n (without sqrt and rounding errors).

Check your knowledge

Open the quiz

Mini quiz: number theory

1. What is -7 % 3 in C++?




2. How many divisors does the number 36 = 2² · 3² have?




3. When is the inverse a⁻¹ = a^(m−2) mod m correct?