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
21.12.2021 21:20
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$
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)