关于奇数的2^t幂被2^(t + 1)取余得1的证明

关于奇数的\(2^t\)幂被\(2^(t + 1)\)取余得1的证明

证明:

奇数可以表示为(2k + 1)的形式,因此对于\((2k + 1)^{2^t}\),我们根据二项式定理有:

\(\begin{aligned} & (2k + 1)^{2^t} \\ = & (^{2^t}_{2^t})2^{2t}k^{2t} + (^{2^t}_{2^{t – 1}})2^{2t – 1}k^{2t – 1} + … + (^{2^t}_1)2k + 1 \\ = & 2^{2t}k^{2t} + 2^t \cdot 2^{2t – 1} \cdot k^{2t – 1} + … + 2^t \cdot 2k + 1 \\ = & 2^{t + 1}k(2^{t – 1}k^{2t – 1} + 2^{t – 2}k^{2t – 2} + … + 1) + 1 \end{aligned}\).

由于结果除去括号最外层值为1的项,其具有因数\(2^{t + 1}\),即证明了它能被\(2^{t + 1}\)整除,考虑回来那个值为1的项后,得到结论,奇数的\(2^t\)次幂被\(2^{t + 1}\)取余得到1.

证毕。

 

注:补充,虽然上面已经证明了命题,但是需要补充的一点是,它被\(2^(t + 2)取余得1,原因是,[latex]k\)与

\(2^{t – 1}k^{2t – 1} + 2^{t – 2}k^{2t – 2} + … + 1\),

二者之间必然有一个是偶数,所以它能够被2整除,于是奇数的\(2^t\)次幂能被\(2^{t + 2}\)取余得到1。

 

相关问题:

关于奇数的平方对8取余(取模)得1的证明

关于奇数的四次方对16取余(取模)得1的证明

关于对a^b % 2^n = b^a % 2^n,当a为奇数时,在范围[1, 2^n]有且仅有一个b使等式成立的证明