0
$\begingroup$

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

  • 1
    Is this homework?2010-10-08
  • 2
    Only 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 3

1

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

3

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.

2

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$