given that: $1683411^{2}=4\mod(2195689)$
calculate a non trivial divider of $2195689$ (without using calculator)
My try: $$ 1683411^{2}=4\,mod(2195689) \\~\\ 1683411^{2}-4=0\,mod(2195689) \\~\\ (1683411-2)(1683411+2)=0\,mod(2195689) \\~\\ (1683409)(1683413)=0\,mod(2195689) $$
and hence :
$(1683409)(1683413)=2195689\cdot k\,\,\,\,$ ($k\in\mathbb{Z}$)
now I think I should use Euclid's algorithm, but I'm not sure how...
edit:
I know $\frac{(1683409)(1683413)}{2195689}=k$
and hence $2195689$ must have common dividers with $1683409$ or $1683413$ am I right?