Factoring $pq$ if $x \equiv y \mod p$ and $x \not\equiv y \mod pq$

Question

Let $G = \mathbb{Z_N}$ be a finite cylcic group of order N = $pq$ . The generic Pollard's Rho algorithm searches for 2 elements $x,y \in G$, such that $x \equiv y \mod p$ and $x \not\equiv y \mod pq$ . How can we factor N with such a collision $x \equiv y \mod p$ ?

$\textbf{My approach}$

$ x \equiv y \mod p \Leftrightarrow (x-y) | p \Rightarrow \gcd(x-y,p) = 1 $ or $p$, because $p$ is prime. However, $x \not\equiv y \mod pq \Leftrightarrow (x-y) \not| \ pq $

How can that be? $x-y$ must be either $1$ or $p$ , so shouldn't it always divide $pq$?

Answer 1

Your mistake is here: $ x \equiv y \mod p \Leftrightarrow (x-y) | p 1 $

Actually it is $ x \equiv y \mod p \Leftrightarrow p | xyz $

Hope you understood. Now you can carry forward.