**Added 3/13/13**: The OP has confirmed, in comments, that my interpretation (beginning with the next paragraph) is basically correct, aside from relaxing the condition that the $x_i$s be nonzero. I've added some additional remarks at the bottom here (and corrected one minor mistake in the original answer).

I agree with Benjamin Young (and Gerry Myerson), the question does not seem to be correctly posed. Here is a possible interpretation, albeit one that drops, at least initially, the condition $x_i\ne0$.

Given a prime $p$ congruent to 3 mod 4, one can ask for the largest $n$ such that for any choice of distinct $y_1,y_2,\ldots,y_n$ with $y_1y_2\cdots y_n\ne0\mod p$, there is a square number $r$ (including the possibility $r=0$) such that $y_i+r$ is a square (mod $p$) for $1\le i\le n$.

The sought-for $n$ depends on $p$. It's immediately clear that $0\le n \le p-1$ for *any* prime $p$; for $p\equiv3\mod4$, it's easy to see that $1\le n$. That's because any $y_1\ne0$ is either a quadratic residue mod $p$, in which case you can let $r=0$, or it's a non-residue, in which case you can let $r=-y_1$, which *is* a quadratic residue (hence square).

For $p=3$, it's easy to see that $n=1$: The only pair at stake is $(y_1,y_2)=(1,2)$, for which adding $r=1$ gives $(2,0)$, which includes the non-square number 2. (Obviously, adding $r=0$ also leaves the non-square 2.)

For $p=7$, the result is also $n=1$, but it takes a bit more checking to see that $(y_1,y_2)=(2,3)$ is an obstruction: The quadratic residues mod 7 are 1, 2, and 4, but $(2,3)+1=(3,4)$, $(2,3)+2=(4,5)$, and $(2,3)+4 = (6,0)$, each of which contains a non-residue. (I hope the notation here is clear.) As it happens, $(y_1,y_2)=(1,5)$ and $(4,6)$ are also obstructions (for all other pairs, there is a square $r$ that makes each number square), but it only takes one.

For $p=11$, though, we *do* find that $n$ is at least 2. The squares mod 11 are 0, 1, 3, 4, 5, and 9, and one can check the completeness and correctness of the following list (which covers all pairs with at least one non-square entry):

$$\begin{align}(1,2)+3&=(4,5)\cr
(1,6)+3&=(4,9)\cr
(1,7)+2&=(3,9)\cr
(1,8)+3&=(4,0)\cr
(1,10)+2&=(3,1)\cr
(2,3)+1&=(3,4)\cr
(2,4)+1&=(3,5)\cr
(2,5)+9&=(0,3)\cr
(2,6)+3&=(5,9)\cr
(2,7)+2&=(4,9)\cr
(2,8)+1&=(3,9)\cr
(2,9)+2&=(4,0)\cr
(2,10)+2&=(4,1)\cr
(3,6)+9&=(1,4)\cr
(3,7)+9&=(1,5)\cr
(3,8)+1&=(4,9)\cr
(3,10)+1&=(4,0)\cr
(4,6)+5&=(9,0)\cr
(4,7)+5&=(9,1)\cr
(4,8)+1&=(5,9)\cr
(4,10)+5&=(9,4)\cr
(5,6)+9&=(3,4)\cr
(5,7)+9&=(3,5)\cr
(5,8)+4&=(9,1)\cr
(5,10)+4&=(9,3)\cr
(6,7)+9&=(4,5)\cr
(6,8)+3&=(9,0)\cr
(6,9)+3&=(9,1)\cr
(6,10)+5&=(0,4)\cr
(7,8)+4&=(0,1)\cr
(7,9)+5&=(1,3)\cr
(7,10)+5&=(1,4)\cr
(8,9)+3&=(0,1)\cr
(8,10)+1&=(9,0)\cr
(9,10)+5&=(3,4)\cr
\end{align}$$

(Note: Several pairs allow more than one choice of $r$. In general I've used the *smallest* $r$ among 0, 1, 3, 4, 5, and 9, except that I've tried to avoid producing a 0 in the sum pair whenever possible. If there's a more sensible way to summarize all the checking, I'm all ears.)

Luckily, it's easy to show that $(1,2,7)$ is an obstruction to $n=3$ for $p=11$, so we can conclude that $n=2$ is the maximum in this case. What one gets for the largest $n$ when $p=19$, I'll leave for someone else to work on. I'll merely note that one might go ahead and reinstate the prohibition on using the square 0, but if you do, you get $n=0$ for $p=3$ and $n=1$ for $p=7$ and $11$. Whether you ever get anything larger is unclear.

**Added 3/13/13**: The "immediately clear" upper bound $n\le p-1$ came from the mindless observation that the $y_i$s are distinct and nonzero. The somewhat more thoughtful observation that the $(y_i+r)$s must all be distinct squares not equal to the square $r$ shows that $n\le (p-1)/2$. But we can do a lot better than that by working backwards: Start with distinct squares $r,s_1,s_2,\ldots,s_n$ and let $y_i=s_i-r$ for $1\le i\le n$. We have $(p+1)/2\choose n$ choices for the $s_i$s, leaving ${p+1\over2}-n$ choices for $r$, whereas there are $p-1\choose n$ choices for the $y_i$s, so the maximum $n$ must satisfy

$$({p+1\over2}-n){(p+1)/2\choose n} \ge {p-1\choose n}$$

For $p=7$, this is $(4-n){4\choose n} \ge {6\choose n}$, from which we see that $n=1$ is OK (as we already know) but $n=2$ is not, since $12 < 15$. (In fact this is how I caught an error in my original answer. I initially thought there were only two "obstructions" to $n=2$ for $p=7$, but this comparisons shows there must be at least *three*. I went back and realized that I had decided that adding 4 to the pair $(1,5)$ would produce a pair of squares, but of course $4+1=5$ is not a square mod 7. Note that for every other pair, there is exactly one value for $r$ that turns it into a pair of squares, since $15-12=3$.)

For $p=11$, the upper bound inequality is

$$(6-n){6\choose n}\ge {10\choose 2}$$

Doublechecking $n=2$, we have $60\ge 45$, but for $n=3$ we have

$$(6-3){6\choose 3} = 3\cdot20 = 60 < {10\choose3} = 120,$$

so we could have concluded that $n=2$ is the maximum for $p=11$ without bothering to look for the obstruction $(1,2,7)$.

For $p=19$, it's easy to check that $n=3$ satisfies the upper bound inequality but $n=4$ does not, so we can conclude that the maximum $n$ is between 1 and 3, but that's about all we can say without exhaustive checking.

A quicker, cruder upper bound comes from letting $s_1,s_2,\ldots,s_n,r$ range over *all* squares, including repetitions, and noting that this should account for all possible $y_i$s, including repetitions and 0s. One needs $({p+1\over2})^{n+1} \ge p^n$, or

$$n \le \log({p+1\over2})/\log({2p\over p+1})$$.

Finally, the OP really wants all the squares to be (non-zero) quadratic residues. This simply changes the upper bound inequality to

$$({p-1\over2}-n){(p-1)/2\choose n} \ge {p-1\choose n}.$$

This rules out $n=2$ for $p=11$ (since $(5-2){5\choose2} = 3\cdot10 = 30 < {10\choose2}=45$), but allows it for $p=19$, since $(9-2){9\choose2}=7\cdot36 = 252 > {18\choose2}=153$. It's easy to see that $n=3$ is ruled out for $p=19$. The OP claims (in comments) to have checked that $n=2$ actually *is* the maximum in this case.

allprimes, and not just primes congruent to 3 mod 4. – Barry Cipra Mar 13 '13 at 13:37