= Solution
Write $n=2^r m$ with $m$ odd. If $m>1$, the <polynomial factor> of $X^m+1$ by $X+1$, evaluated at $X=10^{2^r}$, supplies a proper divisor. Therefore \b[$n$ must be a power of two]. Conversely this is only a necessary condition for <primality testing>.
For a <prime factor> $p$ of the number, $p$ is odd and does not divide $10$. Its <multiplicative order> $d$ satisfies $d\mid 2n$ but $d\nmid n$, since $10^n\equiv-1\pmod p$. When $n$ is a power of two, every proper divisor of $2n$ divides $n$, so $d=2n$. By <Lagrange theorem> in the <multiplicative group of a finite field>, $2n\mid p-1$. Thus $\boxed{p\equiv1\pmod{2n}}$.
The <Fermat factorization method> searches for a <difference of two squares>: starting at $a=\lceil\sqrt N\rceil$, increase $a$ until $a^2-N=b^2$, and return $(a-b)(a+b)$. Every factorization of an odd integer has this form, with $a=(d+e)/2$ and $b=(e-d)/2$. For $N=10001$, the successive differences at $a=101,102,103,104,105$ are $200,403,608,815,1024$. The last is $32^2$, giving $\boxed{10001=73\cdot137}$. Trial division by the <primes> up to their respective square roots confirms that both factors are <prime>.
Back to article page
