关于对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

关于奇数的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使等式成立的证明

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

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

证明:

对于一个奇数,它显然可以表示为\(2k + 1\),则根据二项式定理我们有:

\(\begin{aligned} (2k + 1)^4 & = (^4_4) 2^4 k^4 + (^4_3) 2^3 k^3 + (^4_2) 2^2 k^2 + (^4_1) 2k + 1 \\ & = 16k^4 + 32k^3 + 24k^2 + 8k + 1 \\ & = 8k(2k^3 + 4k^2 + 3k + 1) + 1 \end{aligned}\)

可以证明,\(k\)与\(2k^3 + 4k^2 + 3k + 1\)二者中必然有一个是偶数,所以\(8k(2k^3 + 4k^2 + 3k + 1)\)可以被16整除,因此\(8k(2k^3 + 4k^2 + 3k + 1) + 1\)对16取余得1,即奇数的4次方对16取余得1.

证毕。

 

相关问题:

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

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

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

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

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

证明:

【注:%表示取余(也叫取模)】

对于\(\forall n \in \mathbb{R}\)满足\(n \% 2 = 1\),总\(\exists k \in \mathbb{R}\)使得\(n = 2k + 1\)。

所以有:

\(n^2 = (2k + 1)^2 = 4k^2 + 4k + 1 = 4k(k + 1) + 1\).

其中,\(k(k + 1)\)中k与k + 1二者必然存在一个偶数,因此\(k(k+1)\)能被2整除,即\(k(k + 1) \% 2 = 0\)。所以有,\(4k(k+1) \% 8 = 0\),因此\((4k(k+1) + 1) \% 8 = 1\),也就是一个奇数的平方对8取余得1。

证毕。

 

相关问题:

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

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

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