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
62861
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.
Mathlover_SH
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.
Photaesthesia
30.08.2018 09:12
So now I want to know what association does this have with the 2017 ISL?
Mathlover_SH
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?
kahliipreyta
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?
Tintarn
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$.
kahliipreyta
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.
Tintarn
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...
EthanWYX2009
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$
vsamc
23.06.2023 22:41
Solved with megarnie
Let $k' = \gcd(k, p-1)$. Note that if $a$ is a $k$th nonzero power mod $p$, then $a$ is a $k'$th nonzero power mod $p$ since $k' \mid p$. It is also true that if $a$ is a $k'$th nonzero power mod $p$, then $a$ is a $k$th nonzero power modulo $p$, since if $a = g^r$, for some primitive root $g$ modulo $P$, then we know that there exists an integer $s$ for which $k'r \equiv s\pmod{p-1}$. Then, for each prime $q \mid p-1$, we have that $k'r \equiv s\pmod{q^{\nu_q(p-1)}}$. If $\nu_q(k) > \nu_q(p-1)$, then $\nu_q(k') = \nu_q(p-1)$, so $s\equiv k'r\equiv 0\pmod{q^{\nu_q(p-1}},$ so $s$ is a multiple of $k$ mod $q^{\nu_q(p-1)}$. Else, $\nu_q(k) \leq \nu_q(p-1)$, so $kr \equiv \frac{k}{k'} \cdot s \pmod{q^{\nu_q(p-1)}},$ and $\nu_q(k/k') = \nu_q(k) - \nu_q(k') = 0$, so we have that $s\equiv k\left(\frac{r}{k/k'}\right)\pmod{q^{\nu_q(p-1)}}$, and $\frac{r}{k/k'}$ is congruent to an integer modulo $q^{\nu_q(p-1)}$ as $\gcd(k/k', q^{\nu_q(p-1)}$ is $1$. Thus, $s$ is a multiple of $k$ modulo $q^{\nu_q(p-1)}$, and this holds in the other case too. Thus, if $s \equiv ks_q\pmod{q^{\nu_q(p-1)}}$ for all $q \mid p-1$, for some integer $s_q$, then by CRT there exists a $t$ for which $t\equiv s_q\pmod{q^{\nu_q(p-1)}}$, and so $s\equiv kt\pmod{p-1}$, so $a$ is a nonzero $k$th power modulo $p$.
Thus, $S$ is the set of all nonzero $k'$th powers modulo $p$. Let $d = \frac{p-1}{k'}$. Then, $d$ is a positive integer, since $k' \mid p-1$, and for all $x\in S$, $x^d\equiv 1\pmod{p}$ since $x \equiv y^{k'}\pmod{p}$ for some integer $y$ not divisible by $p$ (since no element of $S$ is divisible by $p$, and so $$x^d\equiv y^{dk'}\equiv y^{p-1} \equiv 1\pmod{p}$$by FLT. There are also only $d$ such $k'$th powers modulo $p$, since if $x \equiv g^a\pmod{p}$ is a $k'$th power for some primitive root $g$, then $k'\mid a$, so the only possible residues of $a$ modulo $p-1$ are $k', 2k', \cdots, k'd = p-1$, and they all work. Thus, by Lagrange $S$ is the set of all $1\leq a\leq p-1$ satisfying $a^d\equiv 1\pmod{p}$.
Now, assume for the sake of contradiction that $S$ was an arithmetic progression. First, note that $|S| = d$, so $3\leq d\leq p-2$. Also, note that $1^d\equiv 1\pmod{p}$, so $1\in S$. By Vieta's mod $p$, the sum of the elements in $S$ is $0\pmod{p}$. Thus, if $x$ is the largest element of $S$, then we have that since $S$ is an arithmetic progression,
\begin{align*}
0 &\equiv \sum_{s\in S}s \\
&\equiv |S|\left(\frac{1+x}{2}\right) \\
&\equiv d\left(\frac{1+x}{2}\right) \pmod{p}.
\end{align*}Since $3\leq d\leq p-2$, we have that $d\not \equiv 0\pmod{p}$ and that $p\geq 5$, so we must have $1+x\equiv 0\pmod{p}$, so $x\equiv p-1\pmod{p}$. Since all elements of $S$ are between $1$ and $p-1$ inclusive, it follows that $x = p-1$. Thus, the common difference of $S$ is $\frac{x-1}{d-1} = \frac{p-2}{d-1}$. Thus, if we let $m = \frac{p-2}{d-1}$, we have that $S = \{ 1, 1 + m, 1 + 2m, \cdots, 1 + (d-1)m \}$. Now, note that by Vieta's mod $p$ again, since $d \geq 3$, we have that the first and second symmetric sums of $S$ are $0\pmod{p}$, so the sums of the squares of the elements of $S$ are also $0\pmod{p}$. Thus, we have that
\begin{align*}
0 &\equiv \sum_{i=0}^{d-1}(1+im)^2 \\
&\equiv m^2\sum_{i=0}^{d-1}i^2 + 2m\sum_{i=0}^{d-1}i + \sum_{i=0}^{d-1}d \\
&\equiv m^2\left(\frac{(d-1)d(2d-1)}{6}\right) + m((d-1)d) + d \pmod{p}.
\end{align*}Since $3 \leq d\leq p-2$, $d\not \equiv 0\pmod{p}$. Also, we have that $d \equiv \frac{p-2}{d-1}\pmod{p}$. Thus,
\begin{align*}
0 &\equiv m^2\left(\frac{(d-1)(2d-1)}{6}\right) + m(d-1) + 1 \pmod{p} \\
&\equiv \left(\frac{-2}{d-1}\right)^2 \cdot \frac{(d-1)(2d-1)}{6} + \frac{-2}{d-1}\cdot (d-1) + 1 \\
&\equiv \frac{2}{3}\cdot \frac{2d-1}{d-1} - 1 \\
&\equiv \frac{4d-2}{3d-3} - 1 \\
&\equiv \frac{d + 1}{3d-3} \pmod{p},
\end{align*}so $d+1\equiv 0\pmod{p}$. However, $3\leq d \leq p-2$, so there is no such $d$, a contradiction, so $S$ cannot be an arithmetic progression, as desired. $\blacksquare$