MathDB

For an arbitrary positive integer

m

, not divisible by

3

, consider the permutation

x \mapsto 3x \pmod{m}

on the set

\{ 1,2,\dotsc ,m-1\}

. This permutation can be decomposed into disjointed cycles; for instance, for

m=10

the cycles are

(1\mapsto 3\to 9,\mapsto 7,\mapsto 1)

(2\mapsto 6\mapsto 8\mapsto 4\mapsto 2)

and

(5\mapsto 5)

. For which integers

m

is the number of cycles odd?

A. 734