Show that for each prime $p \geq 7$, there exist a positive integer $n$ and integers $x_{i}$, $y_{i}$ $(i = 1, . . . , n)$, not divisible by $p$, such that $x_{i}^{2}+ y_{i}^{2}\equiv x_{i+1}^{2}\pmod{p}$ where $x_{n+1} = x_{1}$
Problem
Source: Turkey TST 1997 Problem 5
Tags: modular arithmetic, abstract algebra, number theory proposed, number theory
30.11.2011 20:35
For $p \equiv 1 \pmod{4}$ it is trivial because that are solutions to $a^2 + b^2 \equiv 0 \pmod{p}$ where $a,b \not \equiv 0 \pmod{p}$. Thus we consider $p \equiv 3 \pmod{4}$, so $\left (\frac{-1}{p}\right) = -1$. By Lagrange's Theorem every positive integer can be expressed as the sum of not more than $4$ squares. As $p \not \equiv 1 \pmod{4}$, it requires more than $2$ squares. Thus if $p = a^2 + b^2 + c^2$, then let $n=3, y_1 = a, y_2 = b, y_3 = c$. Then we want none of $x_1, x_2, x_3$ to be $0 \pmod{p}$. However, $x_1,x_4 \equiv 0 \pmod{p}$ iff $x_1 \equiv 0 \pmod{p}$ (obviously) $x_2 \equiv 0 \pmod{p}$ iff $x_1 \equiv -a^2 \pmod{p}$ $x_3 \equiv 0 \pmod{p}$ iff $x_1 \equiv -(a^2 + b^2) \pmod{p}$ But then only $3$ numbers in $\mathbb{Z}_p$ are prohibited. Thus as $p \ge 7$, we can choose an $x_1$ such that none are $0 \pmod{p}$ and we are done with this case. If $p = a^2 + b^2 + c^2 + d^2$, then let $n=4, y_1 = a, y_2 = b, y_3 = c, y_4 = d$. Then: $x_1,x_5 \equiv 0 \pmod{p}$ iff $x_1 \equiv 0 \pmod{p}$ (obviously) $x_2 \equiv 0 \pmod{p}$ iff $x_1 \equiv -a^2 \pmod{p}$ $x_3 \equiv 0 \pmod{p}$ iff $x_1 \equiv -(a^2 + b^2) \pmod{p}$ $x_4 \equiv 0 \pmod{p}$ iff $x_1 \equiv -(a^2 + b^c + c^2) \pmod{p}$ However, only $4$ members of $\mathbb{Z}_p$ are prohibited, and thus as $p \ge 7$ we can choose an $x_1$ such that none are $0 \pmod{p}$ and we are done.
26.12.2017 03:55
More direct way: In what follows, always consider modulo $p$. Start with $x_1=3,y_1=4$. Hence, $x_2=5$. Now, since $p\geq 7$, there exists a $t\in \{1,2,\dots,p-1\}$ such that $3t\equiv 5 \pmod{p}$, thus $x_2=3t$. Now, letting $y_2=4t$, we recover $x_3=5t=3t^2,\dots x_n=3t^{n-1}$, and since $p$ is prime, by Fermat's theorem, $t^{p-1}\equiv 1\pmod{p}$, hence we need to stop at some value (precisely, when $n=d+1$, where $d$ is the smallest positive integer for which $t^{d-1}\equiv 1\pmod{p}$), and that is precisely equal to $x_1$ (remember that we are working on modulo $p$).