In his answer to this previous MO question, Gjergji Zaimi referred to the statement that for every finite group $G$ of order $n$, there is a bijection $\sigma \colon G \to \mathbb{Z}/n\mathbb{Z}$ satisfying $$o(\sigma(g))\geq o(g)$$ for all $g\in G$. However, as Marty Isaacs pointed out, the "proof" of this fact that appeared in the Amer. Math. Monthly is flawed (or at least incomplete).

Does anyone know of a valid proof (or counterexample) of this fact?

**Added:**
Since this question has been without answer for about 2 weeks now, I'm adding some more details that might help (perhaps not everyone has access to the paper in Amer. Math. Monthly.)

The "proof" in *loc. cit.* goes as follows:
Let $G_k = \{\,g \in G: g^k = 1\,\}$.
For $d \mid n$, we inductively define a set $S_d$ consisting of $\phi(d)$ elements in $G_d$, where $\phi$ is Euler's totient function. These sets will be pairwise disjoint; since
$\sum_{d \mid n} \phi(d) = n$, they thus partition $G$.

Let $S_1 = \{1\}$. Suppose that $k$ divides $n$ and that $S_d$ has been constructed for all $d < k$. By a theorem of Frobenius (see M. Hall, The Theory of Groups, Macmillan, 1959, p. 137), $|G_k|$ is a multiple of $k$. Also $G_k$ contains $S_d$ for each $d$ dividing $k$. Since $|G_k| > k$ and $\sum_{d \mid k} \phi(d) = k$, there remain at least $\phi(k)$ other elements in $G_k$, and we take $\phi(k)$ of them to form $S_k$.

The cyclic group $Z_n$ of order $n$ has exactly $\phi(d)$ elements of order $d$ for each $d$ that properly divides $n$. We construct a bijection $\sigma\colon G \to Z_n$ that maps $S_d$ into the elements of order $d$ in $Z_n$. Thus $o(\sigma(g)) > o(g)$ for all $g \in G$. $\quad\square$

The mistake in the proof is in the last sentence of the second paragraph, where the authors overlooked the fact that some of the sets $S_d$ where $d$ does *not* divide $k$ (but still $\gcd(d,k) \neq 1$) might have used some of the elements of $G_k$, leaving less than $\phi(k)$ elements left in $G_k$.

As F. Ladisch (I think, I hope I'm giving proper credit) pointed out in a comment to an earlier answer by G. Zaimi that was deleted, the proof is fundamentally incorrect, in the sense that only using the combinatorial data implied by Frobenius's Theorem cannot be sufficient to prove the result. For example, let $n=12$, and let

$$|G_1| = 1, |G_2| = 4, |G_3| = 3, |G_4| = 4, |G_6| = 6, |G_{12}| = 12. $$

(This would correspond to a non-existing group with $1$ element of order $1$, $3$ elements of order $2$, $2$ elements of order $3$, and $6$ elements of order $12$.)

Then the sets $G_k$ fulfill the requirements given by Frobenius's Theorem, but still there is no bijection to $Z_n$ satisfying the required statement.

Any ideas are welcome!

4more comments