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

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$).

-
Is this homework? –  Aryabhata Oct 8 '10 at 1:10
Only AFTER reading the answers I understood that x!=+-7 did NOT mean "x factorial is congruent to....". PLEASE, use TeX ! –  Andrea Mori Oct 8 '10 at 16:03

HINT $\rm\ pq\:|\:(x-7)(x+7)\:,\$ not $\rm\ pq\:|\:x\pm7\ \Rightarrow\ p\:|\:x- 7,\ q\:|\:x+7\$ or vice versa.

Also, you need $\rm\: -7\not\equiv 7\$ so $\rm\ p,\ q\$ coprime to $\ \ldots$

-

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.

-

You could solve $y^2\equiv1$ (mod $pq$) with $y\not\equiv\pm1$ (mod $pq$) and then take $x=7y$. :-)

-