2 removed all of my silly mistakes

I don't think the result is actually true - I didn't see how to actually construct such a set, with or without arbitrary choices. At any rate, here

Here is something partial, maybe I noticed - no idea if it will be useful in either directionhelps:

Suppose $A\subset\mathbb{Z}$ has the property that for each odd prime $p$ and $\phi_p:\mathbb{Z}\rightarrow\mathbb{Z}/p\mathbb{Z}$, we have $|\phi_p(A)|=\frac{p-1}{2}$. Consider the map $f_p:\mathbb{Z}/p\mathbb{Z}\rightarrow\mathbb{Z}/p\mathbb{Z}$ with $f_p(x)=x^2$. Then $|f_p(\phi_p(A))|\leq\frac{p-1}{2}$. Since there are $\frac{p+1}{2}$ quadratic residues mod $p$, we must have that for each odd prime $p$, there is an $x_p\in\mathbb{Z}/p\mathbb{Z}$ such that $a^2\not\equiv x_p^2\bmod p$ for all $a\in A$ (which is $\Leftrightarrow$ $a\not\equiv \pm x_p\bmod p$).

Thus, if we could show that for any infinite set of squares $S$ in $\mathbb{Z}$ (we would specifically be looking at $A^2$), there necessarily exists at least one prime $p$ such that $|\phi_p(S)|=\frac{p+1}{2}$ (or equivalently, every quadratic residue in $\mathbb{Z}/p\mathbb{Z}$ is represented by some element of $S$), then we can show that what this question asks for is impossible.

I also noticed that, since $A$ is infinite, $P=\{$odd primes dividing some $a\in A\}$ must be infinite as well. Don't really know where to go with that either - just throwing it out there.

1

I don't think the result is actually true - I didn't see how to actually construct such a set, with or without arbitrary choices. At any rate, here is something partial, maybe it will be useful in either direction:

Suppose $A\subset\mathbb{Z}$ has the property that for each odd prime $p$ and $\phi_p:\mathbb{Z}\rightarrow\mathbb{Z}/p\mathbb{Z}$, we have $|\phi_p(A)|=\frac{p-1}{2}$. Consider the map $f_p:\mathbb{Z}/p\mathbb{Z}\rightarrow\mathbb{Z}/p\mathbb{Z}$ with $f_p(x)=x^2$. Then $|f_p(\phi_p(A))|\leq\frac{p-1}{2}$. Since there are $\frac{p+1}{2}$ quadratic residues mod $p$, we must have that for each odd prime $p$, there is an $x_p\in\mathbb{Z}/p\mathbb{Z}$ such that $a^2\not\equiv x_p^2\bmod p$ for all $a\in A$ (which is $\Leftrightarrow$ $a\not\equiv \pm x_p\bmod p$).

Thus, if we could show that for any infinite set of squares $S$ in $\mathbb{Z}$ (we would specifically be looking at $A^2$), there necessarily exists at least one prime $p$ such that $|\phi_p(S)|=\frac{p+1}{2}$ (or equivalently, every quadratic residue in $\mathbb{Z}/p\mathbb{Z}$ is represented by some element of $S$), then we can show that what this question asks for is impossible.

I also noticed that, since $A$ is infinite, $P=\{$odd primes dividing some $a\in A\}$ must be infinite as well. Don't really know where to go with that either - just throwing it out there.