55th IMO Team Selection Test

Let $q=4p+1$ and $a\circ b$ be the remainder of $a$ upon division by $b$. It suffices to show that the last digits of the numbers $10^k\circ q$ cover all digits from 0 to 9. Indeed, since $q$ and $10$ are coprime, that would mean that all digits from 0 to 9 occur among the last digits of the numbers $\lfloor \frac{10^k}{q}\rfloor$ – and those are the same as the digits in the decimal representation of $\frac{1}{q}$.

Let $S$ be the set of all nonzero biquadratic residues modulo $q$, i.e., the set of all $0<t<q$ such that the congruence $x^4\equiv t$ has a solution modulo $q$. Then $S$ has exactly $p$ elements. Indeed, since $-1$ is a quadratic residue modulo $q$, the $2p$ nonzero quadratic residues modulo $q$ can be grouped in pairs of the kind $\{s,-s\}$, and among their squares – which are precisely the biquadratic residues – there are precisely $p$ distinct ones.

We will show that every element of $S$ has the form $10^k\circ q$ for some $k$. Indeed, let $d$ be the index of $q$ modulo $10$. Since $d\mid \phi (q)=4p$, we have $d=p$, $d=2p$, or $d=4p$.

Consider the case $d=p$ first. Let $0\le k<p$; then there is a $0\le j\le 3$ such that $k+jq$ is a multiple of $4$ and, therefore, the number $10^k\equiv [10^{\frac{k+jq}{4}}{]}^4(\mathrm{mod}q)$ is a biquadratic residue. Since the numbers $10^k\circ q$ for $0\le k<p$ are pairwise distinct and all of them are biquadratic residues, they must coincide with the elements of $S$, as needed.

The cases $d=2p$ and $d=4p$ are treated analogously.

Let, then, $u$ be an arbitrary digit. Let $0\le j\le 3$ be such that $u+jq$ ends in $0$, $1$, $5$, or $6$. Since $q>10^9$, we have $\sqrt[4]{-(j+1)q}-\sqrt[4]{u+jq}>6$. It follows that the interval $[u+jq,(j+1)q)$ contains at least six fourth powers. Therefore, it contains at least one fourth power $x^4$ that ends in the same digit as $u+jq$. Let $s=x^4\circ q$; then $x^4=s+jq$ and $10\mid x^4-(u+jq)=s-u$, i.e., $s$ ends in $u$, as needed.