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
    I see we have $4$ total solutions, and so when $p$ and $q$ divide different factors (either $p$ or $q$ dividing $(x-y)$ then there are two solutions. So we have $\dfrac{2}{4} = \dfrac{1}{2}$ probability of $p$ and $q$ dividing different factors. I don't understand the implications this has, namely the $\gcd(xy, n)$ having non-trivial factors. What does it matter if both $p$ and $q$ divide (x+y)$ or (x-y)$?2012-10-18
  • 0
    @codeMasterFiveThousand: I have added the full end of the argument.2012-10-18
  • 0
    Looks good, but I am not clear as to why $q$ cannot divide $2x$ since $\gcd(xy, n) = 1$ I see that $q$ being odd cannot divide an even number $2x$ but what does $\gcd(xy, n) = 1$ mean here?2012-10-18
  • 0
    I know that $\gcd(xy, n) = 1$ means that $xy$ is relatively prime to $n$ but why does it contradict $q$ dividing $(x-y)$$2012-10-18
  • 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