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$).
Find x such that $x^2 \equiv 49$ (mod $pq$), $x \not\equiv\pm 7$ (mod $pq$)
-
1Is this homework? – 2010-10-08
-
2Only AFTER reading the answers I understood that x!=+-7 did NOT mean "x factorial is congruent to....". PLEASE, use TeX ! – 2010-10-08
3 Answers
You could solve $y^2\equiv1$ (mod $pq$) with $y\not\equiv\pm1$ (mod $pq$) and then take $x=7y$. :-)
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.
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$