For integers $m\geq 3$, $n$ and $x_1,x_2, \ldots , x_m$ if $x_{i+1}-x_i \equiv x_i-x_{i-1} (mod n) $ for every $2\leq i \leq m-1$, we say that the $m$-tuple $(x_1,x_2,\ldots , x_m)$ is an arithmetic sequence in $(mod n)$. Let $p\geq 5$ be a prime number and $1<a<p-1$ be an integer. Let ${a_1,a_2,\ldots , a_k}$ be the set of all possible remainders when positive powers of $a$ are divided by $p$. Show that if a permutation of ${a_1,a_2,\ldots , a_k}$ is an arithmetic sequence in $(mod p)$, then $k=p-1$.
Problem
Source: Turkey Team Selection Test 2018 P8
Tags: number theory
27.03.2019 02:37
Let, $k$ be the order of $a$ modulo $p$. Clearly, the sets $\{a_1,\cdots,a_k\}$ and $\{a,a^2,\cdots,a^k\}$ coincide. Let, $\{a^{n_1},\cdots,a^{n_k}\}$ be an (increasing) ordering, where; $a^{n_{i+1}}-a^{n_i}$ remains constant throughout. Denote $\alpha \triangleq a^{n_2}-a^{n_1}$. The sequence can therefore be written (in modulo $p$) as, $b_{i+1}\triangleq \{a^{n_1}+i\alpha\}_{i=0}^{k-1}$. Summing the terms up, we get, $a+a^2+\cdots+a^k \equiv 0 \pmod{p}$ (as, $1<a<p-1$), and, summing the sequence above up yields, $p\mid ka^{n_1}+\frac{k(k-1)}{2}\alpha \implies p\mid 2a^{n_1}+(k-1)\alpha$. $\bullet$ First, suppose $k$ is odd. We have, $k-1$ even, and therefore, $p\mid a^{n_1}+\frac{k-1}{2}\alpha$. However, observe that this guy is also contained in the above sequence; which is assumed to consist of powers of $a$, where, $(a,p)=1$, a contradiction. $\bullet$ Hence, $k$ is even. Let, $k=2\ell$. Notice that, $a^{n_1}+(\ell-1)\alpha + a^{n_1}+\ell \alpha = 0$. Hence, in the above sequence, $b_{\ell}+b_{\ell+1}\equiv 0 \pmod{p}$. Letting, $b_\ell \equiv -u\pmod{p}$; the sequence goes likes this: $$ -(2\ell-1)u,-(2\ell-3)u,\cdots,-u,u,3u,\cdots,(2\ell-1)u. $$Now, take the squares, and sum them up in two different ways (one through this; one through, $\sum_{i=1}^k a^{2i}$). The latter is congruent to $0$ in modulo $p$; and the former is, $$ 2u^2(1^2+3^2+\cdots+(2\ell-1)^2) \equiv 0 \pmod{p} \implies p \mid \ell(2\ell+1)(2\ell-1). $$Clearly, $2\ell = k\leq p-1$; hence, $\ell\leq \frac{p-1}{2}$; and therefore, the only possibility is $p\mid 2\ell +1$; which happens iff $\ell = \frac{p-1}{2}$; giving us $k=p-1$.
27.03.2019 02:50
Very similar to 2018 China TST Day 2 Problem 4.
27.03.2019 03:01
I guess they like number theory a lot.
27.03.2019 03:31
hashtagmath wrote: I guess they like number theory a lot. So, this is a TST problem from past year. This year's TST, on the other hand, seems also quite NT-heavy, but I cannot say exactly that Turkey loves NT a lot . To me, it seems the Turkish TST exams tend to be quite balanced.