Erzsi received the following task. "Find 5 integers such that when any two of them are multiplied and then divided by 12, the remainder is different in every case!" Then solve the same problem, but with 14 instead of 12!"

Erzsi realized that it is sufficient to look for the numbers in the first case between $1,2, \ldots, 11$, and in the second case between 1,2 , ..., 13.

Can we help Erzsi further?
Erzsi's statement is correct for any divisor \( M \) (here \( M=12 \) or 14). It is sufficient to focus on the non-negative integers less than \( M \) in the search, because if one factor is \( a=k M+r \), where \( k \) is an integer and \( 0 \leq r < M \), and the other factor is \( b \), then their product is \( a b=(k b) \cdot M+r b \), and this, when divided by \( M \), gives the same remainder as \( r b \), since

\[
\frac{a b}{M}=k b+\frac{r b}{M}
\]

where \( k b \) is an integer. (This reasoning naturally applies to \( b \) as well.)

However, the number 0 cannot appear among the selected numbers, because multiplying it by any of the other 4 numbers will always yield the same quotient and remainder, i.e., 0. For the same reason, the 5 numbers - within the found limits - must be distinct from each other.

From 5 distinct numbers, say \( a, b, c, d \) and \( e \), 10 two-factor products can be formed:

\[
a b, a c, a d, a e ; b c, b d, b e ; c d, c e ; d e
\]

The further reasoning is based on the observation that if the integers \( A, M, K, R \) satisfy

\[
A=M K+R
\]

and \( d \) is a divisor of \( M \), then either \( A \) and \( R \) are both divisible by \( d \), or neither is. Indeed, from the equation

\[
A-R=M K
\]

which is divisible by \( d \), and this cannot happen if one term is divisible by \( d \) and the other is not.

I. We show that for \( M=12 \), no suitable quintuple can be found. The remainder of the ten two-factor products must be one of the numbers

\[
0,1,2,3,4,5,6,7,8,9,10,11
\]

No matter how we choose ten from these, there will be both even and odd numbers among them. According to our observation, only the even products among our two-factor products give even remainders, since 12 is even; moreover, since 12 is divisible by 4, if a product is divisible by 4, then its remainder is also, and only then.

There will be an even product among the products if there is an even number among the five chosen numbers. If this number is also divisible by 4, then the remainder of its product with the other four numbers is also divisible by 4; however, among the (2) numbers, only three are divisible by 4. Thus, there cannot be a number divisible by 4 among the five numbers.

If, however, there is only an even number not divisible by 4 among the five numbers, then its product with an odd number is also such:

\[
(4 k+2)(2 l+1)=4(2 k l+k+l)+2
\]

so if the other four numbers are odd, then the remainder of four products is not divisible by 4 but is even, whereas among the (1) numbers, only three are such.

If, however, there are at least two even numbers among the five numbers, then the product of these with the other three numbers and with each other, i.e., at least seven products, is even, and thus their remainders are also even, whereas among the (1) numbers, only six are even. Thus, no matter which five numbers we start with, it is not possible for the remainders of all two-factor products (when divided by 12) to be different.

II. For \( M=14 \), the possible remainders are

\[
0^{*}, 1,2,3,4,5,6,7^{*}, 8,9,10,11,12,13
\]

Similarly to the above, we find that 0 cannot appear in our quintuple, but neither can 7, because its product with the other four numbers would also be divisible by 7, and thus, according to our observation, its remainder would also be, whereas among the (3) numbers, only two are divisible by 7. According to our observation, this also means that neither 0 nor 7 can appear as a remainder, so only 6 even and 6 odd remainders can appear from (3). From this, similarly to the above, it follows that one of the five numbers, say the even one, is the other four are odd.

The selection of the odd numbers requires consideration. If, for example, \( b, c, d, e \) are such that the last six products in (1) give different remainders - as we have seen, all odd -, then \( a \) can be any of 2, 4, 6, 8, 10, and 12, because the first four products in (1) and their remainders are even, and thus different from those. Moreover, two of them - e.g., \( a b \) and \( a c \) - cannot give the same remainder, otherwise \( a c-a b=a(c-b) \) would be divisible by 14, and thus by 7, which is not true, because the value of \( c-b \) is also one of the numbers 2, 4, 6, 8, 10, 12.

For the selection of the numbers \( b, c, d, e \), we list in a table the remainders of the products formed from the possible odd numbers when divided by 14.

| smaller factor | larger factor |  |  |  |  |
| ---: | ---: | ---: | ---: | ---: | ---: |
| factor | 3 | 5 | 9 | 11 | 13 |
| 1 | 3 | 5 | 9 | 11 | 13 |
| 3 |  | 1 | 13 | 5 | 11 |
| 5 |  |  | 3 | 13 | 9 |
| 9 |  |  |  | 1 | 5 |
| 11 |  |  |  |  | 3 |

Taking, for example, \( b=1, c=3, d=5 \), the remainders of the even products formed from these are 3, 5, and 1 according to the table. Since there is a 5 in the continuation of the 3rd row and a 3 in the 5th row, in the 11th and 9th columns, 11 and 9 cannot be used as \( e \), but \( e=13 \) can.

According to this, Erzsi's second task requirement is met, for example, by the quintuple

\[
a=6, \quad b=1, \quad c=3, \quad d=5, \quad e=13
\]

The remainders derived from the products, in ascending order:

\[
1,2,3,4,5,6,8,9,11,13
\]

Sailer Kornél (Ózd, József A. Gimn., III. o. t.) Gál Péter (Budapest, Fazekas M. Gyak. Gimn., I. o. t.)

Note. It is easy to show that if \( b, c, d, e \) is a suitable set of four odd numbers for the divisor 14, then \( 14-b, 14-c, 14-d, 14-e \) is also suitable.

The other suitable sets of four odd numbers are:

\[
1,3,9,11 ; \quad 1,5,9,11 ; \quad 1,9,11,13 ; \quad 3,5,9,13 ; \quad 3,5,11,13
\]

The total number of these is 6, so the total number of ways to select the quintuple is \( 6 \cdot 6=36 \).

Sailer Kornél, Gál Péter