There is one nonzero digit in every cell of $2017\times 2017 $ table. On the board we writes $4034$ numbers that are rows and columns of table. It is known, that $4033$ numbers are divisible by prime $p$ and last is not divisible by $p$. Find all possible values of $p$.
HIDE: Example Example for $2\times2$. If table is |1|4| |3|7|. Then numbers on board are $14,37,13,47$Problem
Source: Moscow Math Olympiad 2017, Grade 11, P11
Tags: combinatorics, number theory
MellowMelon
25.04.2017 18:44
The answer is $p = 2$ or $p = 5$. These are easily shown to work by making all digits equal $p$, except the bottom left corner is 1.
Now suppose $\gcd(p, 10) = 1$. Let $a_{i,j}$ be the digit in row $i$ and column $j$, $r_i$ be the number formed by row $i$, and $c_j$ be the number formed by column $j$. Then
\[ \sum_{i=1}^{2017} \sum_{j=1}^{2017} 10^{4034-i-j} a_{i,j} = \sum_{i=1}^{2017} 10^{2017-i} r_i = \sum_{j=1}^{2017} 10^{2017-j} c_j. \]Since $\gcd(p, 10) = 1$, the conditions mean one of the last two sums is 0 mod $p$ and the other is nonzero mod $p$, contradiction.
The trick to solve this problem is identical to the one to solve this one:
Quote:
Let $n$ be a positive integer. Each space of an $(n+2) \times (n+2)$ grid is filled with a real number. A row or column is called good if its entries read in order are $a_1, a_2, \ldots, a_{n+2}$ and there exists a polynomial of degree at most $n$ such that $P(k) = a_k$ for $1 \leq k \leq n+2$. Suppose all rows are good, and all but one of the columns are good. Show that actually all the columns are good.
I proposed this for the USAMTS a long time ago, although it appeared in a watered down form as 5/1/24.