Competition problem — Number theory

Library / /75 of 87

Number theory Difficulty 7.2 National Olympiad, round 2 Prove it Serbia

Problem:

A table of dimensions $n \times n$ , in whose cells are the numbers $1,2, \ldots, n^{2}$ (on each cell exactly one number and each number on exactly one cell), is called a threadwork if all products of $n$ numbers located on $n$ "scattered" cells give the same remainder upon division by $n^{2}+1$ . Does there exist a threadwork table for:

a. $n=8$ ;

b. $n=10$ ?

( $n$ cells are "scattered" if no two of them are in the same row or in the same column.)

Solution

Solution:

a.
Suppose that a threadwork table $8 \times 8$ exists and that the product of any 8 scattered numbers gives remainder $r$ modulo $8^{2}+1=65=5 \cdot 13$ . All numbers in the table can be divided into 8 disjoint octets of scattered numbers. Among these octets there is one that contains a multiple of the number 13 and one that does not contain such a multiple. The product of numbers in the first octet is divisible by 13, and in the second it is not, a contradiction. We conclude that a threadwork table $8 \times 8$ does not exist.

b.
The number $n^{2}+1=101$ is prime. Let us fill in the table as in the figure, where $g$ is a primitive root modulo 101. It is easily seen that the product of the numbers in any 10 scattered cells is congruent to $g^{495}(\bmod 101)$ , so this is an example of a threadwork table.

$g^{0}$	$g^{1}$	$g^{2}$	$\cdots$	$g^{9}$
$g^{10}$	$g^{11}$	$g^{12}$	$\cdots$	$g^{19}$
$g^{20}$	$g^{21}$	$g^{22}$	$\cdots$	$g^{29}$
$\vdots$	$\vdots$	$\vdots$		$\vdots$
$g^{90}$	$g^{91}$	$g^{92}$	$\cdots$	$g^{99}$

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement translated into English from sr; metadata (topic, difficulty) added by this project.