2
$\begingroup$

I want to prove the following:

Let $n = pq$, with $p, q$ distinct odd primes. Let $x,y$ be random integers with $\gcd(xy, n) = 1$ and $x^2 \equiv y^2 \mod n$. Prove that there is a 50-50 chance that $\gcd(n, x-y)$ is a nontrivial factor of n.

I know: $n|(x^2-y^2) \iff n|(x-y)(x+y) \iff nk = (x-y)(x+y)$ for some $k\in \mathbb{Z}$.

Now I want to enumerate over some cases (possibilities from this equation):

  1. $(x-y) = n$
  2. $(x-y) = 1$
  3. $k$ divides $(x-y)$
  4. $k$ does not divide $(x-y)$

I know I am missing something. I am just not quite sure where to go from here...

1 Answers 1

2

Hint: We have $x^2\equiv y^2\pmod{n}$ iff $x^2\equiv y^2\pmod{p}$ and $x^2\equiv y^2\pmod{q}$.

For given $y$, the congruence $x^2\equiv y^2\pmod{p}$ has two solutions, namely $x\equiv y\pmod{p}$ and $x\equiv -y\pmod{p}$. Similarly, for fixed $y$ the congruence $x^2\equiv y^2\pmod{q}$ has two solutions.

So by the Chinese Remainder Theorem, for fixed $y$ the congruence $x^2\equiv y^2\pmod{n}$ has $4$ solutions.

Show that the two uninteresting ones, where the signs match, do not produce a non-trivial factor, but the other two do.

Added detail: Suppose for example that $x\equiv y\pmod{p}$ and $x\equiv -y\pmod{q}$. Then $p$ divides $x-y$, and $q$ divides $x+y$. But $q$ does not divide $x-y$. For if $q$ divided $x-y$, then $q$ would divide $(x-y)+(x+y)$, that is, $2x$. This is impossible, since $\gcd(xy,n)=1$ and $q$ is odd.

Since $p$ divides $x-y$, but $q$ doesn't, $\gcd(x-y,n)\ne 1$, and $\gcd(x-y,n)\ne n$. It follows that $\gcd(x-y,n)=p$.

Essentially the same argument shows that if $x\equiv -y\pmod{p}$ and $x\equiv y\pmod{q}$, then $\gcd(x-y,n)=q$.

  • 0
    Remember that I was assuming $p$ divides $x-y$ and $q$ divides $x+y$. **Then** I wrote that **if** furthermore $q$ divides $x-y$, then $q$ divides $(x-y)+(x+y)=2x$ and therefore $q$ divides x. This is impossible, for if $q$ divides x, then since $q$ divides $n$, it follows that $q$ divides $\gcd(xy,n)$.2012-10-18