一开始有 $n$ 张牌，其中 $n$ 为偶数。
一次洗牌定义为将奇数位置的牌按顺序放在前半部分，偶数位置的牌按顺序放在后半部分，具体的说，将

  • 原先 $1,2,3,\cdots,\frac n2$ 位置上的牌放到现在的 $1,3,5,\cdots,n-1$；
  • 原先 $\frac n2+1,\frac n2+2,\frac n2+3,\cdots,n$ 位置上的牌放到现在的 $2,4,6,\cdots,n$。

比如说，当 $n=8$ 的，时候，那么洗牌的置换 $f$ 满足

\[f=\begin{pmatrix}1&2&3&4&5&6&7&8\\1&3&5&7&2&4&6&8\end{pmatrix}\]

不难发现

\[f(i)=\left\{ \begin{matrix} 2i-1,i\le\frac n2\\ 2n-i,i>\frac n2 \end{matrix} \right.\]

如果我们把下标向左平移一位，那么 $f$ 的性质就体现出来了。
下标平移后，

\[f=\begin{pmatrix}0&1&2&3&4&5&6&7\\0&2&4&6&1&3&5&7\end{pmatrix}\]

不妨写成二进制

\[f=\begin{pmatrix}000&001&010&011&100&101&110&111\\000&010&100&110&001&011&101&111\end{pmatrix}\]

可以发现，当 $n$ 为二的幂时，$f$ 实际上就是把二进制下的最低位转移到最高位，不作详细论证。

题目的下标向左平移一位后，那么原题就相当于证明，每个数置换 $1\sim n-1$ 后所得到的数都不同。而置换 $n$ 次之后就回到了本身。

现在令 $m=\log_2n$，因为 $n$ 是二的幂，所以 $m$ 是个整数。
考虑 $n$ 的一个因子 $d$，满足 $d\ne1$ 且 $d\ne n$。
如果把原序列从左往右平均分成 $\frac nd$ 段，每段的长度为 $d$ 的话，只要每段内填的数一样，那么这种填法经过 $d$ 次置换之后就会变成相同的序列，不符合题意。
因此，合法的 $n$ 不存在任何因子 $d$，满足 $d\ne1$ 且 $d\ne n$。
根据质数的定义，得到所有质数都是合法的。