【趣题征解】设 p 是大于 3 的素数，n＝[2^(2p)-1]/3 ，证明：2^(n-1)-1 能被 n

luyuanhong

[这个贴子最后由luyuanhong在 2011/08/28 08:22am 第 2 次编辑]

【趣题征解】设 p 是大于 3 的素数，n＝[2^(2p)-1]/3 ，证明：2^(n-1)-1 能被 n 整除。
提示：如果 m 能被 n 整除，则 a^m-1 也能被 a^n-1 整除。

moranhuishou

因为
n＝[2^(2p)-1]/3
所以
3＝[2^(2p)-1]/n
设m=2^(2p)-1
因为m 能被 n 整除
（由提示）
所以
2^(n-1)-1 能被 n 整除。

luyuanhong

[这个贴子最后由luyuanhong在 2011/08/28 09:53am 第 3 次编辑]

下面引用由moranhuishou在 2011/08/28 09:00am 发表的内容：
因为
n＝[2^(2p)-1]/3
所以
3＝[2^(2p)-1]/n
设m=2^(2p)-1
因为m 能被 n 整除
（由提示）
所以
2^(n-1)-1 能被 n 整除。

只有在“已知 m 能被 n 整除”的条件下，才能推出“a^m-1 能被 a^n-1 整除”的结论。
楼上想要推出“2^(n-1)-1 能被 2^(2p)-1 整除”的结论，就必须先证明“n-1 能被 2p 整除”。
这才是此证明中最关键之处。

w632158

luyuanhong

[这个贴子最后由luyuanhong在 2011/08/28 03:47pm 第 1 次编辑]

楼上 w632158 的证明很详细，基本正确，很好！
不过有个小小笔误：
“又因为 a^d-1|a^n-1，所以 a^r-1|a^d-1”，
应改为
“又因为 a^d-1|a^n-1，所以 a^d-1|a^r-1”。
另外，证明 2p|n-1 其实还可以更简单一些。
下面是我的证明：

【趣题征解】设 p 是大于 3 的素数，n＝[2^(2p)-1]/3 ，证明：2^(n-1)-1 能被 n 整除。
提示：如果 m 能被 n 整除，则 a^m-1 也能被 a^n-1 整除。

【证】因为 2p 能被 2 整除，所以 2^(2p)-1 能被 2^2-1＝3 整除，所以 n＝[2^(2p)-1]/3
是正整数。（一般来说，有这样的结论：2 的偶数次方减 1 必定是 3 的倍数。）
  n-1＝[2^(2p)-1]/3-1＝[2^(2p)-4]/3＝4[2^(2p-2)-1]/3＝4[2^(p-1)+1][2^(p-1)-1]/3 。
    因为（2,p)=1，由 Fermat 小定理可知，2^(p-1)-1≡0(mod p) ，2^(p-1)-1 是 p 的倍数。
    又因为 p≠3 ，所以 [2^(p-1)-1]/3 也还是 p 的倍数，因此 n-1 是 p 的倍数。
    又因为 n-1 的因式中含有 4 ，n-1 是偶数，所以 n-1 是 2p 的倍数。
    因为 n-1 是 2p 的倍数，所以 2^(n-1)-1 能被 2^(2p)-1 整除。
    而 2^(2p)-1＝3n 又是 n 的倍数，所以 2^(n-1)-1 能被 n 整除。

w632158

不错，运用之妙出乎于心。