Stack Exchange network consists of 183 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.
If you square 2 repeatedly modulo a prime p that is 3 mod 4, it cycles through a cyclic group of odd order (soon enough). You probably want to choose p so that it hits the residue class of -k; because then you are done. A proof conditional on the Artin conjecture on primitive roots then looks likely (i.e. on GRH) via quadratic reciprocity and enough on primes in arithmetic progressions. It gets more interesting if it is possible to do something with a small sledgehammer.
Try writing down some notation, then. Since the cocycle is not uniquely determined, you need to choose elements of P and Q and see why there is one orbit under ~, and describe it.
Sorry for the "thinking aloud". The idea I have now added seems to solve the problem "up to a finite number of possibilities". But perhaps it will serve as a better basis for discussion.