New answers tagged


Consider two numbers $a$ and $b$ that square to the same value modulo $n$ and don't just differ by the sign. $$a^2 \equiv b^2 \pmod n2$$ $$(a-b)(a+b) \equiv 0 \pmod n$$ Neither of the factors on the left is 0 (or equivalently a multiple of $n$), thus each of them must contain one of the prime factors of $n$. Thus you can use $\operatorname{GCD}(a-b, n)$ ...

Top 50 recent answers are included