Let $p$ be a prime and $k$ be a positive integer. Set $S$ contains all positive integers $a$ satisfying $1\le a \le p-1$, and there exists positive integer $x$ such that $x^k\equiv a \pmod p$. Suppose that $3\le |S| \le p-2$. Prove that the elements of $S$, when arranged in increasing order, does not form an arithmetic progression.
Problem
Source: China TST 4 2018 Day 2 Q4
Tags: modular arithmetic, arithmetic sequence, number theory
31.07.2018 16:39
We may assume $p \ge 7$. Let $S = \{g^0, \dots, g^{d-1}\}$ modulo $p$, where $d$ properly divides $p-1$. Then \begin{align*} \sum_{s \in S} s & = g^0 + \dots + g^{d-1} = \frac{g^d-1}{g-1} = 0\\ \sum_{s \in S} s^2 & = g^0 + \dots + g^{2(d-1)} = \frac{g^{2d}-1}{g^2-1} = 0 \end{align*}as $g \neq \pm 1$. This leads to a contradiction. Letting $S = \{a, a+k, \dots, a+(d-1)k\}$ modulo $p$, \begin{align*} \sum_{s \in S} s & = \sum_{i = 0}^{d-1} a + ik = da + \frac{d(d-1)}{2}k,\\ \sum_{s \in S} s^2 & = \sum_{i = 0}^{d-1} (a + ik)^2 = da^2 + d(d-1)ak + \frac{d(d-1)(2d-1)}{6} k^2. \end{align*}For both to be zero, $a + \tfrac{d-1}{2}k = a^2 + (d-1)ak + \tfrac{(d-1)(2d-1)}{6} k^2 = 0$. Setting $a = -\tfrac{d-1}{2}k$ the second expression equals \[k^2 \left(\frac{(d-1)^2}{4} - \frac{(d-1)^2}{2} + \frac{(d-1)(2d-1)}{6}\right) = 0.\]So it is necessary that \[\frac{d-1}{4} - \frac{d-1}{2} + \frac{2d-1}{6} = 0 \implies d = -1,\]which is not possible.
31.07.2018 16:49
Above is too complicated. Just notice that if $x$ is an element of $S$,then $S=xS$,where $xS$ means mutiplying elements in $S$ by $k$. So if the elements of $S$, when arranged in increasing order, forms an arithmetic progression We can choose a $x$ in $S$ such that x isn't 1 or -1 $(mod p)$ Let $f(X)$ be the sum of the elements in set $X$ We have $f(S)=f(xS)(mod p)$ $i.e. (1-x)f(S)=0(mod p)$ Similarly,$(1-x^2)f(S^2)=0(mod p)$(I believe you can easily guess what $S^2$ is) So $f(S)=f(S^2)=0(mod p)$ Actually,$f(S)=a+(a+d)+(a+2d)+...+(a+(x-1)d)(mod p)$,here $x$ is the numeber of elements in $S$ So $xa+x(x-1)/2=0 (mod p)$ And we get $a+(x-1)/2=0(mod p)$ Through the same procession we get $a^2+(x-1)ad+(x-1)x(2x-1)d^2/6=0(mod p)$ Then we can easily reach a paradox. By the way this is P4 of China TSTST.
30.08.2018 09:12
So now I want to know what association does this have with the 2017 ISL?
30.08.2018 10:03
Photaesthesia wrote: So now I want to know what association does this have with the 2017 ISL? What's that then?
28.11.2018 16:00
CantonMathGuy wrote: \begin{align*} \sum_{s \in S} s & = g^0 + \dots + g^{d-1} = \frac{g^d-1}{g-1} = 0\\ \sum_{s \in S} s^2 & = g^0 + \dots + g^{2(d-1)} = \frac{g^{2d}-1}{g^2-1} = 0 \end{align*} \begin{align*} \sum_{s \in S} s & = \sum_{i = 0}^{d-1} a + ik = da + \frac{d(d-1)}{2}k,\\ \sum_{s \in S} s^2 & = \sum_{i = 0}^{d-1} (a + ik)^2 = da^2 + d(d-1)ak + \frac{d(d-1)(2d-1)}{6} k^2. \end{align*}For both to be zero, $ Dear Canton Math Guy, can you expain more clearly, for me, how can it be zero?
28.11.2018 20:30
kahliipreyta wrote: Dear Canton Math Guy, can you expain more clearly, for me, how can it be zero? Note that the invertible zeroes modulo $p$ form a cyclic group (i.e. there is a primitive root) and the $k$-th powers form a subgroup. Hence they are generated by some element $g$ which then satisfies $g^d=1$ due to the fact that the order of any element in a group divides the order of the group (which is $d$ here). Hence $g^d=1$ and $\frac{g^d-1}{g-1}=0$.
29.11.2018 16:10
Tintarn wrote: Note that the invertible zeroes modulo $p$ form a cyclic group (i.e. there is a primitive root) and the $k$-th powers form a subgroup. Hence they are generated by some element $g$ which then satisfies $g^d=1$ due to the fact that the order of any element in a group divides the order of the group (which is $d$ here). Hence $g^d=1$ and $\frac{g^d-1}{g-1}=0$. Dear Tintarn, I still have some stucks, - Invertible zeros modulo $p,$ what does it means - What is a cyclic group?(I have searched in the internet but its definiton is too complex, it is not a normal group) - How can $g^d=1,$ in Number Theory, which $g=1?$ It is very kind of you to give me some Exs, thank you, I am new to TST and every things are strange for me.
30.11.2018 11:37
kahliipreyta wrote: Dear Tintarn, I still have some stucks, - Invertible zeros modulo $p,$ what does it means Oh sorry that should have been "invertible residues". Just the residues not divisible by $p$ i.e. $\{1,2,3,\dotsc,p-1\}$. kahliipreyta wrote: - What is a cyclic group?(I have searched in the internet but its definiton is too complex, it is not a normal group) Just a group where there is an element $g$ (called a generator or a primitive root) such that by considering $1,g,g^2,g^3,\dotsc$ we run through the whole group. kahliipreyta wrote: - How can $g^d=1,$ in Number Theory, which $g=1?$ Well of course this means $g^d \equiv 1\mod p$ i.e. we have an equality of residues and not an equality of integers. Not sure if that helps...
23.06.2023 05:42
My 400th post! Very meaningful to me. Step 1 If not$,$ let $|S|=n,3\leq n\leq p-2,S=\{a_1,a_2,\cdots ,a_n\},a_1<a_2<\cdots <a_n$ and $a_i=a_1+(n-1)d,1\leq i\leq n.$ As $n\geq 3,\exists a\in S$ satisfying $a^2\not\equiv 1\pmod p.$ For $1\leq i\leq n,$ let $a_i\equiv x_i^k\pmod p,$ and let $a\equiv x^k\pmod p.$ Then for $1\leq i\leq n,aa_i\equiv (xx_i)^k\pmod p,$ therefore $aa_i\in S.$ By $aa_i\not\equiv aa_j\pmod p,1\leq i<j\leq n,$ we have $$\{aa_1,aa_2,\cdots ,aa_n\}\equiv\{a_1,a_2,\cdots ,a_n\}\pmod p.$$Step 2 We have $\sum\limits_{i=1}^naa_i\equiv\sum\limits_{i=1}^na_i\pmod p.$ Then $$p\mid (a-1)\sum\limits_{i=1}^na_i\stackrel{p\nmid (a-1)}{\Longrightarrow} p\mid\sum\limits_{i=1}^na_i=na_1+\frac{n(n-1)d}2\stackrel{p\nmid n}{\Longrightarrow} p\mid 2a_1+(n-1)d.$$Step 3 We have $\sum\limits_{i=1}^n(aa_i)^2\equiv\sum\limits_{i=1}^na_i^2\pmod p.$ Then $p\mid (a^2-1)\sum\limits_{i=1}^na_i^2,$ $${\begin{aligned}\stackrel{p\nmid (a^2-1)}{\Longrightarrow} p\mid\sum\limits_{i=1}^na_i^2&=\sum\limits_{i=1}^n[a_1+(i-1)d]^2=\sum\limits_{i=1}^n[a_1^2+(i-1)^2d^2+2d(i-1)a_1]\\&=na_1^2+\frac 16(n-1)n(2n-1)d^2+n(n-1)a_1d.\end{aligned}}$$$$\stackrel{p\nmid n}{\Longrightarrow} p\mid 6a_1^2+(n-1)(2n-1)d^2+6(n-1)a_1d.$$$$\begin{aligned}(n-1)d\equiv -2a_1\pmod p &\Rightarrow 6a_1^2+(n-1)(2n-1)d^2+6(n-1)a_1d\\ &\equiv 6a_1^2-2(2n-1)a_1d-12a_1^2=-6a_1^2-(4n-2)a_1d\\&\equiv 3a_1(n-1)d-(4n-2)a_1d\equiv -(n-1)a_1d\pmod p.\end{aligned}$$Therefore $p\mid (n-1)a_1d,$ contradiction$!$ So we are done$.\blacksquare$
23.06.2023 22:41
Solved with megarnie