II OM - III - Task 2

What digits should be placed instead of zeros in the third and fifth positions in the number $ 3000003 $ to obtain a number divisible by $ 13 $?
Let the sought digits be denoted by $ x $ and $ y $, and write the number $ 30x0y03 $ in the form

We need to find such integers $ x $ and $ y $ that the number $ N $ is divisible by $ 13 $ and that the inequalities

are satisfied.

The numbers $ 10^6 $, $ 10^4 $, $ 10^2 $ give remainders $ 1 $, $ 3 $, $ 9 $ respectively when divided by $ 13 $, so

\[ 3 \cdot 10^6 = 13k_1 + 3, \]

\[ x \cdot 10^4 = 13k_2 + 3x, \]

\[ y \cdot 10^2 = 13k_3 + 9y, \]

where $ k_1 $, $ k_2 $, $ k_3 $ are natural numbers. Therefore,

\[ 30x0y03 = 3 \cdot 10^6 + x \cdot 10^4 + y \cdot 10^2 + 3 = 13k_1 + 3 + 13k_2 + 3x + 13k_3 + 9y + 3 \]

\[ = 13(k_1 + k_2 + k_3) + 3 + 3x + 9y + 3 \]

\[ = 13(k_1 + k_2 + k_3) + 3x + 9y + 6 \]

where $ k $ is a natural number.
For the number $ N $ to be divisible by $ 13 $, it is necessary and sufficient that the number $ x + 3y + 2 $ is divisible by $ 13 $, i.e., that $ x $ and $ y $ satisfy the equation

\[ x + 3y + 2 = 13m \]

where $ m $ is a natural number.
From the inequalities $ x \leq 9 $, $ y \leq 9 $, it follows that

\[ 0 \leq x + 3y + 2 \leq 38 \]

so the number $ m $ must satisfy the inequality $ 13m \leq 38 $, i.e., $ m $ can only be $ 1 $ or $ 2 $.
1° Taking $ m = 1 $, we get the equation for $ x $ and $ y $

\[ x + 3y + 2 = 13 \]

Under the constraints $ 0 \leq x \leq 9 $, $ 0 \leq y \leq 9 $, this equation has three integer solutions:

\[ (x, y) = (8, 1), (4, 2), (2, 3) \]

2° Taking $ m = 2 $, we get the equation

\[ x + 3y + 2 = 26 \]

and we obtain the solutions:

\[ (x, y) = (9, 5), (6, 6), (3, 7), (0, 8) \]

Thus, the problem has $ 7 $ solutions, corresponding to the numbers: $ 3080103 $, $ 3040203 $, $ 3020303 $, $ 3090503 $, $ 3060603 $, $ 3030703 $, $ 3000803 $.
Note. In problem 35, it was about changing the digits of a certain specified number. Let's consider two more general examples of such problems:
I. Given a natural number $ N $ not divisible by a prime number $ p $ and having a digit $ 0 $ in the $ k $-th decimal place. Can the zero be replaced by a digit $ x $ so that the new number is divisible by $ p $?
First, note that if $ p $ is $ 2 $ or $ 5 $, the problem has no solution. Therefore, we assume in the following that $ p \ne 2 $ and $ p \ne 5 $.
When we place the digit $ x $ in the $ k $-th decimal place of the number $ N $, the resulting number $ N(x) $ is given by the formula

\[ N(x) = N + x \cdot 10^{k-1} \]

Consider the values of the function $ N(x) $ when $ x $ takes the values $ 0, 1, 2, \ldots, (p - 1) $:

\[ N(0), N(1), N(2), \ldots, N(p-1) \]

Each of the $ p $ numbers in the sequence (2) gives a different remainder when divided by $ p $. Indeed, according to formula (1), the difference between two numbers in the sequence (2) is given by

\[ N(i) - N(j) = (i - j) \cdot 10^{k-1} \]

When $ i \ne j $, this number is not divisible by $ p $, because the factor $ (i - j) $ is non-zero and less in absolute value than $ p $, and the factor $ 10^{k-1} $ has only the prime divisors $ 2 $ and $ 5 $. Therefore, the numbers $ N(i) $ and $ N(j) $ give different remainders when divided by $ p $.
Since the remainders of the numbers in the sequence (2) are different and there are $ p $ of them, one and only one of these remainders is zero, i.e., one and only one of the numbers in the sequence (2) is divisible by $ p $; let this number be $ N(x_0) $.
If $ x_0 \leq 9 $, then $ x_0 $ gives a solution to the problem.
If $ x_0 > 9 $, the problem has no solution.
Hence the conclusion:
a) When $ p = 3 $, the problem always has three solutions; the sought digits are either $ 1 $, $ 4 $, $ 7 $ or $ 2 $, $ 5 $, $ 8 $.
b) When $ p = 7 $, the problem has either two solutions - the digits $ 1 $, $ 8 $ or $ 2 $, $ 9 $, or one solution - one of the digits $ 3 $, $ 4 $, $ 5 $, $ 6 $.
c) When $ p \geq 11 $, the problem may have one solution or no solution. If $ p = 11 $, the first of these cases occurs, for example, for the number $ 10 $, and the second case is given by the number $ 109 $.
II. Given a natural number $ N $ not divisible by a prime number $ p \geq 11 $ and having a digit $ 0 $ in the $ k $-th and $ l $-th decimal places. Can the zeros be replaced by digits $ x $ and $ y $ so that the new number is divisible by $ p $?
When we place the digit $ x $ in the $ k $-th decimal place and the digit $ y $ in the $ l $-th decimal place of the number $ N $, we obtain the number $ N(x, y) $ given by the formula

\[ N(x, y) = N + x \cdot 10^{k-1} + y \cdot 10^{l-1} \]

Consider the values of the function $ N(x, y) $ obtained by substituting $ 0, 1, 2, \ldots, (p - 1) $ for $ x $ and $ y $. We get $ p^2 $ numbers:

\[ N(0, 0), N(0, 1), \ldots, N(0, p-1), N(1, 0), N(1, 1), \ldots, N(1, p-1), \ldots, N(p-1, 0), N(p-1, 1), \ldots, N(p-1, p-1) \]

We state, as in problem I, that in each row and each column of this table there is one and only one number divisible by $ p $; let the number in the $ i $-th row be denoted by $ N(i, y_i) $.
The table thus contains $ p $ numbers divisible by $ p $; they are the numbers

\[ N(0, y_0), N(1, y_1), N(2, y_2), \ldots, N(p-1, y_{p-1}) \]

where the sequence of numbers $ y_0, y_1, y_2, \ldots, y_{p-1} $ contains the same numbers as the sequence $ 0, 1, 2, \ldots, (p - 1) $, but in a different order. Note also that $ y_0 $ is certainly not equal to $ 0 $, since the number $ N(0, 0) = N $, by assumption, is not divisible by $ p $.
The number $ N(i, y_i) $ in the sequence (4) gives a solution to the problem only if $ i \leq 9 $ and $ y_i \leq 9 $. It is easy to count how many such numbers the sequence (4) can contain. They should be sought among the numbers

\[ N(0, y_0), N(1, y_1), N(2, y_2), \ldots, N(9, y_9) \]

In the case where none of the numbers $ y_0, y_1, \ldots, y_9 $ is greater than $ 9 $, the problem has $ 10 $ solutions given by the numbers in the sequence (5). This is the maximum possible number of solutions.
If among the numbers $ y_0, y_1, \ldots, y_9 $ there are numbers greater than $ 9 $ (there can be at most $ p - 10 $ such numbers), the corresponding terms should be crossed out from the sequence (5). The problem thus has at least $ 10 - (p - 10) $, i.e., $ 20 - p $ solutions.
Hence the conclusion:
a) When $ p = 11 $, the problem has at least $ 9 $ solutions. An example of the case where there are the maximum number of $ 10 $ solutions is the number $ 101015 $.
b) When $ p = 13 $, the problem has at least $ 7 $ solutions; the case where there are only $ 7 $ solutions was in problem 35.
c) When $ p = 17 $, we have at least three solutions.
d) When $ p = 19 $, the problem has at least one solution.
e) When $ p \geq 23 $, the problem may have no solutions. An appropriate example for the case $ p = 23 $ can be found easily if one considers that the number $ 10^{22} $ gives a remainder of $ 1 $ when divided by $ 23 $. We propose this as an exercise.