Originally Posted by
desiresjab
We may further notice that when both p and q are primes of the species 4n+3, their squares always wrap around the other modulus so that p2≡2 (mod q) and q2≡1 (mod p), or vice versa. They will always express this relationship when squared within the modulus of the other. This is a fact of the universe, as inviolate as 2 is the successor of 1.
One always checks first to see if the larger of p and q simply reduces to a familiar square under the other as modulus. If so, the work is done. Otherwise one starts squaring n's to see if any wraps around to the value of p, under q as modulus, or vice versa.