= Solution
The supplied congruence is a <congruence of squares>, since $25=5^2$. Hence
$$
3953\mid(2886-5)(2886+5).
$$
A nontrivial square root modulo a product of two odd primes may agree with $+5$ modulo one prime and $-5$ modulo the other. Taking greatest common divisors separates these factors. The <Euclidean algorithm> gives
$$
\gcd(3953,2881)=67,\qquad\gcd(3953,2891)=59.
$$
For example the successive remainders for the first computation are $1072,737,335,67,0$; for the second they are $1062,767,295,177,118,59,0$. Therefore
$$
\boxed{3953=59\cdot67.}
$$
Both numbers are prime by trial division by primes at most their square roots. More generally, given $a^2\equiv b^2\pmod N$ with $a\not\equiv\pm b\pmod N$, computing $\gcd(N,a-b)$ often produces a proper factor. The method requires no prior knowledge of which prime gives which sign, and is the basic factor-extraction step in congruence-of-squares algorithms.
Back to article page
