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

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

首先,如果a是奇数,则它不含有因子2,所以b个a相乘必然没有因数2,即\(a^b\)是个奇数,因此它对一个偶数(这里的\(2^n\))取模得到的一定是一个奇数,所以等式右边也必要是一个奇数,所以b也是个奇数。总结一下:通过上边这个过程,我们得知如果a是个奇数,则b也是个奇数。

我们发现如下规律:

Part 1. 当\(n = 1\)时,由于a是一个奇数,则\(a \% 2 = 1\),我们有:

\(a^b \% 2 = (a \% 2)(a \% 2) … (a \% 2) = a \% 2 = 1\).

同理:

\(b^a \% 2 = (b \% 2)(b \% 2) … (b \% 2) = b \% 2 = 1\).

如果题设等式成立,则:

\(a \% 2  = b \% 2\).                <1>

因为\(b \in [1, 2^n]\),所以对于每一个确定的a,只存在一个b使等式成立。

Part 2. 当\(n = 2\)时,因为奇数的平方模4余1【证明比较比模8的时候要简单,可以去阅读奇数平方模8的证明:关于奇数的平方对8取余(取模)得1的证明】,对于b个(奇数个)a取模,我们运用取模的分配率得到:

\(a ^ b \% 4 = (a ^ 2 \% 4)(a ^ 2 \% 4)…(a \% 4) = a \% 4\).

同理:

\(b ^ a \% 4 = (b ^ 2 \% 4)(b ^ 2 \% 4)…(b \% 4) = b \% 4\).

如果题设等式成立,则:

\(a \% 4  = b \% 4\).                <2>

显然,对于确定的a,\(b \in [1, 4]\)只存在唯一的b。

Part 3. 当\(n = 3\)时,因为奇数的平方模8余1【关于这点的证明请看:关于奇数的平方对8取余(取模)得1的证明】,对于b个(奇数个)a取模,有:

\(a ^ b \% 8 = (a ^ 2 \% 8)(a ^ 2 \% 8)…(a \% 8) = a \% 8\).

同理:

\(b ^ a \% 8 = (b ^ 2 \% 8)(b ^ 2 \% 8)…(b \% 8) = b \% 8\).

如果题设等式成立,则:

\(a \% 8  = b \% 8\).                <3>

显然,对于确定的a,\(b \in [1, 8]\)只存在唯一的b。

Part 4. 当\(n = 4\)时,因为奇数的4次方模16余1【证明部分请阅读:关于奇数的四次方对16取余(取模)得1的证明】,对于b个(奇数个)a取模,有:

\(a ^ b \% 16 = (a ^ 4 \% 16)(a ^ 4 \% 16)…(a^{b \% 4} \% 16) = a^{b \% 4} \% 16\).

同理:

\(b ^ a \% 16 = (b ^ 4 \% 16)(b ^ 4 \% 16)…(b^{a \% 4} \% 16) = b^{a \% 4} \% 16\).

如果题设等式成立,则:

\(a^{b \% 4} \% 16  = b^{a \% 4} \% 16\).

由于前面已经证明过的<2>式\(a \% 4 = b \% 4\),我们可以由上式等价得到:

\(a \% 16  = b \% 16\).                <4>

显然,对于确定的a,\(b \in [1, 16]\)只存在唯一的b。

要证明题设命题,显然不能手动继续逐个n值接着往后推【那样做始终是优先数量的,无法保证结论的普适性】。

所以计划使用数学归纳法:

证明:

Part 1. 对于n = 1以及n = 2的证明,可以直接看上边,这里略过。

Part 2. 假设从n = 1到n = k都有\(a \% 2^n = b \% 2^n\)成立,现在要证明对于\(n = k + 1\)仍然能使上式成立。

我们用到一个结论,就是:对于\(t \in \mathbb{N}\)且\(t \neq 0\),奇数的\(2^t\)次幂被\(2^{t + 1}\)取余后得1【证明请阅读:关于奇数的2^t幂被2^(t + 1)取余得1的证明】。

因此,我们有:

\(\begin{aligned} & a^b \% 2^{k + 1} \\ = & (a^{2^k} \% 2^{k + 1})(a^{2^k} \% 2^{k + 1})…(a^{2^k} \% 2^{k + 1})a^{b \% 2^{k}} \% 2^{k + 1} \\ = & a^{b \% 2^{k}} \% 2^{k + 1} \end{aligned}\)                <5>

\(\begin{aligned} & b^a \% 2^{k + 1} \\ = & (b^{2^k} \% 2^{k + 1})(b^{2^k} \% 2^{k + 1})…(b^{2^k} \% 2^{k + 1})b^{a \% 2^{k}} \% 2^{k + 1} \\ = & b^{a \% 2^{k}} \% 2^{k + 1} \end{aligned}\)                <6>

根据\(a \% 2^k = b \% 2^k\),\(a^b \% 2^n = b^a \% 2^n\),以及<5><6>式,我们便推出\(a \% 2^{k + 1} = b \% 2^{k + 1}\)。

至此,满足数学归纳法的两个条件,因此我们证明了当a是奇数的时候,总能够由\(a^b \% 2^n = b^a \% 2^n\)推出\(a \% 2^n = b \% 2^n\),因为b的取值范围是\([1, 2^n]\),所以对于每一个确定的a,显然在取值范围内只存在1个b使上式成立。

证毕。

 

用到了这个结论的ACM赛题:【HDU-6189】Law of Commutation