Find all positive integers $a$ such that there exists a set $X$ of $6$ integers satisfying the following conditions: for every $k=1,2,\ldots ,36$ there exist $x,y\in X$ such that $ax+y-k$ is divisible by $37$.
Problem
Source: CMO 2022 P3
Tags: number theory
CANBANKAN
21.12.2021 21:20
Throughout the solution, a and elements of X are in $\mathbb{Z}_{37}$.
The answer is $a\equiv \pm 6$ only.
Construction: $X=\{16,17,18,19,20,21\}$
Proof of optimality: Let $\omega$ be any primitive $37$th root of unity. Then $\left(\sum_{t\in X} \omega^{at}\right)\left(\sum_{t\in X} \omega^{t}\right)=-1$ is sufficient and necessary.
In particular, $\left(\sum_{t\in X} \omega^{a^2t}\right)\left(\sum_{t\in X} \omega^{at}\right)=-1$, so $\sum_{t\in X} \omega^{a^2t}-\omega^t=0$. This polynomial is divisible by $x^{37}-1$.
I claim this implies $a^2X=X$ in $\mathbb{Z}_{37}$. Sort the remainders of $a^2X, X$ into increasing order, say $0\le y_1<y_2<\cdots<y_6\le 36$ for $a^2X$ and $0\le x_1<x_2<\cdots<x_6 \le 36$. We can see $x_6=y_6, x_5=y_5, x_4=y_4$, and so on, implying $a^2X=X$. This implies if $t\in X, a^2t\in a^2X$, so $a^2t\in X$.
If we consider a permutation $\pi: [6]\rightarrow [6]$ such that $x_j\cdot a^2=x_{\pi(j)}$. Letting
let $d=ord_{37}(a^2)$, the permutation is a disjoint union of cycles of length $d$. Therefore, $d\in \{1,2,3,6\}$.
Case 1: $d=1$. If $a\equiv 1(\bmod\; 37)$ then $(x+y)_{x,y\in X}$ cannot be pairwise distinct.
If $a\equiv -1(\bmod\; 37)$ then $-1=\left(\sum_{t\in X} \omega^{at}\right)\left(\sum_{t\in X} \omega^{t}\right)=|\sum_{t\in X} \omega^{t}|^2$, contradiction.
Case 2: $d=3$. If $a^3\equiv -1(\bmod\; 37)$, we get $\left(\sum_{t\in X} \omega^{at}\right)\left(\sum_{t\in X} \omega^{t}\right)=|\sum_{t\in X} \omega^{t}|^2$ again. If $a^3\equiv 1(\bmod\; 37)$, we can get $X=\{c,a^2c,a^4c,d,a^2d,a^4d\}$ so $aX=X$, so $\frac{x^{37}-1}{x-1} \mid (\sum\limits_{t\in X} x^t)^2+1$, which fails by the same reasoning as $a\equiv 1$.
Case 3: $d=2$. Then $a$ can be 6 or 31 mod 37. Check $\{16,17,18,19,20,21\}$ works.
Case 4: $d=6$, then $X=\{t,a^2t,a^4t,\cdots,a^{10}t\}$. We need $aX+X=\{1,\cdots,36\}$.
Clearly, $t\ne 0$. If we divide all elements of $X$ by $t$ (mod 37) then we have that $X$ is the set of $6$th powers mod 37 and $aX$ is the set of cubes that are not 6th powers mod 37. We can find $X=\{1,27,26,36,10,11\}, aX=\{8,31,23,29,6,14\}$. Note $1+6\equiv 36+8(\bmod\; 37)$, so this case fails.
squareman
25.12.2021 00:09
Clearly $37 \nmid a$. We will take the elements of $X$ as residues $\pmod{37}$. Clearly all of them must be nonzero and distinct. So if $\omega$ is any primitive $37$th root of unity, then it is necessary and sufficient for $$\left(\sum_{n\in X} \omega^{an}\right)\left(\sum_{n\in X} \omega^{n}\right)=\left(\sum_{n\in X} \omega^{a^2n}\right)\left(\sum_{n\in X} \omega^{an}\right) =\sum_{n=1}^{36} \omega^n = -1.$$Consider the polynomial $\sum_{n \in X} x^{a^2n}-\sum_{n\in X} x^{n}$. For each term $x^m$ in the polynomial, replace it with $x^{m\text{'s remainder mod 37}}$. Then this polynomial has degree less than $37,$ but is divisible by $x^{37}-1.$ So it's the zero polynomial, and $a^2X \equiv X \pmod{37}$. Thus, $ord_{37}(a^2) \mid 6.$ If $a^3 \equiv -1,$ $$\left(\sum_{n\in X} \omega^{an}\right)\left(\sum_{n\in X} \omega^{n}\right)=\left(\sum_{n\in X} \omega^{-\frac{n}{a^2}}\right)\left(\sum_{n\in X} \omega^{n}\right)=\left(\sum_{n\in X} \omega^{-n}\right)\left(\sum_{n\in X} \omega^{n}\right)$$which is the magnitude of $\sum_{n\in X} \omega^{n}$ squared, which cannot be $-1.$ If $a^3 \equiv 1,$ then $aX \equiv X \pmod{37}$. So $$\left(\sum_{n\in X} \omega^{n}\right)^2=\left(\sum_{n\in X} \omega^{an}\right)\left(\sum_{n\in X} \omega^{n}\right)=\sum_{n=1}^{36} \omega^n$$ for any primitive $37$th root of unity $\omega$. Take the polynomial $\left(\sum_{n\in X} x^{n}\right)^2-\sum_{n=1}^{36} x^n,$ and for each term $x^m$ in the polynomial, replace it with $x^{m\text{'s remainder mod 37}}$. Then the result has degree less than $37$ and is divisible by $\frac{x^{37}-1}{x-1}$ and $x,$ so it is a zero polynomial, but it's not hard to see that this is impossible. So $ord_{37}(a^2) = 2$ or $6.$ In the former case, $\boxed{a \equiv 6 \pmod{37}}$ works if $X = \{16,17,18,19,20,21 \}$. Note that in this case, $$\left(\sum_{n\in X} \omega^{6n}\right)\left(\sum_{n\in X} \omega^{n}\right) = \omega^{16} \cdot \frac{\omega^{6}-1}{\omega-1} \cdot \omega^{16 \cdot 6} \cdot \frac{\omega^{36}-1}{\omega^{6}-1} = \omega \cdot \frac{\omega^{36}-1}{\omega-1}=-1$$for any primitive $37$th root of unity $\omega$. $\boxed{a \equiv 31 \pmod{37}}$ works as well by an identical argument. In the latter case, $X=\{x,a^2x,a^4x,\cdots,a^{10}x\}$ for some nonzero residue $x$. We can assume WLOG $x=1,$ then this forces $X=\{1,27,26,36,10,11\}, aX=\{8,31,23,29,6,14\}.$ Note $26+6\equiv 1+31 \pmod{37}$ which is contradiction. $\square$
Justanaccount
28.12.2021 15:48
My solution. I replace the set X with S. When a=6, if I let S={1,-1,m,-m,n,-n} then it is easy to see that (m^2+1)(n^2+1)=1 (mod 37). SInce m can't be 2, I let m=3 and see that n =5 satifies the modulo condition. The rest is just check.
Attachments:
CHINA MO 2022 P3.docx (18kb)