Let $p$ a prime number and $r$ an integer such that $p|r^7-1$. Prove that if there exist integers $a, b$ such that $p|r+1-a^2$ and $p|r^2+1-b^2$, then there exist an integer $c$ such that $p|r^3+1-c^2$.
Problem
Source: 2019 Polish MO Finals
Tags: number theory, prime numbers, Divisibility
09.07.2019 04:38
Work in $\mathbb{F}_p$. We first deal with the case where one of $(a,b)$ is allowed to be $0$. If $a=0$, then $r=-1$, which doesn't work unless $p=2$ (the $p=2$ case is trivial as every value is a quadratic residue $\bmod 2$). If $b=0$, then $r^2=-1$, so $1=r^7=\left(r^2\right)^3r=-r$, so $r=-1$, whence we again get $p=2$. Now, we have $$\left(\frac{r+1}{p}\right)=\left(\frac{r^2+1}{p}\right)=1.$$ If $r=1$, then we are given that $(2/p)=1$ and need to show that $(2/p)=1$, so we are done. So, assume $r\neq 1$, whence we have $$r^6+r^5+r^4+r^3+r^2+r+1=0.$$ Now, we have $(r^3+1)(r^2+1)(r+1)=r^6+r^5+r^4+2r^3+r^2+r+1=r^3$, so $$\left(\frac{r^3+1}{p}\right)=\left(\frac{r^3}{p}\right)=\left(\frac{r}{p}\right).$$ As $r^7=1$ but $r\neq 1$, we have $p\equiv 1\bmod 7$, which implies that $p\equiv 1\bmod 14$, and thus $s^{14}=1$ has $14$ roots in $\mathbb{F}_p$, and in particular $r$ has a square root, finishing the proof.
09.07.2019 06:03
Work in $\mathbb{F}_p$. First, we dispatch the case $ab=0$. If $a=0$, then $r=-1\implies -1=r^7=1$ or $p=2$. Analogously, $b=0\implies r^2=-1\implies 1 = r^{14}=-1$ or $p=2$. For now, assume that $ab\ne 0$. If $r=1$, then $r+1=r^2+1=r^3+1=2$ so we are done. Assume that $r\ne 1$. This means $$\left(\frac{r+1}{p}\right) = \left(\frac{r^2+1}{p}\right) = 1$$Therefore $$(r-1)(r+1)(r^2+1)(r^4+1) = r^8-1 = r-1 \implies (r+1)(r^2+1)(r^4+1)=1$$or $\left(\tfrac{r^4+1}{p}\right) = 1$. But $$r^4+1 = \frac{1}{r^3}+1 = \frac{r^3+1}{r^3}$$so we will be done if we show that $\left(\tfrac{r}{p}\right)=1$. But this is obvious as $\left(\tfrac{r^7}{p}\right) = 1$.
09.07.2019 08:11
Slightly different finish from aboves: get $\left( \frac{r^4 + 1}{p} \right ) =1$. Then \[\left( \frac{r^3 + 1}{p} \right ) = \left( \frac{r^3 + 1}{p} \right )\left( \frac{r^4}{p} \right ) = \left( \frac{r^4 + 1}{p} \right ) =1.\]
09.07.2019 11:29
Exclude the case when $r\equiv \pm 1,0\pmod{p}$. We have $$\left( \frac{r-1}{p}\right)\left( \frac{r^4+1}{p}\right) =\left( \frac{r-1}{p}\right) \left( \frac{r+1}{p}\right)\left( \frac{r^2+1}{p}\right)\left( \frac{r^4+1}{p}\right) =\left( \frac{r^8-1}{p}\right) =\left( \frac{r^8-r^7}{p}\right) =\left( \frac{r}{p}\right)\left( \frac{r-1}{p}\right).$$Hence, $$\left( \frac{r^3+1}{p}\right)=\left( \frac{r^3+r^7}{p}\right)=\left( \frac{r}{p}\right)\left( \frac{r^4+1}{p}\right)=1.\quad \blacksquare$$
09.07.2019 18:08
Whoops, here is a bad brute force approach. In the following, QR = quadratic residue and NQR = non-quadratic residue. Our game plan is to use the $r^7 - 1$ condition to continually bash out expressions that must be QR's and NQR's, until we get the desired. First of all, we get rid of the case $r \equiv 1$ (mod $p$) since it is trivial. The case where $p = 2$ is also trivial, and so hence WLOG assume that $p$ is odd and $p \nmid r-1.$ Henceforth, we assume that $p|r^6+r^5+r^4+r^3+r^2+r+1.$ If we make the substitution $x = r + \frac1r,$ we then know that $p|r^3 + r^2 + r^1 + 1 + \frac1r + \frac{1}{r^2} + \frac{1}{r^3} = x^3 + x^2 - 2x -1.$ Note that since the order of $r$ modulo $p$ is $7$, we must have that $r$ is a perfect square since $7$ is odd. This implies that $r+1, r^2+1, r^5+1 (=r^5(r^2+1)), r^6+1 (=r^6(r+1))$ are all QR's modulo $p.$ Writing $r^2+1, r^6+1$ in terms of $x$, we know that $rx, r^3 (x^3-3x)$ are both QRs, which together with $\left ( \frac{r}{p} \right ) = 1$ yield that $x, x^2-3$ are both QRs. Lemma. $x^2-2$ is a QR. Proof. Suppose the contrary, for contradiction. That is, $x^2 - 2$ is a NQR. In view of $(x^2-2)(-x-1) \equiv 1$ (mod $p$), we now get that $-x-1$ is a QR. Hence, since $(x^2-3)(-x-1) \equiv x+2$ (mod $p$), we obtain that $x+2$ is a QR. Next, since $(x+2)(x^2-x) \equiv 1$ (mod $p$), we obtain that $x^2 -x$ is a QR. Since we already know $\left ( \frac{x}{p} \right ) = 1$, we get that $x-1$ is a QR. Thus, since $x-1, -x-1$ are both QR's, we know that $(x-1)(-x-1) \equiv 1-x^2 \equiv x^3-2x$ is a QR. Hence, since we already know that $x$ is a QR, we get that $x^2 - 2$ is a QR. However, this is a clear contradiction to our assumption, and therefore our initial assumption was incorrect. In other words, $x^2 - 2$ is a QR modulo $p$. $\blacksquare$ From the lemma, we obtain that $x^2 - 2 \equiv r^2 + \frac{1}{r^2}$ is a QR, so since $r$ is a QR we obtain that $(r^2 + \frac{1}{r^2})(r^5) \equiv r^3 + 1$ is a QR. The proof is complete. $\square$
11.07.2019 19:02
pieater314159 wrote: Work in $\mathbb{F}_p$. We first deal with the case where one of $(a,b)$ is allowed to be $0$. If $a=0$, then $r=-1$, which doesn't work unless $p=2$ (the $p=2$ case is trivial as every value is a quadratic residue $\bmod 2$). If $b=0$, then $r^2=-1$, so $1=r^7=\left(r^2\right)^3r=-r$, so $r=-1$, whence we again get $p=2$. Now, we have $$\left(\frac{r+1}{p}\right)=\left(\frac{r^2+1}{p}\right)=1.$$ If $r=1$, then we are given that $(2/p)=1$ and need to show that $(2/p)=1$, so we are done. So, assume $r\neq 1$, whence we have $$r^6+r^5+r^4+r^3+r^2+r+1=0.$$ Now, we have $(r^3+1)(r^2+1)(r+1)=r^6+r^5+r^4+2r^3+r^2+r+1=r^3$, so $$\left(\frac{r^3+1}{p}\right)=\left(\frac{r^3}{p}\right)=\left(\frac{r}{p}\right).$$ As $r^7=1$ but $r\neq 1$, we have $p\equiv 1\bmod 7$, which implies that $p\equiv 1\bmod 14$, and thus $s^{14}=1$ has $14$ roots in $\mathbb{F}_p$, and in particular $r$ has a square root, finishing the proof. Or ((r^3+1) / p) = ((r^3/p) = (r^7/p) = 1
12.03.2021 19:26
From the text $r^7,r+1,r^2+1$ are quadr residues mod p. $r^7$ is a quadratic residue mod p, so by multiplication of Legendre symbol, $r$ is also a quadratic residue mod p. 1st case: $p|r^7-1=(r-1)(r^6+r^5+r^4+...+r+1)$. Let $p|r-1$ then ${a^2}\equiv {2}$ mod p but also $r^3+1\equiv {2}$ mod p so we can put $c=a$. 2nd case: $p|(r^6+r^5+r^4+...+r+1)$. Then $r^4(r^2+r+1)\equiv {-(r^2+1)(r+1)}$ Bur $r^2+1$ and $r+1$ are quadratic residues mod p, so $(r^2+1)(r+1)$ is also a quadratic residue. Then $r^4(r^2+r+1)\equiv {-(x)^2}$ for some x. Note that $r^4$ is also a quadratc residue (because r is a quadr. residue), so $(r^2+r+1)\equiv {-(y)^2}$ for some y. (1) Then, note $(r^4+r^2+1)(r+1)\equiv {-(r)^6}$ but $ r^6$ is quadratic residue and $r+1$ is also a quadr. residue so similarly to (1) $r^4+r^2+1\equiv {-(z)^2}$ for some z. (2) Then note $(r^4+r^2+1)=(r^2+r+1)(r^2-r+1)$ and by (1) and (2) we get that $(r^2-r+1)$ is a quadr. residue so $r^3+1=(r+1)(r^2-r+1)$ is also a quadr. residue (because $(r+1)$ is a quadr. residue), Q.E.D.