KOL16E - Editorial

editorial
, , , , ,
1

PROBLEM LINK:

Practice
Contest

Editorialist: Soumik Sarkar

DIFFICULTY:

MEDIUM

PREREQUISITES:

Modular arithmetic, Fermat’s little theorem, Multiplicative order

PROBLEM:

Given a prime P (excluding 2 and 5), find the divisiblity test for P in terms of sums or alternate sums of groups of digits of minimum size.
Problem reduces to finding the smallest k for which 10^k \bmod P is either 1 or -1.

QUICK EXPLANATION:

The answer is guaranteed to be among the divisors of P-1.

EXPLANATION:

Finding the real problem

The first step is to determine what the problem is in mathematical terms. Consider the example of P=3 with a n digit number N. The number can be written in terms of its digits d_0, d_1, ..., d_{n-1} as

\begin{aligned} N &= d_{n-1} \cdot 10^{n-1} + d_{n-2} \cdot 10^{n-2} + ... + d_1 \cdot 10^1 + d_0 \cdot 10^0 \\ \therefore N \bmod 3 &= (d_{n-1} \cdot 10^{n-1} + ... + d_1 \cdot 10^1 + d_0 \cdot 10^0) \bmod 3 \\ &= (d_{n-1} \bmod 3) (10^{n-1} \bmod 3) + ... + (d_1 \bmod3) (10^1 \bmod 3) + (d_0 \bmod 3) (10^0 \bmod 3) \end{aligned}

Now 10 \bmod 3 = 1, which implies that 10^x \bmod 3 = (10 \bmod 3)^x = 1^x = 1 for all x\ge 1. So the above equation reduces to

\begin{aligned} N \bmod 3 &= (d_{n-1} \bmod 3) + ... + (d_1 \bmod3) + (d_0 \bmod 3) \\ \therefore N \bmod 3 &= (d_{n-1} + ... + d_1 + d_0) \bmod 3 \end{aligned}

…which is exactly what the 3-sum divisibility test is!

Let’s try another example with P = 7. If we try to split the number digit-wise as above, it will not work out like before because 10 \bmod 7 \ne 1. If we try groups of 2 digits, that will also fail. We will strike gold with groups of 3 digits. Let the number N have n such groups g_0, g_1, ... , g_{n-1}. Then as before,

\begin{aligned} N &= g_{n-1} \cdot 1000^{n-1} + g_{n-2} \cdot 1000^{n-2} + ... + g_1 \cdot 1000^1 + g_0 \cdot 1000^0 \\ \therefore N \bmod 7 &= (g_{n-1} \cdot 1000^{n-1} + ... + g_1 \cdot 1000^1 + g_0 \cdot 1000^0) \bmod 7 \\ &= (g_{n-1} \bmod 7) (1000^{n-1} \bmod 7) + ... + (g_1 \bmod 7) (1000^1 \bmod 7) + (g_0 \bmod 7) (1000^0 \bmod 7) \end{aligned}

Here 1000 \bmod 7 = -1, so 1000^x \bmod 7 = (1000 \bmod 7)^x = (-1)^x

\begin{aligned} N \bmod 7 &= (g_{n-1} \bmod 7)(-1)^{n-1} + ... + (g_1 \bmod 7)(-1)^{1} + (g_0 \bmod 3)(-1)^0 \\ \therefore N \bmod 7 &= ((-1)^{n-1}g_{n-1} + ... -g_3 + g_2 - g_1 + g_0) \bmod 7 \end{aligned}

…which is once again the divisibility test of 7.
Feel free to try out the same for other primes such as 11 or 13 on paper.

So the problem reduces to finding the smallest k for which 10^k \bmod P is either 1 or -1. If we find k for which 10^k \bmod P = 1 then the test is “k-sum” otherwise it is “k-altersum”.

Solving the problem

There is actually a term for the smallest k such that a^k \bmod P = 1.
It is termed the multiplicative order of a modulo P, denoted as ord_P(a).
From Fermat’s little theorem, we know that a^{P-1} \bmod P = 1.
Hence, 1 \le ord_P(a) \le P-1.
But here, P \le 2^{31}-1, so we cannot just iterate over all integers upto P to find the answer.

It can be proved that a^n \bmod P = 1 if and only if ord_P(a) \mid n. Refer to Theorem 6.1 of this excellent paper for proof.
Since we know that a^{P-1} \bmod P = 1, then ord_P(a) \mid (P-1).
Now the problem is greatly reduced, the order can only be found among the divisors of P, which can be enumerated in \mathcal{O}(\sqrt{P}).

This solves the problem for the “k-sum” case, but what about “k-altersum”?
If a^x \bmod P = -1, then clearly a^{2x} \bmod P = 1.
For the smallest such k, 2k = ord_P(a), hence k = ord_P(a)/2.
So for the altersum case, it is easy enough to check whether 10^{ord_P(10)/2} \bmod P = -1. However it is not necessary.
Let ord_P(a) = 2x. Then

a^{2x} \bmod P = 1 \\ (a^{2x}-1) \bmod P = 0 \\ (a^x+1)(a^x-1) \bmod P = 0 \\

This implies that either a^x \bmod P = -1 or a^x \bmod P = 1.
But a^x \bmod P \ne 1 since ord_P(a) = 2x.
Hence it is proved that if ord_P(a) is even, a^{ord_P(a)/2} \bmod P is guaranteed to be -1.

Bonus fact: This problem is the subject of Exercise 1.38 of the book Algorithms by S. Dasgupta, C. Papadimitriou, and U. Vazirani.

EDITORIALIST’S SOLUTION:

Editorialist’s solution can be found here.

2 Likes