“In mathematics, modular arithmetic is a system of arithmetic for integers, where numbers “wrap around” upon reaching a certain value—the modulus.” – Wiki

The clock is a good example for modular arithmetic. Let’s say $12$’o clock means $0$. Then clock shows the following values, ${0,1,2,3,4,5,6,7,8,9,10,11,0,1,2,3…}$. Every time clock hits $12$, it wraps around to $0$. Since clock wraps around $12$, we say that $12$ is the Modulus.

General Concepts

In order to understand modular arithmetic, we need to know the following:

Modulo Operation $\%$

Modular arithmetic deals with Modulo operation. It has the symbol, “$\%$”. The expression $A \% B = C$ means that when we divide $A$ with $B$ we get the remainder $C$. In other words, the modulo operation finds the remainder. For example:

$5 \ \% \ 3 = 2$
$15 \ \% \ 5 = 0$
$24 \ \% \ 30 = 24$
$30 \ \% \ 24 = 6$
$4 \ \% \ 4 = 0$

Congruence Relation $\equiv$

In mathematics, saying that $A \ \equiv \ B \ \text{(mod M)}$ means that both $A$ and $B$ has same remainder when they are divided by $M$. For example,

$5 \ \equiv \ 10 \text{ (mod 5) }$
$2 \ \equiv \ 7 \text{ (mod 5) }$
$4 \ \equiv \ 10 \text{ (mod 3) }$

Range

In modular arithmetic with modulus $M$, we only work with values ranging from $0$ to $M-1$. All other values can be converted to the corresponding value from the range using Modulo operation. For example for $M=3$:

Properties of Modular Arithmetic

There are four properties of Modular Arithmetic that we need to learn.

Addition

$$ \text{if,}\ a\ \equiv\ b\ \text{(mod m)} \ \text{and,}\ c\ \equiv\ d\ \text{(mod m)} \ \text{then,}\ a + c\ \equiv\ b + d \ \text{(mod m)}$$

Meaning, if we have to find $(a_1+a_2+a_3…+a_n)\ \%\ m$, we can instead just find $( (a_1\ \% \ m ) + (a_2\ \% \ m ) +… (a_n\ \% \ m ) )\ \% \ m$.

For example, $( 13 + 24 + 44 )\ \%\ 3 = ( 1 + 0 + 2 )\ \%\ 3 = 3\ \%\ 3 = 0$.

Subtraction

$$ \text{if,}\ a\ \equiv\ b\ \text{(mod m)} \ \text{and,}\ c\ \equiv\ d\ \text{(mod m)} \ \text{then,}\ a – c\ \equiv\ b – d \text{(mod m)}$$

Meaning, if we have to find $(a_1-a_2-a_3…-a_n)\ \%\ m$, we can instead just find $( (a_1\ \%\ m ) – (a_2\ \%\ m ) -… (a_n\ \%\ m ) )\ \%\ m$.

For example, $( -14 – 24 – 44 )\ \%\ 3 = ( -2 – 0 – 2 )\ \%\ 3 = -4\ \%\ 3 = -1 \ \%\ 3 = 2$.

Multiplication

$$ \text{if,}\ a\ \equiv\ b\ \text{(mod m)} \ \text{and,}\ c\ \equiv\ d\ \text{(mod m)} \ \text{then,}\ a \times c\ \equiv\ b \times d\ \text{(mod m)}$$

Meaning, if we have to find $(a_1 \times a_2 \times a_3… \times a_n)\ \%\ m$, we can instead just find $( (a_1\ \%\ m ) \times (a_2\ \%\ m ) \times … (a_n\ \%\ m ) )\ \%\ m$.

For example, $( 14 \times 25 \times 44 )\ \%\ 3 = ( 2 \times 1 \times 2 )\ \%\ 3 = 4\ \%\ 3 = 1 \ \%\ 3 = 1$.

Division

Modular Division does not work same as the above three. We have to look into a separate topic known as Modular Inverse in order to find $\frac{a}{b}\ \%\ m$. Modular Inverse will be covered in a separate post.

For now just know that, $\frac{a}{b}\ not\equiv\ \frac{a\ \%\ m} {b\ \%\ m}\ \text{(mod m)}$. For example, $\frac{6}{3}\ \%\ 3$ should be $2$. But using the formula above we get $\frac{0}{0}\ \%\ 3$ which is undefined.

Coding Tips

Handling Negative Numbers

In some programming language, when modulo operation is performed on negative numbers the result is also negative. For example in C++ we will get $-5\ \%\ 4 = -1$. But we need to convert this into legal value. We can convert the result into legal value by adding $M$.

Therefore, in C++ it is better to keep a check for a negative number when doing modulo operation.

res = a % m;
if ( res < 0 ) res += m;

Modulo Operation is Expensive

Modulo Operation is as expensive as a division operator. It takes more time to perform division and modulo operations than to perform addition and subtraction. So it is better to avoid using modulo operation where possible.

One possible situation is when we are adding lots of values. Let's say that we have two variables $a$ and $b$ both between $0$ to $m-1$. Then we can write:

res = a + b;
if ( res >= m ) res -= m;

This technique will not work when we are multiplying two values.

Resource

1. Wiki - Modular Arithmetic - https://en.wikipedia.org/wiki/Modular_arithmetic
2. AoPS - Introduction to Modular Arithmetic - http://www.artofproblemsolving.com/wiki/index.php/Modular_arithmetic/Introduction

Problem

Given an integer $N$, find the Sum of Number of Divisors from $1 \to N$. That is, find $\sum_{i=1}^{N}NOD(i)$.

For example, find the Sum of Number of Divisors, $SNOD()$, when $N=5$. $SNOD(5)= NOD(1) + NOD(2) + NOD(3) + NOD(4) + NOD(5) = 1 + 2 + 2 + 3 + 2 = 10$.

Divisor Summatory Function

“In number theory, the divisor summatory function is a function that is a sum over the divisor function.” – Wiki

Divisor Summatory Function is defined as $D()$ in Wiki, but we will use $SNOD()$ in this article. Divisor Summatory Function finds Sum of Number of Divisors from $1 \to N$.

Brute Force Solution – $O(N^2)$ Approach

A simple solution is to run two nested loop which counts all divisors from $1 \to N$. It is simple but inefficient.

int SNOD( int n ) {
    int res = 0;
    for ( int i = 1; i <= n; i++ ) { // For each number from 1 - N
        for ( int j = 1; j <= i; j++ ) { // Find possible divisors of "i"
            if ( i % j == 0 ) res++;
        }
    }
    return res;
}

Using $NOD()$ - $O( N \times \frac{\sqrt{N}}{ln(\sqrt{N})})$ Approach

We can use the code for $NOD()$ to get the number of divisors for each integer from $1$ to $N$ instead of using a $O(N)$ loop. This will make it faster than the above solution.

int SNOD( int n ) {
    int res = 0;
    for ( int i = 1; i <= n; i++ ) {
        res += NOD(i);
    }
    return res;
}

Since $NOD()$ has same complexity as factorize(), the complexity for this code is $O( N \times \frac{\sqrt{N}}{ln(\sqrt{N})} )$.

Using Divisor List - $O(N)$ Approach

Suppose we are trying to find $SNOD(10)$. Let us write down the divisors for each integer between $1$ and $10$.

$NOD(1) = 1, : {1}$
$NOD(2) = 2, : {1 , 2}$
$NOD(3) = 2, : {1 , 3}$
$NOD(4) = 3, : {1, 2, 4}$
$NOD(5) = 2, : {1, 5}$
$NOD(6) = 4, : {1, 2, 3, 6}$
$NOD(7) = 2, : {1, 7}$
$NOD(8) = 4, : {1, 2, 4, 8}$
$NOD(9) = 3, : {1, 3, 9}$
$NOD(10) = 4, : {1, 2, 5, 10}$

So $SNOD(10) = 1 + 2 + 2 + 3 + 2 + 4 + 2 + 4 + 3 + 4 = 27$.

Now, look at the divisor list for each of integer between $1$ and $N$. Each divisor in the divisor lists contributes $1$ to the result. There are $27$ divisors in total.

How many times do we find $1$ in the divisor lists? It will appear once for every integer it can divide from $1$ to $N$. $1$ can divide $\frac{N}{1}$ numbers. So it appears $\frac{10}{1} = 10$ times.

Repeat for $2 \to N$. How many times do we find $2$? $2$ can divide $\frac{10}{2} = 5$ numbers, namely ${2,4,6,8,10}$. So it will appear $5$ times.

By repeating this from $1$ to $N$ we can find $SNOD(N)$.

int SNOD( int n ) {
    int res = 0;
    for ( int i = 1; i <= n; i++ ) {
        res += n / i;
    }
    return res;
}

We removed $NOD()$ from the code in line $4$ and replaced it with $\frac{n}{i}$.

Using Divisor Pairs - $O(\sqrt{N})$ Approach

Let us create another list. Instead of making divisor list, we will make "Ordered Divisor Pair" list for each value between $1$ to $N$. A divisor pair of value $X$ is a pair $(A, B)$ such that $A \times B = X$. Ordered pair means if $A \neq B$, then $(A, B)$ is a different pair than $(B, A)$.

$NOD(1) = 1, : (1,1)$
$NOD(2) = 2, : (1,2) (2,1)$
$NOD(3) = 2, : (1,3)(3,1)$
$NOD(4) = 3, : (1,4)(2,2)(4,1)$
$NOD(5) = 2, : (1,5)(5,1)$
$NOD(6) = 4, : (1,6)(2,3)(3,2)(6,1)$
$NOD(7) = 2, : (1,7)(7,1)$
$NOD(8) = 4, : (1,8)(2,4)(4,2)(8,1)$
$NOD(9) = 3, : (1,9)(3,3)(9,1)$
$NOD(10) = 4, : (1,10)(2,5)(5,2)(10,1)$

The "Ordered Divisor Pair" list is almost same as "Divisor List". The only difference is that each divisor $A$ is now paired with $B = \frac{X}{A}$.

Now, $NOD(X)$ represents number of ordered divisor pairs $(A,B)$ such that $A \times B = X$. So, $SNOD(N)$ is same as number of ordered divisor pairs such that $A \times B \leq N$.

How to find Number of Ordered Divisor Pairs $\leq N$?

We can find this by following three steps.

1. Find number of divisor pairs $(A, B)$ where $A < B$

What are the possible values for $A$? Can it ever be $> \sqrt{N}$? No. If $A > \sqrt{N}$, then with $B>A$, $B$ will be $> \sqrt{N}$ and $A \times B$ will be $ > N$. So $A$ can only be between $1$ and $\lfloor \sqrt{N} \rfloor$.

Let $u = \lfloor \sqrt{N} \rfloor$. Then for each value of $A$ between $1$ and $u$, what are the possible values of $B$?

For any value of $A$, there are $\frac{N}{A}$ possible values of $B$ for which $A \times B$ does not exceed $N$. For $N=10$ and $A=2$, there are $\frac{10}{2}=5$ possible values for $B$, and they are ${1,2,3,4,5}$. Multiplying $A=2$ with any of these values produces value $\leq N$. But we need $B > A$. So we omit ${1,2}$ from the list. We can only use ${3,4,5}$ as $B$.

So, for any value of $A$, there will be $\lfloor \frac{N}{A} \rfloor$ possible values of $B$. The values will be from $1$ to $\lfloor \frac{N}{A} \rfloor$. Out of those, we have to omit values that are $\leq A$. So we can use $\lfloor \frac{N}{A} \rfloor - A$ values for $B$.

For example, $N=10$. Then $u=\lfloor \sqrt{10} \rfloor = 3$. When $A=1$, number of legal values we can use is $\lfloor \frac{10}{1} \rfloor - 1 = 9$. Namely, $B$ can be one of ${2,3,4,5,6,7,8,9,10}$.

When $A=2$, legal values are $\lfloor \frac{10}{2} \rfloor - 2 = 3$. $B$ can be ${3,4,5}$.
When $A=3$, legal values are $\lfloor \frac{10}{3} \rfloor - 3 = 0$.

$A$ cannot be bigger than $u$. So number of $(A, B)$ pairs such that $A \times B \leq 10$ and $A < B$ is 12.

2. Multiply the result with $2$

Once we find the number of pairs $(A, B)$ such that $A < B$ and $A \times B \leq N$, we multiply that number with $2$. That is because we want to find the number of ordered divisor pairs. When $A \neq B$, each pair $(A, B)$ will occur in "Ordered Divisor Pair" list as $(B, A)$ again.

Once we double the number, our result contains the number of ordered pair $(A, B)$ such that $A \neq B$ and $A \times B \leq N$.

3. Add the number of pairs $(A, B)$ where $A = B$

We still did not count pairs where $A = B$ and $A \times B \leq N$. How many pairs can there be? Since $A$ must be between $1$ and $u$, there cannot be more than $u$ such pairs. The pairs will be $(1,1),(2,2)...(u,u)$.

Code for $O(\sqrt{N})$ Approach

int SNOD( int n ) {
    int res = 0;
    int u = sqrt(n);
    for ( int i = 1; i <= u; i++ ) {
        res += ( n / i ) - i; //Step 1
    }
    res *= 2; //Step 2
    res += u; //Step 3
    return res;
}

Reference

1. forthright48 - Number of Divisors of an Integer - https://forthright48.com/2015/07/number-of-divisors-of-integer.html
2. Wiki - Divisor Summatory Function - https://en.wikipedia.org/wiki/Divisor_summatory_function

Problem

Given an integer N, find the sum of all its divisors.

For example, find Sum Of Divisors (SOD) of $12$. $12$ has the following divisors, ${1, 2, 3, 4, 6, 12}$. So $SOD (12 ) = 1 + 2 + 3 + 4 + 6 + 12 = 28$.

Sum of Divisor Function: $SOD(N)$ or $\sigma_{1}(N)$

The Sum of Divisors of $N$ is also called $\sigma_{1}(N)$. That’s just a fancy way of saying Sum of Divisors of $N$. You can read more on it from Wiki. I will refer to Sum of Divisors of $N$ as either $\sigma_{1}(N)$ or $SOD(N)$. They both mean same.

Inefficient Solutions

Let us first look into some simple, but inefficient, solutions. These solutions are similar to the naive solutions we came up for “Number of Divisors of an Integer“.

Loop Till $N$

This is the simplest solution. We loop from $1 \to N$ and add all numbers that divide $N$.

Loop Till $\sqrt{N}$

If $N = A \times B$, where $A \leq B$, $A$ must be $\leq \sqrt{N}$. Using this fact we can run a loop from $1 \to \sqrt{N}$ and add all numbers that divide $N$ and their complements to result.

int SOD ( int n ) {
    int sqrtn = sqrt ( n );
    int res = 0;
    for ( int i = 1; i < sqrtn; i++ ) {
        if ( n % i == 0 ) {
            res += i; //"i" is a divisor
            res += n / i; //"n/i" is also a divisor
        }
    }
    if ( n % sqrtn == 0 ) {
        if ( sqrtn * sqrtn == n ) res += sqrtn; //Perfect Square.
        else {
            res += sqrtn; //Two different divisor
            res += n / sqrtn;
        }
    }
    return res;
}

At line $10$, we handle $sqrtn$ separately cause when $N$ is a perfect square we don't get different values for ${A, B}$ pair. For example, for $49$ we have a divisor pair $7times 7$. We need to add $7$ only once in our result.

Using Prime Factorization

It is possible to find $SOD(N)$ using the prime factorization of $N$. Let us see an example for it.

$Let \ N = 12,$
$SOD(12)= 1 + 2 + 3 + 4 + 6 + 12,$
$SOD(12) = (2^0 \times 3^0) + (2 ^1 \times 3^0) + (2^0 \times 3^1) + (2^2 \times 3^0) + (2^1 \times 3^1) + (2^2 \times 3^1),$
$SOD(12) = 2^0 ( 3^0 + 3^1 ) + 2^1 ( 3^0 + 3^1 ) + 2^2 ( 3^0 + 3^1 ),$
$SOD(12) = ( 2^0 + 2^1 + 2^2 ) \times ( 3^0 + 3^1)$

This pattern emerges with any value of N. More generally, if $N= p_1^{a_1} \times p_2^{a_2} \times ... p_k^{a_k}$, then $$ SOD(N) = (p_1^0 + p_1^1 + p_1^2 ... p_1^{a_1} ) \times (p_2^0 + p_2^1 + p_2^2 ... p_2^{a_2} ) \times ... (p_k^0 + p_k^1 + p_k^2 ... p_k^{a_k} ) $$Using this formula and our code for Prime Factorization, we can write the function $SOD(N)$. This code is similar to $factorize()$. We only need to modify it in few places.

int SOD( int n ) {
    int res = 1;
    int sqrtn = sqrt ( n );
    for ( int i = 0; i < prime.size() && prime[i] <= sqrtn; i++ ) {
        if ( n % prime[i] == 0 ) {
            int tempSum = 1; // Contains value of (p^0+p^1+...p^a)
            int p = 1;
            while ( n % prime[i] == 0 ) {
                n /= prime[i];
                p *= prime[i];
                tempSum += p;
            }
            sqrtn = sqrt ( n );
            res *= tempSum;
        }
    }
    if ( n != 1 ) {
        res *= ( n + 1 ); // Need to multiply (p^0+p^1)
    }
    return res;
}

For each prime we find in factorization, we need to find the corresponding value of $(p^0+p^1+...p^a)$. For that, we use tempSum in line $6$. It contains $p^0$ initially. Then for each successful division at line $8$, we increase the power of $p$ in line $10$ and add it to tempSum in line $11$. Eventually, we multiply the final sum to result at line $14$.

In line $17$, we check if we are left with a sole prime remainder. In this case, we know that $n$ is a prime so we simply multiply $p^0 + p^1 = 1 + n$ to the result.

Reference

1. Wiki - Divisor Function - https://en.wikipedia.org/wiki/Divisor_function
2. forthright48 - Number of Divisors of an Integer - https://forthright48.com/2015/07/number-of-divisors-of-integer.html
3. forthright48 - Prime Factorization - https://forthright48.com/2015/07/prime-factorization-of-integer.html