|
2 | added 214 characters in body | ||
|
If you know any factors of $N$, it's easy to find non-trivial solutions of $a^2\equiv b^2\pmod N$. If $m$ and $n$ are (relatively prime) factors of $N$, then given any $a$, take $b$ to solve $b\equiv a\pmod m$, $b\equiv-a\pmod n$. EDIT: A bit careless of me, let's try again. If $N$ is odd and $N=mn$ is non-trivial with $\gcd(m,n)=1$, then the construction above, with $\gcd(a,N)=1$, gives a non-trivial solution of $a^2\equiv b^2\pmod N$. |
||||
|
|
1 |
|
||
|
If you know any factors of $N$, it's easy to find non-trivial solutions of $a^2\equiv b^2\pmod N$. If $m$ and $n$ are (relatively prime) factors of $N$, then given any $a$, take $b$ to solve $b\equiv a\pmod m$, $b\equiv-a\pmod n$. |
||||
