Let $p>5$ be a prime number and $A=\{b_1,b_2,\dots,b_{\frac{p-1}{2}}\}$ be the set of all quadratic residues modulo $p$, excluding zero. Prove that there doesn't exist any natural $a,c$ satisfying $(ac,p)=1$ such that set $B=\{ab_1+c,ab_2+c,\dots,ab_{\frac{p-1}{2}}+c\}$ and set $A$ are disjoint modulo $p$. This problem was proposed by Amir Hossein Pooya.
Problem
Source: Iran third round number theory exam 2015 - problem 3
Tags: number theory, prime numbers, Quadratic Residues
09.09.2015 12:45
Trivial problem My solution: assume for a sake of a contradiction that $ab_i+c$ are quadratic non-residues modulo $p$ so they are roots of polynomial $x^{\frac{p-1}{2}}+1$ so $x^{\frac{p-1}{2}}+1\equiv (x-ab_1-c)(x-ab_2-c)\dots (x-ab_{\frac{p-1}{2}}-c)$ so $c^{\frac{p-1}{2}}+1\equiv (-1)^{\frac{p-1}{2}}\prod_{i=1}^{\frac{p-1}{2}}b_ia^{\frac{p-1}{2}}\equiv (-1)^{\frac{p-1}{2}}\left(\frac{p-1}{2}\right)!^2a^{\frac{p-1}{2}}\equiv -a^{\frac{p-1}{2}}\equiv 1,-1\pmod{p}$ on the other hand $c^{\frac{p-1}{2}}+1\equiv 0,2$ so the only possible case is that $2\equiv -1\pmod{p}\Longrightarrow p=3$. Contradiction DONE
09.09.2015 12:58
Actually, there's a slight mistake in your solution, because $0$ is not a quadratic residue - nor a quadratic non-residue - modulo $p$ and $x^{\frac{p-1}{2}}+1\equiv (x-ab_1-c)(x-ab_2-c)\dots (x-ab_{\frac{p-1}{2}}-c)$ should rather be changed to $ (x-ab_1-c)(x-ab_2-c)\dots (x-ab_{\frac{p-1}{2}}-c)|x(x^{\frac{p-1}{2}}+1)$ Although the official solution is still using polynomials over field of $\mathbb{Z}_p$.
09.09.2015 15:11
TheOverlord wrote: Actually, there's a slight mistake in your solution, because $0$ is not a quadratic residue - nor a quadratic non-residue - modulo $p$ and $x^{\frac{p-1}{2}}+1\equiv (x-ab_1-c)(x-ab_2-c)\dots (x-ab_{\frac{p-1}{2}}-c)$ should rather be changed to $ (x-ab_1-c)(x-ab_2-c)\dots (x-ab_{\frac{p-1}{2}}-c)|x(x^{\frac{p-1}{2}}+1)$ Although the official solution is still using polynomials over field of $\mathbb{Z}_p$. Ok here is the correction of my solution: consider a case when one of $ab_i+c$ is $0$ modulo $p$. note that $x(x^{\frac{p-1}{2}}+1)\equiv (x-t)(x-ab_1-c)\dots (x-ab_{\frac{p-1}{2}}-c)$$\bigstar$ where $t$ is quadratic non-residue modulo $p$ which is not among $ab_i+c$ then substitute $c$ in $\bigstar$ we get that $c(c^{\frac{p-1}{2}}+1)\equiv a^{\frac{p-1}{2}}(t-c)\pmod{p}$ now there are four cases: 1) $c^{\frac{p-1}{2}}\equiv -1,a^{\frac{p-1}{2}}\equiv 1\pmod{4}\Longrightarrow t\equiv c\pmod{p}$ now rewriting $\bigstar$ we get $x(x^{\frac{p-1}{2}}+1)\equiv (x-c)(x-ab_1-c)\dots (x-b_{\frac{p-1}{2}}-c)$ now we check the coefficient of $x^{\frac{p-1}{2}}$ we get $p\mid a\sum b_i+\frac{p+1}{2}\times c\equiv \frac{p+1}{2}\times c\pmod{p}$ contradiction. 2) $c^{\frac{p-1}{2}}\equiv 1,a^{\frac{p-1}{2}}\equiv 1\pmod{4}\Longrightarrow t\equiv 3c\pmod{p}$ now rewriting $\bigstar$ we get $x(x^{\frac{p-1}{2}}+1)\equiv (x-3c)(x-ab_1-c)\dots (x-b_{\frac{p-1}{2}}-c)$ now we check the coefficient of $x^{\frac{p-1}{2}}$ we get $p\mid a\sum b_i+\frac{p+5}{2}\times c\equiv \frac{p+5}{2}\times c\pmod{p}$ contradiction with the condition $p>5$. 3) $c^{\frac{p-1}{2}}\equiv -1,a^{\frac{p-1}{2}}\equiv -1\pmod{4}\Longrightarrow t\equiv c\pmod{p}$ we get the first case. 4) $c^{\frac{p-1}{2}}\equiv 1,a^{\frac{p-1}{2}}\equiv -1\pmod{4}\Longrightarrow t\equiv -c\pmod{p}$ now rewriting $\bigstar$ we get $x(x^{\frac{p-1}{2}}+ 1)\equiv (x+c)(x-ab_1-c)\dots (x-b_{\frac{p-1}{2}}-c)$ now we check the coefficient of $x^{\frac{p-1}{2}}$ we get $p\mid a\sum b_i+\frac{p-3}{2}\times c\equiv \frac{p-3}{2}\times c\pmod{p}$ contradiction. DONE
10.09.2015 05:38
We work in $\mathbb{Z}/p\mathbb{Z}.$ First suppose $\left(\tfrac{a}{p}\right) = 1$ so that $\left(\tfrac{ab_i}{p}\right) = \left(\tfrac{a}{p}\right)\left(\tfrac{b_i}{p}\right) = 1.$ It follows that $S := \left\{ab_1, ab_2, \cdots , ab_{\frac{p - 1}{2}}\right\}$ is the set of all quadratic residues. Now note that the equation $x^2 = \pm c$ has at most four solutions. Then since $|\mathbb{Z}/p\mathbb{Z}| > 5$, we may choose a nonzero element $r$ such that $r^2 \ne \pm c.$ Let $s = \tfrac{c}{r}$ and observe that $\left(\tfrac{r + s}{2}\right)^2 - \left(\tfrac{r - s}{2}\right)^2 = c.$ In particular, $r \ne \pm s$ so $\left(\tfrac{r + s}{2}\right)^2$ and $\left(\tfrac{r - s}{2}\right)^2$ are both quadratic residues. Thus if we set $\left(\tfrac{r - s}{2}\right)^2 = ab_k$ for some $k \in \left\{1, 2, \cdots , \tfrac{p - 1}{2}\right\}$, the element $ab_k + c$ is common to both $A$ and $B.$ Next, suppose that $\left(\tfrac{a}{p}\right) = -1$ so that $S$ is the set of all quadratic nonresidues modulo $p.$ Consider the arithmetic progression $0, c, 2c, \cdots , (p - 1)c.$ Notice that if $\left(\tfrac{kc}{p}\right) = -1$ for $k = 1, 2, \cdots , p - 2$, then $\left(\tfrac{(k + 1)c}{p}\right) = -1$ as well, for otherwise $kc \in S$ and therefore $(k + 1)c \ne 0$ would be an element common to $A$ and $B.$ In particular, if we consider some $k \in \{1, 2, \cdots , p - 2\}$ satisfying, $\left(\tfrac{kc}{p}\right) = -1$ then we may inductively obtain $\left(\tfrac{nc}{p}\right) = -1$ for all $k \le n \le p - 1$, implying that there are at least $p - k$ quadratic nonresidues. Since there are precisely $\tfrac{p - 1}{2}$ quadratic nonresidues, we must have $k \ge \tfrac{p + 1}{2}.$ It follows that $c, 2c, \cdots , \left(\tfrac{p - 1}{2}\right)c$ are all quadratic residues. By the multiplicative nature of the Legendre symbol, we see that $T:= \left\{1, 2, \cdots , \tfrac{p - 1}{2}\right\}$ must either be the set of all quadratic residues or all quadratic nonresidues, according to the value of $\left(\tfrac{c}{p}\right).$ However, note that $1$ is obviously a quadratic residue, implying $T$ is the set of all the quadratic residues. But then since the Legendre symbol is multiplicative, it follows that $2 \cdot \tfrac{p - 1}{2} = p - 1 \not\in T$ is a quadratic residue as well, contradiction. $\square$
10.09.2015 09:51
Why does there exist $(x,y)$ satisfying the pell equation such that $(xy,p)=1$? Since if it doesn't, then either it is not possible to show $cdy^2$ as $ab_k$ or $cx^2$ is not an element of $A$.
10.09.2015 23:36
@TheOverlord: Thanks for the catch. I've edited the final part of the proof.
18.11.2016 20:39
The great tyranny of life is that we must add numbers neither of which are $1$. The great beauty of $\mathbb Z/p\mathbb Z\setminus\{0\}$ is that the existence of an inverse element often guarantees that we can send one of the addends to $1$. Denote the (nonzero) quadratic residues in $\mathbb Z/p\mathbb Z$ as $R_2$. Call a set of $\tfrac{p-1}{2}$ residues angelic if it is a subset of $R_2\cup \{0\}$ and demonic if it is a subset of $\mathbb Z/p\mathbb Z\setminus R_2$. The problem asks whether $\alpha R_2+\beta$ can ever be a demonic set with $p\nmid \alpha\beta$. Because the quadratic residues are a multiplicative group and the nonresidues are a coset, multiplying our demonic set by $\beta^{-1}$ will give a set that is either demonic or angelic. Also $\alpha\beta^{-1}R_2$ gives either the quadratic residues or the nonresidues. We will show that at least all of the following four items exist for $p\geq 13$: a quadratic residue one more than a nonresidue, a nonresidue one more than a residue, two consecutive residues, and two consecutive nonresidues. The first exists since $\sqrt{p}-\sqrt{0.5p}>1$. The second exists since $1$ is a quadratic residue less than $p-1$. The third and fourth exist since $1,4,9$ are all distinct quadratic resides. They also exist for $p=7,11$ upon a quick check. We are done $\Box$
19.11.2016 00:52
Here is an alternative way to do the second case in Dukejukem's solution: Dukejukem wrote: Next, suppose that $\left(\tfrac{a}{p}\right) = -1$ so that $S$ is the set of all quadratic nonresidues modulo $p.$ Consider the set $\{-c,-2c,\cdots,-\tfrac{p-1}{2}c\}$. It is clear that in order for the hypothesis to be true, this set must be $S$, and more importantly the nonresidues. Note that $B$ cannot be the set of nonresidues, since the sum of its elements is zero whilst the sum of $aA+c$'s elements is nonzero. The sum of the elements of $B$ must then be $-s$ where $s$ is some nonresidue. Hence $-s\equiv -2^{-1}c$, so $2^{-1}c$ is a nonresidue. Denote $B'$ as the multiset of the squares of the elements of $B$. The sum of the elements of $B'$ is then $-s^2$, so $-s^2\equiv -2^{-1}c^2$, meaning that $2^{-1}$ is a quadratic residue. We conclude that $c$ is a nonresidue. Now $c^{-1}S=\{-1,-2,\cdots,-\tfrac{p-1}{2}\}$ is the set of quadratic residues. But $1$ is a quadratic residue. Contradiction $\Box$
03.12.2016 02:39
Some standard notation Let $p':=\frac{p-1}{2}$ and let denote by $\left( \frac{x}{p}\right)$ the Legendre's symbol. Now assume opposite, for the sake of contradiction, i.e. that there exists numbers $a$ and $c$ with required properties. Obviously $B$(when taken mod $p$) represents complete system of quadratic non-residues. Thus $\forall b_i,\ i\in (1,2,...,p')$ we have $$\underbrace{\left( \frac{b_i}{p}\right)=1\stackrel{\text{condition}}{\Longrightarrow} \left( \frac{ab_i+c}{p}\right)=-1}_{\Big \Downarrow}$$$$-1=1\cdot (-1)=\left( \frac{b_i}{p}\right)\cdot \left( \frac{ab_i+c}{p}\right)=\left( \frac{ab_i^2+cb_i}{p}\right)\ . \ . \ . \ \bigstar$$.
). Thus $\forall k_i\in B,\ i\in (1,2,...,p')$ we have $$\underbrace{\left( \frac{k_i}{p}\right)=-1\stackrel{\text{condition}}{\Longrightarrow} \left( \frac{ak_i+c}{p}\right)=1}_{\Big \Downarrow}$$$$-1=-1\cdot 1=\left( \frac{k_i}{p}\right)\cdot \left( \frac{ak_i+c}{p}\right)=\left( \frac{ak_i^2+ck_i}{p}\right)\ . \ . \ . \ \bigstar \bigstar$$. Now we have: \begin{align*} 1-p=\sum_{i=1}^{p-1} (-1)& \stackrel{\bigstar\text{ and }\bigstar \bigstar}{=}\sum_{i=1}^{p'} \left( \left( \frac{ab_i^2+cb_i}{p}\right)+\left( \frac{ak_i^2+ck_i}{p}\right)\right)\\ & =\sum_{i=0}^{p-1} \left( \frac{ai^2+ci}{p}\right)= \begin{cases} -\left( \frac{a}{p}\right) & \text{if } p\nmid c^2; \\ (p-1)\left( \frac{a}{p}\right) & \text{if } p|c^2. \end{cases}\Biggr\rvert \ p\nmid a\\ & \stackrel{\text{only possibility}}{\Longrightarrow} 1-p=(p-1)\left( \frac{a}{p}\right)\text{ if } p|c^2 \\ & \stackrel{(ac,p)=1}{\Longrightarrow} \text{contradiction}\end{align*}
08.03.2017 20:04
If $0\not \in B$ $\implies$ $B$ is the set of quadratic non-residues and hence it's sum is $0$ (in $\mathbb{F}_p$ they are roots of $X^{\frac{p-1}{2}}+1$) $\implies$: $\sum_{x\in B} x=0=a\sum_{x\in A}+c\frac{p-1}{2}=c\frac{p-1}{2}$$\implies$ $c=0$,breaking the first condition.So from now on $0\in B$. Lemma:$A-1$ or $1-A$ contains at least one quadratic residue Proof: Say no.Than $A-1$ contains all quadratic non-residues except on say $r$.By summing elements of $A-1$ we have that $r=-\frac{1}{2}$.Now consider the product of elements in $A-1$ by two.$\sum_{1\leq i<j\leq \frac{p-1}{2}} (b_i-1)(b_j-1)=\sigma_2(b_1,b_2,...b_{\frac{p-1}{2}})+d\sum b_i+\binom{\frac{p-1}{2}}{2}=\binom{\frac{p-1}{2}}{2}=\frac{3}{8}$ However expressing this on another way with $r$ we have that $-\sum_{\left(\frac{x}{p}\right)=-1,x\not=r} rx=r^2=\frac{1}{4}\not = \frac{3}{8}$ contradiction.The proof for $1-A$ is analogous. $\prod_{x\in B} x=\prod_{i<\frac{p-1}{2}}(ab_i+c)=a\prod_{i<\frac{p-1}{2}}b_i+c^{\frac{p-1}{2}}=-a(-1)^{\frac{p-1}{2}}+c^{\frac{p-1}{2}}=0$ as all symmetric polys of $b_i$ in $\mathbb{F}_p$ are zero except for the product.Now by previous a is $\{1,-1\}$.$a=1$ than $\exists j$ $c=\pm b_j$ and wlog let $j=1$.Now: $$B=\{j\leq \frac{p-1}{2}\mid \mp b_j \pm b_1\}$$By assumption contains no quadratic residues.Letting $b_j=kb_1$ and using the lemma we have $\exists j$ so that $\mp k \pm 1$ is a quadratic residue and hence a contradiciton.
03.11.2020 12:53
Define $d=c \cdot a^{-1}.$ So, $ab_i+c$ being a NQR is the same as $b_i+d$ being a QR if $a$ is a NQR, and a NQR if $a$ is a QR, respectively. So, showing that $B$ does not contain all NQRs is the same as showing the set $\{b_i+d\}$ cannot contain only QRs or only NQRs for any $d \not \equiv 0 \pmod{p}.$ However, if $\{b_i+d\}$ are all QRs, then adding all elements shows $\tfrac{p-1}{2}d \equiv 0 \pmod{p},$ a contradiction. So we deal with the case when $\{b_i+d\}$ are all NQR. Now, note that since $p>2,3,$ hence sum of quadratic residues is $$1^2+2^2+\dots+\left(\frac{p-1}{2} \right)^2=\frac{p}{6}\left( \frac{p-1}{2} \right)\left( \frac{p+1}{2} \right) \equiv 0 \pmod{p}.$$Also, sum of all residues mod $p$ is $0,$ implying that sum of al quadratic nonresidues is $0.$ Hence if all $\{b_i+d\}$ are NQRs, adding again gives $\tfrac{p-1}{2}d \equiv 0 \pmod{p},$ a contradiction.