Theorem B

The function defined by

is periodic with period . The induced function is a permutation, and its order is a power of 2.

Proof B

(sketch). The theorem is established by induction on k, using the inductive hypotheses:

(1) is periodic with period for . In fact

 

for .

(2) is periodic with period .

(3) and are periodic with period .

(4) is a permutation whose order divides . Also

 

I omit the details.