Number Theory #2

By Sadek Mohammed

Modular Arithmetic

We have investigated modulus (%) as a way to get the remainder after divison, but what does modulus do?

Clock Model

The easiest way to imagine the workflow of the modulus is to imagine the clock. A clock has 12 hours, where certain hours repeat. To illustrate:

13 pm corresponds to 1 (13 - 12) pm.
14 pm corresponds to 2 (14 - 12) pm.
12 pm corresponds to 0 (12 - 12) pm.

What can we get from that.

Imagine that you have a rotated number line, where it has the following $12$ marks: $0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11$ . Look at the following:

If we move one step, we would be at place $1$ .
If we move twelve steps, we would be at place $1$ , again.
Start from the beginning again, and then move 5 places. You are at position 5.
Move 24 places, you are at position 5 for the third time.

We can conclude that multiples of the modulus cause complete cycles around the number line. That means they could be eliminated when calculating the modulus.

, but how to define that correspondence in a precise way?

Division model

Any two integers $n$ and $m$ could be put in the following formula.

n = q m + r

Some Facts:

When there is no remainder, a number $n$ could be expressed in terms of $m$ as the following $n = q m$ . We can proof that numbers which are divisble by a third number have a difference that is divisble by that number, too.

a = q n b = l n a - b = q n - l n = (q - l) n

The same holds for addition, too, by a similar proof.

Some terms:

n $\Rightarrow$ dividend (the number that is divided)
m $\Rightarrow$ divisor (the number that divides another one)
q $\Rightarrow$ quotient (the integer part of the result of division)
r $\Rightarrow$ remainder (the result of multiplying the decimal part of the divisor)

Congurence:

Two integers are said to be congruent (mod x) if they have the same remainder ( $r$ ) when divided by x. For example:

$6 \equiv 10 (mod 4)$ as $6 = 4 \cdot 1 + 2$ and $10 = 4 \cdot 2 + 2$ .
$540 \equiv 180 (mod 360)$ as $180 = 0 \cdot 360 + 180$ and $540 = 1 \cdot 360 + 180$ . (Co-terminal angles).

Range of a modulus

If you evaluate a number $mod m$ , you have always to output a number between $0$ and $m - 1$ (Just think of it).
If a number is evaluated $mod m$ , where m is bigger than it, the output is the number itself.
If a number is larger than $m$ , just subtract $m$ 's till you get a number smaller than $m$ , and do the same in the previous point.

Distribution

On solving some problems, the problem statement sometimes requires that you output the answer mod a certain number $m$ as the number may get too big. For example, take the following:

Problem Statement

A certain person has a number of $n$ categories of clothes ( $1 \leq n \leq 1 0^{5}$ ), where each category has $a_{i}$ pieces ( $1 \leq a_{i} \leq 1 0^{18}$ ). You have to output the number of different combinations of clothes. (Since the number of combinations could be huge, output it $mod 1 0^{9} + 7$ )

Sample Input

3 3 2 1

Sample Output

Explanation of Sample

The person has 3 categories: shoes, trousers, and shirts. He has 3 shoes, 2 trousers, and a single shirt. That means that the total number of possibilities is $3 \cdot 2 \cdot 1 = 6$ .

How to solve ?

Look at the following code:

// Initialize the vairables (Notice that ans starts with 1)
int ans = 1, n = 0, inp = 0;
// Take the number of clothes categories
cin >> n;
while (n--)
{
    // Take the number of pieces of each category
     cin >> inp;
    // Multiply them by the answer (1)
    ans *= inp;
}
// Output the answer
cout << ans;

But there is a single problem. We need to ouptut the number $mod m$ . In our case, the numbers are too big. Let's do some maths.

$a_{i}$ could reach $1 0^{1} 8$ , where that means that we need to store it in long long.
$an s$ , in the worst case could react $a_{i}^{n} = 1 0^{18}^{1 0^{5}} = 1 0^{18 \cdot 1 0^{5}}$ , which is far too big to store in a $64$ -bit long long.

Fortunately, the problem statement is the supreme savior. If we take the answer repeatedly $mod 1 0^{9} + 7$ , we would always obtain an answer that is always less than $1 0^{9} + 7$ that perfectly fits in a normal $32$ -bit integer. To do so we need to have some knowledge about the distribution of operations.

Distribution Rules

$(a + b) mod m = ((a mod m) + (b mod m)) mod m$
$(a - b) mod m = ((a mod m) - (b mod m)) mod m$
$(a \times b) mod m = ((a mod m) \times (b mod m)) mod m$

Proof of distributive addition rule:

a = x_{1} \cdot m + r_{1} b = x_{2} \cdot m + r_{2} ((a mod m) + (b mod m)) = ((r_{1} + r_{2}) mod m) (a + b) mod m = (x_{1} \cdot m + x_{2} \cdot m + r_{1} + r_{2}) mod m = (r_{1} + r_{2}) mod m (By neglecting multiples : clock model)

You can look for proofs for subtraction and multiplication, too.

New code

int n = 0;
// Notice that both ans and inp became long long 
long long ans = 1, inp = 0;
// Note that ans is initialized by 1 (Multiplicative Identity)
cin >> n;
while (n--)
{
    cin >> inp;
    // Take inp mod 
    inp %= mod; 
    ans *= inp;
    // Take ans mod
    ans %= mod; 
}
cout << ans;

Notice the following:

inp should be long long as it has an upper bound of $1 0^{18}$ .
ans should be long long because of the third line in the loop.
We should take the mod each time to satisfy the following equation.

(a_{1} \cdot a_{2} \cdot a_{3}) mod m = ((a_{1} mod m) \cdot (a_{2} mod m) \cdot (a_{3} mod m)) mod m

Modulus of negative numbers

Taking modulus of negative numbers differs according to the language; however, in cpp, we do the following:

Take the normal modulus.
Add the value of the modulus.
Retaking the normal modulus.

int all_mod (int n, int m)
{
    return ((n % m) + m) % m;
}

This method works for positive numbers, too. That's because all we do is neglecting the multiples of the modulus as in the clock model.

The greatest common divisor.

What is the gcd.

Imagine the following numbers:

$12 = 2 \cdot 2 \cdot 3$
$8 = 2 \cdot 2 \cdot 2$

In the previous session, we have observed that 12 must have 6 divisors: $1, 12, 3, 4, 6, 2$ . On the contrary, 8 must have 4 divisors: $1, 8, 2, 4$ .

We could observe that they have 3 common divisors: $1, 2, 4$ . The greatest commond divisor (gcd) is $4$ .

How could I find the gcd of two numbers?

Let a be a number with prime divisors: $p_{i}^{q}, p_{i + 1}^{q_{1}}, p_{i + 2}^{q_{2}}, \dots p_{n}^{q_{n}}$ and b be a number with the following divisors: $p_{i}^{m}, p_{i + 1}^{m_{1}}, p_{i + 2}^{m_{2}}, \dots p_{n}^{m_{n}}$ . Let their gcd be c.

c = p_{1}^{m i n (q_{1}, m_{1})} \cdot p_{2}^{m i n (q_{2}, m_{2})} \dots p_{n}^{m i n (q_{n}, m_{n})}

How to do that on a computer?

Euclidean Theorem.

Since each number that divides $a$ and $b$ divides their difference $a - b$ . We can find the gcd this way:

g cd (990, 720) = g cd (990 - 720, 720) g cd (720, 270) = g cd (720 - 270, 270) g cd (450, 270) = g cd (450 - 270, 270) g cd (270, 180) = g cd (270 - 180, 180) g cd (180, 90) = g cd (180 - 90, 90) g cd (90, 90) = g cd (90 - 90, 90) g cd (90, 0) = 90

Extended Euclidean Theorem.

If you could remember the clock model, we were extensively subtracting 12s from the hour to get its counterpart in the range $0, \cdot, 11$ . The same goes with a great improvement to the euclidean theorem.

g cd (990, 720) = g cd (720, 990 mod 720) g cd (720, 270) = g cd (270, 720 mod 270) g cd (270, 180) = g cd (180, 270 mod 180) g cd (180, 90) = g cd (90, 180 mod 90) g cd (90, 0) = 90

Code

The extended euclidean algorithm can be implemented as follows:

int gcd(int a, int b)
{
    if (a < b)
    {
        swap(a, b);
    }
    if (b == 0)
    {
        return 0;
    }
    return gcd(b, a%b);
}

The least common multiple.

What is the lcm?

See the following:

Multiples of 14: $14, 28, 42, 56, 70, \dots, 140$
Multiples of 35: $35, 70, 105, 140, \dots, 350$

There can be common multipes: 70, 140, etc; however, the least one of them is $70$ .

But how could that happen?

$14 = 2 \cdot 7$
$35 = 5 \cdot 7$

Observe the following:

LCM: $70 = 2 \cdot 5 \cdot 7$ .
Another common multiple: 140: $2^{2} \cdot 5 \cdot 7$ .

How could I find the gcd of two numbers?

c = p_{1}^{m a x (q_{1}, m_{1})} \cdot p_{2}^{m a x (q_{2}, m_{2})} \dots p_{n}^{m a x (q_{n}, m_{n})}

How to do that on a computer?

When we take the gcd for two numbers like 42 $(2 \cdot 3 \cdot 7)$ and 28 $(2^{2} \cdot 7)$ .

Their GCD & LCM

Let's look at the exponents of the prime factors:

2: 42 has 1 as the exponent while 28 has 2 as the exponent.
3: 42 has 1 as the exponent while 28 has 0 as the exponent.
7: Both 42 and 7 has 1 as the exponent.

This implies that:

Since GCD uses the minimums, the GCD = $2 \cdot 7$ , which is 14.
Since LCM uses the maximums, the LCM = $2^{2} \cdot 3 \cdot 7$ , which is 84.

Let's look at the following:

42: $(2 \cdot 3 \cdot 7)$ .
28: $(2^{2} \cdot 7)$ .
14 (GCD): $2 \cdot 7$ .
84 (LCM): $2^{2} \cdot 3 \cdot 7$ .
1176 ( $42 \cdot 28$ ): $2^{3} \cdot 3 \cdot 7^{2}$ ).

It can be concluded that result of multiplying the two numbers has all their factors, GCD has the minimum factors only, and LCM has the maximum factors, so if we can find the GCD and a way to remove the minimum factors, we could find the maximum factors, lcm.

l c m (a, b) = \frac{a \cdot b}{g cd ( a , b )}

When using this with the above way of calculating the gcd, the process becomes very efficient.