Now for the other direction:

-------

**Lemma:** Given

, suppose

is the smallest number greater than

such that

and

where

, then

.

**Proof:** By the division algorithm,

where

. So we then get

. Since

and

, by the minimality of

this forces

. So we see that

.

-------

Suppose

is solvable. This implies

is solvable. So observe that it's equivalent to show

solvable implies

.

Since

is odd,

, so we have the following:

So as you can see,

is the smallest exponent greater than

such that

. Now by Fermat's little theorem, since

. By our above Lemma, this implies

.