嘿，针对你问的素数幂模n的阶的求解问题，我来给你整理一下可行的方法、公式，还有相关的参考资料～

先拿你举的例子来说：求$3^x \mod 21$的阶，你通过枚举得到周期是6（对应序列3,9,6,18,12,15），这个结果完全正确。下面我们把这个例子拓展成通用的解法：

一、核心求解思路（针对素数p的幂模n的情况） #

首先要明确：当p和n不互质时（比如例子里$\gcd(3,21)=3≠1$），我们讨论的是p的幂在模n下的周期（严格来说，这时候因为p和n不互质，p的幂无法生成模n的简化剩余系，所以不是传统意义上的“阶”，但周期的计算逻辑是相通的）。

通用步骤如下：

1. 分解n的素因子：把n拆成$n = p^s \cdot t$，其中t和p互质。比如21=3^1 *7，这里s=1，t=7；
2. **分析模$p^{s$的情况**：当x≥s时，$p}x ≡0 \mod p^{s$（例子里x≥1时，$3}x \mod3=0$）；当x<s时，$p^x$模$ps$的结果就是$p^x$，不会出现重复，直到x≥s后结果稳定为0；
3. 计算p模t的阶：因为t和p互质，根据欧拉定理，p模t的阶一定是$\varphi(t)$的约数（$\varphi$是欧拉函数）。例子里$\varphi(7)=6$，我们验证6的约数：$3^1=3≠1 \mod7$，$3^2=2≠1 \mod7$，$3^3=6≠1 \mod7$，$3^6≡1 \mod7$，所以p模t的阶是6；
4. 结合得到周期：当x≥s时，模$p^{s$的结果稳定，所以整个$p}x$模n的周期就等于p模t的阶，也就是例子里的6。

如果是求$p^{k$模n的阶（k>1），只需要把第三步改成计算$p}k$模t的阶即可，逻辑是一样的：先算$\varphi(t)$，找出它的所有正约数，从小到大验证哪个最小的d满足$(p^k)d ≡1 \mod t$，这个d就是阶。

二、相关参考资料 #

如果你想深入学习这个话题，可以看看这些经典数论书籍：

• 《初等数论》（David M. Burton）：入门级教材，详细讲解了阶的定义、欧拉定理、中国剩余定理，还有大量计算案例，非常适合理解基础逻辑；
• 《数论导引》（华罗庚）：国内经典数论著作，对模运算的周期和阶有更深入的理论分析，包括非互质场景的拓展讨论；
• 《Elementary Number Theory and Its Applications》（Kenneth H. Rosen）：有专门章节讲解阶的计算算法，还附带了编程实现的思路，实用性很强。

备注：内容来源于stack exchange，提问作者zakrea2070