4. Let's say a subset $\mathrm{P}$ of the set $\mathrm{M}=\{1,2,3, \ldots, 42\}$ is halfish if it contains 21 elements and each of the 42 numbers in the sets $\mathrm{P}$ and $\mathrm{Q}=\{7 x ; x \in \mathrm{P}\}$ gives a different remainder when divided by 43. Determine the number of halfish subsets of the set M.

(Josef Tkadlec)
SOLUTION. We will treat all numbers as residue classes modulo the prime number 43.

First, we note that the sets $\mathrm{P}$ and $\mathrm{Q}$ form a disjoint partition of the set $\mathrm{M}$. Let $\mathrm{P}$ be the half-set and let $x \in \mathrm{P}$, for which then $7 x \in \mathbf{Q}$.

We will show that $7^{2} x \in \mathrm{P}$. If we assume the opposite, that $7^{2} x \in \mathrm{Q}$, then there exists $y \in \mathrm{P}$ such that $7^{2} x=7 y$. According to the guiding problem $\mathrm{N} 2$, such a $y$ is uniquely determined, and thus it is $7 x$. Since $7 x \notin \mathrm{P}$, we get the required contradiction.

Then, of course, $7^{3} x \in \mathrm{Q}$, and by repeating the previous argument, we will show that $7^{4} x \in \mathrm{P}$, and subsequently $7^{5} x \in \mathrm{Q}$. In principle, we could continue this way further, however, $7^{6} x \equiv 49^{3} x \equiv 6^{3} x \equiv x(\bmod 43)$, thus closing the "cycle". The cyclic sextet (of different) numbers $\left(x, 7 x, 7^{2} x, 7^{3} x, 7^{4} x, 7^{5} x\right)$ has the arrangement $(\mathrm{P}, \mathrm{Q}, \mathrm{P}, \mathrm{Q}, \mathrm{P}, \mathrm{Q})$.

We will now divide the set $\mathrm{M}$ into seven such cyclic sextets as

$$
\begin{array}{ccc}
(1,7,6,42,36,37), \quad(2,14,12,41,29,31), & (3,21,18,40,22,25), \\
(4,28,24,39,15,19), & (5,35,30,38,8,13), & (9,20,11,34,23,32),
\end{array}
$$

$$
(10,27,17,33,16,26) \text {. }
$$

Each of these sextets will have the arrangement either $(P, Q, P, Q, P, Q)$ or $(Q, P, Q, P, Q, P)$, and each such choice will determine the sets $P$ and $Q$ satisfying the conditions of the problem. The number of possibilities is thus $2^{7}=128$.

Note. In fact, it is not necessary to find seven cyclic sextets directly. It is enough to prove the existence of such a partition of the set $\mathrm{M}$. This follows from two partial statements:

(i) Every element of $\mathrm{M}$ is an element of some sextet.

(ii) If two sextets have one element in common, then they have all elements in common.

The validity of the first statement is immediate and for the proof of the second, it is enough to realize that according to the construction, the sextets are closed under multiplication by 7, and one common element thus "generates" the other five common elements by successive multiplication by seven.

GUIDING AND ADDITIONAL PROBLEMS:

N1. Given a prime number $p$, the set $\mathrm{U}=\{0,1, \ldots, p-1\}$, and a natural number $a$ coprime with $p$. Show that no two numbers from the set $\mathrm{V}=\{0 a, 1 a, \ldots,(p-1) a\}$ give the same remainder when divided by the prime number $p$. [Assume the opposite and lead to a contradiction that $p$ divides the difference of some two numbers from the set V.]

N2. [“The septuple is unique”] In the notation of the problem, show that for each $x \in \mathrm{M}$ there exists exactly one $y \in \mathrm{M}$ such that $x \equiv 7 y(\bmod 43)$ (read as, $x$ gives the same remainder as $7 y$ when divided by 43"). [According to N1 for $p=43$ and $a=7$, among the multiples of 7 of all non-zero remainders, each non-zero remainder appears exactly once, including the pre-selected remainder $x$.]

N3. What remainders do the powers of seven give when divided by 43? If $1 \in P$, what can be said about the affiliation of these remainders to the sets $\mathrm{P}$ and $\mathrm{Q}$ from the problem statement? $[1,7,6,42,36,37$. Further think about why in the case $1 \in \mathrm{P}$ the affiliation of the other five determined remainders to the sets $\mathrm{P}$ and $\mathrm{Q}$ is uniquely determined: $6,36 \in \mathrm{P}$ and $7,42,37 \in \mathbf{Q}$.]

D1. Given a prime number $p$, the set $U=\{1, \ldots, p-1\}$, and its element $a$. Show that then there exists exactly one element $b \in \mathrm{U}$ such that $a b$ gives a remainder of 1 when divided by $p$. [According to N1, among the "multiples" of the number $a$, every possible remainder when divided by $p$ appears exactly once. Thus, the remainder 1 is also included.]

D2. [Little Fermat's Theorem] Given a prime number $p$ and a natural number $a$ coprime with $p$. Show that then $p \mid a^{p-1}-1$. [According to $\mathrm{N} 1$, the sets $\mathrm{U}$ and $\mathrm{V}$ (after reduction to remainders when divided by $p$) are the same. The products of their non-zero elements must therefore be equal. What comes out?]

D3. [Wilson's Theorem]. Show that for every prime number $p$ it holds that $p \mid(p-1) !+1$. [The statement is trivial for $p \in\{2,3\}$. In the case $p \geqq 5$, from the product, we remove all pairs of factors whose product gives a remainder of 1 when divided by $p$. Which two numbers will remain (since they form such a pair with themselves)?]