【趣题征解】证明：当 n 是一个大于 1 的奇数时，3^n+1 不可能被 n 整除

luyuanhong

【趣题征解】证明：当 n 是一个大于 1 的奇数时，3^n+1 不可能被 n 整除。
例如，n＝3 时，3^n+1＝3^3+1＝28 ，不能被 3 整除。
      n＝5 时，3^n+1＝3^5+1＝244 ，不能被 5 整除。
      n＝7 时，3^n+1＝3^5+1＝2188 ，不能被 7 整除。

luyuanhong

请楼上想一想：能从 3^n×(3^n+1)≡0(mod n) 推出 3^n≡0(mod n) 吗？

w632158

不能推出。

w632158

A*0=0能推出A等于0吗？

awei

的确是搞错了，呵呵！

王成5

任在深

证
  因为 3^n+1=2m,  m=1,2,3,,,
    若 m=an,3^n+1=2an才能被n整除，则 n=m/a,   n是大于1的奇数！
  而
     n=m/a 不是正整数，所以不符合题意！
  因此 3^n+1,不可能被n整除！
    证毕。
                关公面前耍大刀了！

luyuanhong

【趣题征解】证明：当 n 是一个大于 1 的奇数时，3^n+1 不可能被 n 整除。

【证】用反证法。
    假设有大于 1 的奇数 n 满足 n|3^n+1 。设 p 是 n 的最小的素数因子。
    因为 n|3^n+1 ，n 不可能是 3 的倍数，所以 p≠3 ，p 与 3 互素，所以
由 Fermat 小定理可知，必有 3^(p-1)≡1(mod p) 。
    同时又因为 3^n+1 是 n 的倍数，因而也是 p 的倍数，所以 3^n+1≡0(mod p) ，
即有 3^n≡-1(mod p) ，3^(2n)≡3^n×3^n≡(-1)×(-1)≡1(mod p) 。
    将 3^(p-1)≡1(mod p) 与 3^(2n)≡1(mod p) 两式辗转相除，最后可得
3^(p-1,2n)≡1(mod p) 。
    因为 n 是奇数，所以 p 也是奇数，p-1 是偶数，又因为 (p-1,n)＝1 ，所以
(p-1,2n)＝2 ，所以有 3^(p-1,2n)＝3^2＝9≡1(mod p) ，即有 9-1≡8≡0(mod p) 。
但 p 是奇素数，8 不可能被 p 整除，这就产生了矛盾。
    所以假设不成立，不可能有大于 1 的奇数 n 满足 n|3^n+1 。

任在深

楼主的证明是否时间长了一些？