I study at University of Warsaw and we have subject called Number Theory. There was set of optional tasks to do in december given to students by M. Skalba and M. Rotkiewicz on this subject. That was only not-so-obvious problem from this set and it looks very nice, so I simply wanted to know how to solve it :)

Well, that was problem given to me by profesor at University - this problem isn't from any contest known to me. Yesterday I only prove that we can find $p$ prime that satisfies $(q_i/p) = a_i$ for finitely many primes $q_i$ and any $a_i\in\{-1, 1\}$. Later my friend finish this prove in the same way as you. Thank you very much for answer.