Factor It 4

The identity $x^n - 1 \; = \; \prod_{d|n} \Phi_d(x)$ is the factorisation of $x^n-1$ into irreducibles, where $\Phi_m(x)$ is the $m$ th cyclotomic polynomial. Thus $x^n-1$ is a product of $\sigma_0(n)$ irreducible factors, where $\sigma_0(n)$ is the number of divisors of $n$ . We want to determine the numbers $n$ such that $\sigma_0(n) = p$ .

Note that $\sigma_0(n) = (a_1+1)(a_2+1)\cdots (a_N+1)$ if $n = q_1^{a_1}q_2^{a_2}\cdots q_N^{a_N}$ is the prime factorisation of $n$ (so that $q_,q_2,...q_N$ are distinct primes and $a_1,a_2,...,a_N$ are positive integers). Thus it is clear that $\sigma_0(n)$ is composite whenever $n$ has two or more distinct prime factors. Thus, for $\sigma_0(n)$ to be prime, $n$ must be a prime power. If $n = q^u$ where $q$ is prime and $u$ is a positive integer, then $\sigma_0(n) = u+1$ . Thus the only integers $n$ such that $\sigma_0(n)$ is a prime $p$ are $n = q^{p-1}$ for some prime $q$ .

Thus the smallest possible such integer is $2^{p-1}$ .