[Math] Find x such that $x^2 \equiv 49$ (mod $pq$), $x \not\equiv\pm 7$ (mod $pq$)

Question

Suppose you have two distinct large primes $p$ and $q$.
Explain how you can find an integer $x$ such that $x^2 \equiv 49$
(mod $pq$), $x \not\equiv\pm 7$ (mod $pq$).

Answer 1

It's helpful to know the multiplicative structure of $(\mathbb{Z}/n\mathbb{Z})^*$. It is always a product of cyclic subgroups.

For powers of 2, we have $(\mathbb{Z}/2^k\mathbb{Z})^* \equiv C_2 \times C_{2^{k-2}}$.

For odd primes p, we have $(\mathbb{Z}/p^k\mathbb{Z})^* \equiv C_{(p-1)p^{k-1}}$.

Knowing the structure for the prime powers is enough; we can use the Chinese Remainder Theorem to see that

$(\mathbb{Z}/p_1^{i_1}\cdots p_r^{i_r}\mathbb{Z})^* = (\mathbb{Z}/p_1^{i_1}\mathbb{Z})^* \times \cdots \times (\mathbb{Z}/p_r^{i_r}\mathbb{Z})^*$.

Then $(\mathbb{Z}/pq\mathbb{Z})^* = C_{p-1} \times C_{q-1}$ has four solutions to $x^2=7^2$, and Bill's answer shows very nicely how to find them.