I came across Lenstra ECM algorithm and I wonder why it works. Please refer for simplicity to Wikipedia section Why does the algorithm work
I NOT a math expert but I understood first part well enough (I suppose), what I miss is
When this is the case, $kP$ does not exist on the original curve, and in the computations we found some $v$ with either $\text{gcd}(v,p)=p$ or $\text{gcd}(v,q)=q$, but not both. That is, $\text{gcd}(v,n)$ gave a non-trivial factor of $n$.
As far as I know this has to do with the fact that $E(\mathbb Z/n\mathbb Z)$ is not a group if $n$ is not prime so some element (i.e. $x_1-x_2$) is not invertible but what is the link between non invertible elements and $n$ factors?
Thanks to everyone