Number Theory

Number Theory is just a fancy name for playing with integers (whole numbers). No fractions, no decimals – just pure numbers like 1, 5, 42, -10.

By now, you should be familiar with division, taking the remainder when dividing, and identifying patterns related to these operations.

Greatest Common Divisor (GCD)

The GCD of two numbers is the largest number that divides both of them without leaving a remainder.

For example:

GCD(12, 18) = 6 (Both can be divided by 1, 2, 3, 6, and then 6 is the biggest)
GCD(7, 13) = 1 (They share nothing except 1)

How to calculate it?

It is fairly simple to calculate GCD(a, b) if we don’t care about efficiency. One could iterate from 1 to the \(max(a, b)\) and check which number was the last to divide both of the numbers \(a\) and \(b\), without remainder.

Time complexity of this approach is \(\mathcal{O}(max(a, b))\).

How to calculate it efficiently? (Euclidean Algorithm)

We can do much better. Don’t test every number! There is a 2000-year-old hack: GCD(a, b) is the same as GCD(b, a % b). You keep taking the remainder until one number becomes 0.

// Recursive way (The "standard" way)
int gcd(int a, int b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}

Tip

You could also just use the built-in function for gcd. For newer versions (C++17 and onwards), there is a function gcd(int, int). For older versions of C++, you can use __gcd(int, int).

Least Common Multiple (LCM)

The LCM is the smallest number that both numbers can divide into.

Think of it as the “first time their multiples meet”.

Multiples of 4: 4, 8, 12, 16…
Multiples of 6: 6, 12, 18…
LCM(4, 6) = 12

Formula

You don’t need a loop to find this. Use the GCD!

\[ \text{LCM}(a, b) = \frac{(a \times b)}{\text{GCD}(a, b)} \]

Caution

To avoid overflow (number getting too big), divide first: (a / gcd(a,b)) * b.

int lcm(int a, int b) {
    if (a == 0 || b == 0) return 0;
    return (a / gcd(a, b)) * b;
}

Example problems

Simplifying Fractions

You are given a fraction, say \(18/24\). You need to output it in its simplest form.

Solution

To simplify a fraction, divide both the top (numerator) and bottom (denominator) by their GCD.

#include <iostream>
#include <numeric> // for std::gcd
using namespace std;

int main() {
    int num = 18;
    int den = 24;
    
    int common = std::gcd(num, den);
    
    num /= common;
    den /= common;
    
    cout << num << "/" << den; // Outputs: 3/4
}

By removing the biggest common factor (6), we get the simplest version immediately.

The Meeting Point

Two lights flash at different intervals.

Light A flashes every 12 seconds.
Light B flashes every 15 seconds.

They just flashed together. When will they flash together again?

Solution

We are looking for a time \(T\) that is a multiple of both 12 and 15. Specifically, the first (smallest) time this happens. This is exactly LCM.

#include <iostream>
#include <numeric>
using namespace std;

int main() {
    int a = 12;
    int b = 15;
    
    // LCM formula: (a * b) / GCD(a, b)
    int meet_time = std::lcm(a, b); 
    
    cout << "They meet again in " << meet_time << " seconds."; 
    // Output: 60 seconds
}