求3²⁹除以12的余数，排查模运算推导错误

首先，咱们先复盘一下你的思路：你把3²⁹ ÷ 12转化成了3²⁸ ÷ 4，然后利用9 ≡ 1 mod4推出9¹⁴ ≡1¹⁴ mod4，得到余数1，但这个结果和选项对不上——问题就出在被除数和除数同时缩小的时候，余数不能直接等价转换！

咱们拆解一下为什么错：

• 当计算3²⁹ ÷12的余数时，正确的表达式应该是：3²⁹ = 12*k + r，其中0 ≤ r <12。而且因为3²⁹是3的倍数，12*k也是3的倍数，所以r必须是3的倍数（这是你之前忽略的核心点！）。
• 你把式子两边除以3得到3²⁸ =4*k + r/3，这时候r/3是3²⁸ ÷4的余数，你算出这个余数是1，那对应的r/3=1，所以r=3——这才是3²⁹ ÷12的正确余数！

另外，咱们也可以用找规律的方法快速验证：

• 3¹ ÷12余数是3
• 3² ÷12余数是9
• 3³=3²*3=9*3=27，27÷12余数是3
• 3⁴=3³*3=27*3=81，81÷12余数是9
• 明显能看到规律：3的奇数次幂除以12的余数都是3，偶数次幂是9。29是奇数，所以3²⁹ ÷12的余数是3，对应选项b。

内容的提问来源于stack exchange，提问作者space