I think we can let $p \ge 7$. (Indeed, verify manually the primes lower than the given bound in the problem. Thus, this better result must be true by the problem.)

We will prove the result for all $p > 5.$ Suppose we have an integer solution $(x, y)$ to $x^2 + y^2 \equiv 1 \pmod{p}.$ Because $x^2 \equiv \left(p - x\right)^2 \pmod{p}$, we may assume that $0 \le x, y \le \tfrac{p - 1}{2}.$ Then as long as $(x, y) \ne (0, \pm1), (\pm1, 0)$, we may establish the inequality $p + 1 \le x^2 + y^2 < (p - 3)p + 1$ on account of $p > 5.$ Thus, the pair $(x, y)$ will satisfy the problem statement. Therefore, because we discount the pairs $(0, \pm1)$ and $(\pm1, 0)$, it suffices to show that there are at least $5$ solutions to the equation $x^2 + y^2 = 1$ in $\mathbb{Z}/p\mathbb{Z}.$ While its not strictly necessary to solve this problem, we can show that this equation has $p + 1$ solutions for $p \equiv 3 \pmod{4}$ and $p - 1$ solutions for $p \equiv 1 \pmod{4}.$ We work in $\mathbb{Z}/p\mathbb{Z}.$ Note that for a fixed $x$, the equation $x^2 + y^2 = 1$ has precisely $1 + \left(\tfrac{1 - x^2}{p}\right)$ solutions. Therefore, the total number of solutions to $x^2 + y^2 = 1$ is given by \[N := \sum\limits_{x \in \mathbb{Z}/p\mathbb{Z}} \left[1 + \left(\frac{1 - x^2}{p}\right)\right] = p + \sum\limits_{x \in \mathbb{Z}/p\mathbb{Z}} \left(\frac{1 - x^2}{p}\right).\] To simplify the algebra, define \[S_3 := \sum\limits_{x \in \left(\mathbb{Z}/p\mathbb{Z}\right)^{\times}} \left(\frac{1 - x^2}{p}\right) \quad \text{and} \quad S_1 := \sum\limits_{x \in \mathbb{Z}/p\mathbb{Z}} \left(\frac{1 - x^2}{p}\right).\] Now, we consider two cases: If $p \equiv 3 \pmod{4}$, then by evaluating the $x = 0$ term of $N$, we deduce that $N = S_3 + p + 1.$ Now, note that as $x$ ranges over all elements of $\left(\mathbb{Z}/p\mathbb{Z}\right)^{\times}$, so does $\tfrac{1}{x}.$ Therefore, \[S_3 = \sum\limits_{x \in \left(\mathbb{Z}/p\mathbb{Z}\right)^{\times}}\left(\frac{1 - \left(\frac{1}{x}\right)^2}{p}\right) = \sum\limits_{x \in \left(\mathbb{Z}/p\mathbb{Z}\right)^{\times}} \left(\frac{x^2 - 1}{p}\right) = \sum\limits_{x \in \left(\mathbb{Z}/p\mathbb{Z}\right)^{\times}} \left(\frac{-1}{p}\right)\left(\frac{1 - x^2}{p}\right) = -S_3,\] where the last step follows from $\left(\tfrac{-1}{p}\right) = -1$ on account of $p \equiv 3 \pmod{4}.$ Therefore $S_3 = 0$ and $N = p + 1$, as claimed. $\blacksquare$ Now, suppose that $p \equiv 1 \pmod{4}.$ Note that $\left(\tfrac{-1}{p}\right) = 1$ and $N = p + S_1.$ Then for any $a \ne 0$, as $x$ ranges over all elements of $\mathbb{Z}/p\mathbb{Z}$, so does $\tfrac{x}{a}.$ Therefore, \[S_1 = \sum\limits_{x \in \mathbb{Z}/p\mathbb{Z}} \left(\frac{x^2 - 1}{p}\right) = \sum\limits_{x \in \mathbb{Z}/p\mathbb{Z}} \left(\frac{\left(\frac{x}{a}\right)^2 - 1}{p}\right) = \sum\limits_{x \in \mathbb{Z}/p\mathbb{Z}} \left(\frac{x^2 - a^2}{p}\right) = \sum\limits_{x \in \mathbb{Z}/p\mathbb{Z}} \left(\frac{x + a}{p}\right)\left(\frac{x - a}{p}\right) = \sum\limits_{x \in \mathbb{Z}/p\mathbb{Z}} \left(\frac{x}{p}\right)\left(\frac{x - 2a}{p}\right),\] where the last step follows from the variable change $x \mapsto x + a.$ By summing over $2a = 1, 2, \cdots , p - 1$, we obtain exactly one term of the form $\left(\tfrac{b}{p}\right)\left(\tfrac{c}{p}\right)$ for every pair $(b, c)$ with $b \ne c.$ Therefore, \[(p - 1)S_1 = \sum_{\substack{b, c \in \mathbb{Z}/p\mathbb{Z} \\ b \ne c}} \left(\frac{b}{p}\right)\left(\frac{c}{p}\right) = \left[\sum\limits_{x \in \mathbb{Z}/p\mathbb{Z}} \left(\frac{x}{p}\right)\right]^2 - \sum\limits_{x \in \mathbb{Z}/p\mathbb{Z}} \left(\frac{x}{p}\right)^2 = -p + 1.\] Thus $S_1 = -1$ and $N = p - 1$ as desired. $\square$

stronger problem: $a$ is a natural number and $p$ is a prime such that $p\nmid a,p>5$ prove that we can write one of $p+a,2p+a,\dots,\left(\frac{p-3}{2}\right)p+a$ in a form $x^2+y^2$. Lemma: if $p>5$ is prime then there is one element in the set $\{-x^2+a|1\le x\le \frac{p-1}{2}\}$ which is quadratic reside modulo $p$. proof: see Iranian third round number theory p3 from the lemma there is an integer $x$ such that $-x^2+a\equiv y^2\pmod{p}$ thus $\frac{(p-1)^2}{2}\ge x^2+y^2-a=pk\Longrightarrow \frac{p-3}{2}\ge k$ so $x^2+y^2=pk+a$ where $k\le \frac{p-3}{2}$ DONE

Lemma: If $p>30$ and $p \nmid a,b^2-4ac,$ then $$\sum_{x=1}^{p}\left(\frac{ax^2+bx+c}{p} \right)=-\left(\frac{a}{p} \right)$$Proof: As for the proof, we will actually need a well known sub-lemma: Sub-lemma: If $0 \le a < p-1$ then $1^a+...+(p-1)^a \equiv 0 \pmod p$ Proof of sub-lemma: Trivial, just take $g$ to be primitive root, then we have $$1^a+...+(p-1)^a \equiv \frac{g^{(p-1)a}-1}{g^{a}-1} \equiv 0 \pmod p \blacksquare$$It is well known that $a^{\frac{p-1}{2}} \equiv \left(\frac{a}{p} \right) \pmod p$ hence for all $x=1,...,p$ we have $$\left(\frac{ax^2+bx+c}{p} \right) \equiv (ax^2+bx+c)^{\frac{p-1}{2}} \equiv a_{p-1}x^{p-1}+...+a_1x+a_0 \pmod p$$So, summing through $x=1,...,p$ we obtain, by sub-lemma, that $$\sum_{x=1}^{p}\left(\frac{ax^2+bx+c}{p} \right) \equiv -a_{p-1} \equiv -a^{\frac{p-1}{2}} \equiv -\left(\frac{a}{p} \right) \pmod p$$and now it's easy to finish $\blacksquare$ As for the problem, we need to count the number of solutions of $x^2+y^2 \equiv 1 \pmod p,$ call this number $U.$ It is evident that $$U=\sum_{x+y=1}(1+\left(\frac{x}{p} \right)) \cdot (1+\left(\frac{y}{p} \right))=p+\sum_{x+y=1}\left(\frac{xy}{p} \right)=p+\sum_{x=1}^{p}\left(\frac{-x^2+x}{p} \right)=p-\left(\frac{-1}{p} \right) > p-2$$So, wlog let $0 \le x,y \le \frac{p-1}{2}$ with $x,y$ non trivial (doable, by previous). Now it follows that $p+1 \le x^2+y^2 \le \frac{(p-1)^2}{2} < p(p-3)+1 \blacksquare$

Iran problems are amazingly beautiful.

The problem is true for any $p\geq 7$. Consider $x=\pm\frac{3}{5}\pmod p$, $y=\pm\frac{4}{5}\pmod p$, such that $x,y\in\{1,2,\dots,\frac{p-1}{2}\}$. Then $x^2+y^2\equiv 1\pmod p$ and $x^2+y^2<(x+y)^2\leq(p-1)^2$, so we are done.

Why is math90's solution so easy in comparison to the others?

andria wrote: stronger problem: $a$ is a natural number and $p$ is a prime such that $p\nmid a,p>5$ prove that we can write one of $p+a,2p+a,\dots,\left(\frac{p-3}{2}\right)p+a$ in a form $x^2+y^2$. It's well-known that $x^2+y^2 \equiv a \pmod p$ has $p+(-1)^{\frac{p-1}{2}}$ solutions if $p$ doesn't divide $a$ so you can make the problem even stronger by having at least some of them sum of squares instead of one(haven't checked in detail how many.)

Plz Check Mine - $p =7$ can be checked manually , assume $p>7$ Note that number of solutions to $x^2 + y^2 \equiv 1 (mod p)$ is $ p-(-1)^{p-1}$ which is atleast $p-1$ , and we can assume $ 0 \le x,y \le \frac{p-1}{2}$ , and by solving we get $x^2 + y^2 \le (p-3)p +1$ and number of solutions to $x^2 +y^2 = 1$ are only $2$ , so rest atleast $p-3$ solutions will get distributed to $p +1 , 2p+1 , .... (p-3)p+1$ , hence atleast one of the numbers can be represented in form $x^2 + y^2$ $\blacksquare$

MatBoy-123 wrote: Plz Check Mine - $p =7$ can be checked manually , assume $p>7$ Note that number of solutions to $x^2 + y^2 \equiv 1 (mod p)$ is $ p-(-1)^{p-1}$ which is atleast $p-1$ , and we can assume $ 0 \le x,y \le \frac{p-1}{2}$ , and by solving we get $x^2 + y^2 \le (p-3)p +1$ and number of solutions to $x^2 +y^2 = 1$ are only $2$ , so rest atleast $p-3$ solutions will get distributed to $p +1 , 2p+1 , .... (p-3)p+1$ , hence atleast one of the numbers can be represented in form $x^2 + y^2$ $\blacksquare$ How can you prove that the number of solutions to $x^{2}+y^{2}\equiv 1(modp)$ is $p-(-1)^{p-1}$

mrhandsomeugly wrote: MatBoy-123 wrote: Plz Check Mine - $p =7$ can be checked manually , assume $p>7$ Note that number of solutions to $x^2 + y^2 \equiv 1 (mod p)$ is $ p-(-1)^{p-1}$ which is atleast $p-1$ , and we can assume $ 0 \le x,y \le \frac{p-1}{2}$ , and by solving we get $x^2 + y^2 \le (p-3)p +1$ and number of solutions to $x^2 +y^2 = 1$ are only $2$ , so rest atleast $p-3$ solutions will get distributed to $p +1 , 2p+1 , .... (p-3)p+1$ , hence atleast one of the numbers can be represented in form $x^2 + y^2$ $\blacksquare$ How can you prove that the number of solutions to $x^{2}+y^{2}\equiv 1(modp)$ is $p-(-1)^{p-1}$ It can be proved using the fact that number of solutions to $x^2 \equiv a mod p$ has $(\frac{a}{p})$$+1$ solutions and then in $x^2+y^2$ $\equiv 1 mod p$ fix a $y$ and then find number of $x$ and do the sum over all $x$..

Lemma: The number of solutions to $x^2+y^2 \equiv a \pmod p$ has $ p-(-1)^{p-1}$ solutions when $p|a$ and $p-(-1)^{\frac{p-1}{2}}$ in all other cases. Of course this implies that there are atleast $p-1$ solutions and discounting all the trival solutions we get $p-5$ solutions so we must need $p>5$ which is already given.

Actually, if we find a single solution to $$x^2+y^2 \equiv 1 \pmod p$$with $p \nmid x, y$, then we're done as we can assume $x, y \leq \frac{p-1}2$, and $x^2+y^2$ is clearly in the desired range. On the other hand it is well-known that the number of solutions to this congruence is either $p-1$ or $p+1$, and as $p-1 \geq 5$, modulo the four trivial solutions, there must exist a nontrivial solution, so we are done.

Actually, if we find a single solution to $$x^2+y^2 \equiv 1 \pmod p$$with $p \nmid x, y$, then we're done as we can assume $x, y \leq \frac{p-1}2$, and $x^2+y^2$ is clearly in the desired range. On the other hand it is well-known that the number of solutions to this congruence is either $p-1$ or $p+1$, and as $p-1 \geq 5$, modulo the four trivial solutions, there must exist a nontrivial solution, so we are done.

math90 wrote: The problem is true for any $p\geq 7$. Consider $x=\pm\frac{3}{5}\pmod p$, $y=\pm\frac{4}{5}\pmod p$, such that $x,y\in\{1,2,\dots,\frac{p-1}{2}\}$. Then $x^2+y^2\equiv 1\pmod p$ and $x^2+y^2<(x+y)^2\leq(p-1)^2$, so we are done. Actually, my proof also shows that $$x^2+y^2\le 2\left(\frac{p-1}{2}\right)^2=\frac{p^2-2p+1}{2}<\frac{p(p-1)}{2}+1$$so we can improve the initial bound to $\frac{p-3}{2}p+1$.

posting for storage: