The Exercise

Shor’s algorithm factors a composite number $N$ by reducing factoring to order finding, that is, to finding the period of $a^x \bmod N$ for a number $a$ coprime to $N$, the one step that runs on a quantum computer. Some $N$ never reach that step, because a classical computation already gives a factor: an even $N$ has the factor $2$, and a perfect power $N = m^k$ with $k \geq 2$ has the factor $m$. The exercise is to show that $N = 15$ is the smallest number for which the order finding step is needed.^✦

Numbers That Need Order Finding

A natural number $N$ needs order finding if it is greater than $1$ and not prime, odd, and not a perfect power $m^k$ with natural numbers $m$ and $k \geq 2$: $$N > 1, \qquad N \text{ not prime}, \qquad N \text{ odd}, \qquad N \neq m^k \quad \text{for all } m, k \in \mathbb{N} \text{ with } k \geq 2.$$(1)^✦

The Claim

What Is Checked

The claim is stated over the natural numbers and the property (1) of needing order finding, with prime and perfect power in their usual sense.