Past exam of the mathematics course of the University of Cambridge / 2015 / ii / Paper 4 / 1H / 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 $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(\mathrm{mod}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\equiv 1(\mathrm{mod}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\cdot 137}$. Trial division by the primes up to their respective square roots confirms that both factors are prime.