【趣题征解】证明：对任何正整数 n ，19×8^n+17 必定是合数

luyuanhong

[这个贴子最后由luyuanhong在 2011/08/10 04:38pm 第 1 次编辑]

【趣题征解】证明：对任何正整数 n ，19×8^n+17 必定是合数。
例如，n＝1 时，19×8^1+17＝19×8+17＝169＝13^2 是一个合数。
      n＝2 时，19×8^2+17＝19×64+17＝1233＝3^2×137 是一个合数。
      n＝3 时，19×8^3+17＝19×512+17＝9745＝5×1949 是一个合数。

旅游者

当 n = 1，5，9，13，17，……时， 19*8^n +17 中必有 13 的因子；
当 n = 2，4，6，8，10，……时， 19*8^n +17 中必有 3 的因子；
当 n = 3，7，11，15，19，……时， 19*8^n +17 中必有 5 的因子。
具体怎样证明，还没有考虑呢。

旅游者

当 k = 0，1，2，3，4，……时，4*k+1，4*k+2，4*k+3，4*k+4 可表示出全部的自然数。因此本题可考虑这样证明：
   证明当 n = 4*k+1 时，19*8^n + 17 可以被 13 整除；
       当 n = 4*k+3 时，19*8^n + 17 可以被  5 整除；
       当 n 是偶数时，19*8^n + 17 可以被 3 整除。

旅游者

[这个贴子最后由旅游者在 2011/08/10 07:17pm 第 2 次编辑]

先证明一下，当 n 是偶数时，19*8^n + 17 可以被 3 整除。
  因为 mod(19,3)=1,
       mod(8^n,3)=1,  n 为偶数
  所以，当 n 是偶数时 mod(19*8^n,3) = 1*1=1, 而 1+17=18 能被 3 整除，
  所以 mod(19*8^n+17,3) = 0,
  就是说，当 n 是偶数时，19*8^n + 17 可以被 3 整除。

旅游者

第二步，证明当 n 是 4*k+1 时，19*8^n + 17 可以被 13 整除。
也就是要证明 19*8*8^4k +17 可以被 13 整除。
因为 mod(19*8, 13) = 9,
      mod(8^4k, 13) = 1,  k = 0，1，2，3，……
所以， mod(19*8*8^4k, 13) = 9*1 = 9, 而 9+17 =26 能被 13 整除，
所以 19*8*8^4k +17 可以被 13 整除，也就是当 n 是 4*k+1 时，19*8^n + 17 可以被 13 整除。

旅游者

第三步，证明当 n 是 4*k+3 时，19*8^n + 17 可以被 5 整除。
也就是要证明 (19*8^3)*(8^4k) +17 可以被 5 整除。
因为 mod(19*8^3, 5) = 3,
     mod(8^4k, 5) = 1,  k = 0，1，2，3，……
所以， mod((19*8^3)*(8^4k), 5) = 3*1 = 3, 而 3 +17 = 20 能被 5 整除，
所以 (19*8^3)*(8^4k) +17 可以被 5 整除，也就是当 n 是 4*k+3 时，19*8^n + 17 可以被 5 整除。
这就完成了全部证明。
证明对否？

王成5

[这个贴子最后由王成5在 2011/08/10 08:41pm 第 1 次编辑]

w632158

n为非负数即可。原命题即为合数

luyuanhong

楼上几位的证明思路都很正确，很好！

tian27546